simple sudoku

rachel7430 · 07-03-2009, 07:42 AM

both...

Erica · 07-03-2009, 07:59 AM

Quote:

Originally Posted by legit

Dude, post your code and your problem... Your trying to make us find treasure with no map here!

Fyi, she hasn't start her coding.
Else, she would have shown it here.
All she needs is the whole concept about it.
And where and how she should start it.

legit · 07-03-2009, 08:11 AM

Quote:

Originally Posted by Erica

Fyi, she hasn't start her coding.
Else, she would have shown it here.
All she needs is the whole concept about it.
And where and how she should start it.

Yes I realise that

Erica · 07-03-2009, 08:14 AM

help her on.

legit · 07-03-2009, 08:23 AM

Quote:

Originally Posted by Erica

help her on.

I would if I had ever made a sodoku solver before, maybe I should have a go now and see where I get.

Erica · 07-03-2009, 08:31 AM

ahaha
cool.

btw, the main thing is it allow user to enter 16 numbers without repetition at each column and row?

legit · 07-03-2009, 08:35 AM

Lemmi guess, you guys are in the same class? And it depends, the sodoku may be larger than 16x16. A sodoku solver, from my point of view, should solve a pre-set/pre-loaded incomplete sodoku.

Erica · 07-03-2009, 08:40 AM

Quote:

Originally Posted by legit

A sodoku solver, from my point of view, should solve a pre-set/pre-loaded incomplete sodoku.

Hurm...
I don't get what do you mean by pre-set/pre-loaded incomplete sudoku..
Further explanation please..

legit · 07-03-2009, 08:46 AM

Opinions may vary, but mine is that a sodoku solver should be able to complete an incomplete sodoku either loaded to the program, or defined by the user at run-time.

Erica · 07-03-2009, 08:56 AM

meaning I need to came out with an algorithm of the game itself first?

legit · 07-03-2009, 09:07 AM

Well what do you have so far, design wise?

Erica · 07-03-2009, 09:23 AM

just started the design phase..
but still kinda stuck with the whole thingy.

what kind of condition should I assign to in order to check if the user repeated the number?

legit · 07-03-2009, 11:38 AM

I've been thinking - creating a sodoku solver would be difficult without using arrays? I can't seem to find a way without arrays, using arrays is still pretty tough!

dwks · 07-03-2009, 04:54 PM

I've written a sudoku solver before, but I should mention that I wrote it out of my head without doing any research first. I'm reasonably good at solving sudoku puzzles, but I'm sure you'd find more waterproof methods if you looked around.

Anyway, the method I used went something like this. I represented all of the data in the puzzle as a two-dimensional array, and applied various algorithms to the puzzle until it was solved or the puzzle was unchanged (in which case the program wasn't good enough to solve it). The algorithms would be strategies that you might use when solving a sudoku puzzle by hand; e.g., if eight of the nine numbers in a row are filled out, then the last number is whichever number does not appear in the row.

As I said, it's a reasonably good method, but not perfect. For one thing, it doesn't completely model how a human sudoku-solver will think. A lot of the thought process goes something like this: "if I put this 7 here, would it create an impossibility?" Here an "impossibility" is something like two 7's in the same quadrant, column, or row. If it is impossible, you rule out that move, which narrows down your choices; maybe since the 7 can't go there, it has to go somewhere else. And so on.

I never did look at a "real" sudoku-solving program. There are lots of them online that profess to be able to solve any sudoku puzzle (which is certainly possible). If you want more ideas you could see how some of them work.

Well, here I was talking about automatically solving sudoku puzzles. You'll have to forgive me if that's not what you want, since you haven't been very clear on that point. Are you just trying to create a sudoku game that ensures that every move the player makes is a valid one?

That's pretty easy. When the user asks to place a '7' in a particular spot, you just scan that row and column for other sevens, and that quadrant too. I'm not sure if "quadrant" is quite the right word, but you know what I mean. Here's the sort of code you might use.

Code:

/** Check to see if the user made a valid move. The user is assumed to have
    attempted to place the number @a number at position @c data[x][y].
*/
int is_valid_move(int data[9][9], int x, int y, int number) {
    /* The x and y coordinates of the upper-left corner of the quadrant
        in which the position (x, y) lies.
    */
    int qx = (x / 3) * 3, qy = (y / 3) * 3;

    int i, j;
    for(i = 0; i < 9; i ++) {
        /* check this column */
        if(data[x][i] == number) return 0;

        /* and this row */
        if(data[i][y] == number) return 0;
    }

    /* check this quadrant */
    for(int i = 0; i < 3; i ++) {
        for(int j = 0; j < 3; j ++) {
            if(data[qx + i][qy + j] == number) return 0;
        }
    }

    /* The number wasn't duplicated in the column, row, or quadrant;
        therefore, this must be a valid move.
    */
    return 1;
}

That assumes you use -1 or something to represent a square which has not been given any number.

Anyway, enough blathering. If you want more help you'd better describe what you're trying to do.

scwizzo · 07-03-2009, 07:13 PM

In relation to the solution dwks said, I implemented a way for the solver to check if there are any numbers that absolutely cannot be any other number than a single number. After each move, since each number placement could determine the placement of another number.

07-03-2009, 07:42 AM	#16
rachel7430 Registered User Join Date: Jul 2009 Posts: 19	both...
rachel7430 is offline

07-03-2009, 08:14 AM	#19
Erica Registered User Join Date: Jun 2009 Posts: 9	help her on.
Erica is offline

07-03-2009, 08:31 AM	#21
Erica Registered User Join Date: Jun 2009 Posts: 9	ahaha cool. btw, the main thing is it allow user to enter 16 numbers without repetition at each column and row?
Erica is offline

07-03-2009, 08:35 AM	#22
legit Student Join Date: Aug 2008 Location: UK -> Newcastle Posts: 156	Lemmi guess, you guys are in the same class? And it depends, the sodoku may be larger than 16x16. A sodoku solver, from my point of view, should solve a pre-set/pre-loaded incomplete sodoku. __________________ MSDN <- Programmers Haven!
legit is offline

07-03-2009, 08:46 AM	#24
legit Student Join Date: Aug 2008 Location: UK -> Newcastle Posts: 156	Opinions may vary, but mine is that a sodoku solver should be able to complete an incomplete sodoku either loaded to the program, or defined by the user at run-time. __________________ MSDN <- Programmers Haven!
legit is offline

07-03-2009, 08:56 AM	#25
Erica Registered User Join Date: Jun 2009 Posts: 9	meaning I need to came out with an algorithm of the game itself first?
Erica is offline

07-03-2009, 09:07 AM	#26
legit Student Join Date: Aug 2008 Location: UK -> Newcastle Posts: 156	Well what do you have so far, design wise? __________________ MSDN <- Programmers Haven!
legit is offline

07-03-2009, 09:23 AM	#27
Erica Registered User Join Date: Jun 2009 Posts: 9	just started the design phase.. but still kinda stuck with the whole thingy. what kind of condition should I assign to in order to check if the user repeated the number?
Erica is offline

07-03-2009, 11:38 AM	#28
legit Student Join Date: Aug 2008 Location: UK -> Newcastle Posts: 156	I've been thinking - creating a sodoku solver would be difficult without using arrays? I can't seem to find a way without arrays, using arrays is still pretty tough! __________________ MSDN <- Programmers Haven!
legit is offline

07-03-2009, 04:54 PM	#29
dwks Frequently Quite Prolix Join Date: Apr 2005 Location: Canada Posts: 7,629	I've written a sudoku solver before, but I should mention that I wrote it out of my head without doing any research first. I'm reasonably good at solving sudoku puzzles, but I'm sure you'd find more waterproof methods if you looked around. Anyway, the method I used went something like this. I represented all of the data in the puzzle as a two-dimensional array, and applied various algorithms to the puzzle until it was solved or the puzzle was unchanged (in which case the program wasn't good enough to solve it). The algorithms would be strategies that you might use when solving a sudoku puzzle by hand; e.g., if eight of the nine numbers in a row are filled out, then the last number is whichever number does not appear in the row. As I said, it's a reasonably good method, but not perfect. For one thing, it doesn't completely model how a human sudoku-solver will think. A lot of the thought process goes something like this: "if I put this 7 here, would it create an impossibility?" Here an "impossibility" is something like two 7's in the same quadrant, column, or row. If it is impossible, you rule out that move, which narrows down your choices; maybe since the 7 can't go there, it has to go somewhere else. And so on. I never did look at a "real" sudoku-solving program. There are lots of them online that profess to be able to solve any sudoku puzzle (which is certainly possible). If you want more ideas you could see how some of them work. Well, here I was talking about automatically solving sudoku puzzles. You'll have to forgive me if that's not what you want, since you haven't been very clear on that point. Are you just trying to create a sudoku game that ensures that every move the player makes is a valid one? That's pretty easy. When the user asks to place a '7' in a particular spot, you just scan that row and column for other sevens, and that quadrant too. I'm not sure if "quadrant" is quite the right word, but you know what I mean. Here's the sort of code you might use. Code: /** Check to see if the user made a valid move. The user is assumed to have attempted to place the number @a number at position @c data[x][y]. / int is_valid_move(int data[9][9], int x, int y, int number) { / The x and y coordinates of the upper-left corner of the quadrant in which the position (x, y) lies. / int qx = (x / 3) 3, qy = (y / 3) * 3; int i, j; for(i = 0; i < 9; i ++) { /* check this column / if(data[x][i] == number) return 0; / and this row / if(data[i][y] == number) return 0; } / check this quadrant / for(int i = 0; i < 3; i ++) { for(int j = 0; j < 3; j ++) { if(data[qx + i][qy + j] == number) return 0; } } / The number wasn't duplicated in the column, row, or quadrant; therefore, this must be a valid move. / return 1; } That assumes you use -1 or something to represent a square which has not been given any number. Anyway, enough blathering. If you want more help you'd better describe what you're trying to do. __________________ dwk Seek and ye shall find. quaere et invenies.* "Simplicity does not precede complexity, but follows it." -- Alan Perlis "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra "The only real mistake is the one from which we learn nothing." -- John Powell Other boards: DaniWeb, TPS Unofficial Wiki FAQ: cpwiki.sf.net My website: http://dwks.theprogrammingsite.com/ Projects: codeform, xuni, atlantis, etc. New project: nort
dwks is offline

07-03-2009, 07:13 PM	#30
scwizzo Registered User Join Date: Mar 2007 Posts: 335	In relation to the solution dwks said, I implemented a way for the solver to check if there are any numbers that absolutely cannot be any other number than a single number. After each move, since each number placement could determine the placement of another number. __________________ home page (new layout)
scwizzo is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
creating very simple text editor using c	if13121	C Programming	6	11-25-2004 09:49 AM
Simple message encryption	Vicious	C++ Programming	10	11-07-2004 11:48 PM
Binary Search Trees Part III	Prelude	A Brief History of Cprogramming.com	16	10-02-2004 03:00 PM
Simple simple program	Ryback	C++ Programming	10	09-09-2004 05:48 AM
Need help with simple DAQ program	canada-paul	C++ Programming	12	03-15-2002 08:52 AM