Basic Approach

King Wonka · Posted: Mon Dec 19, 2005 8:31 pm Post subject: Basic Approach

How does this sound for just a pure generator in pseudo-code. I really don't want to re-use any code here but advice is welcome. I have a general idea for creating a sudoku board but but it doesn't quite get one finished.

1. set up a Grid[9,9] array, Row[9,10],Col[9,10],Box[9,10]
2. select 3 random numbers (row=0 thru 8, col=0 thru 8, n=1 thru 9)
3. check to see if the cell is unused
4. check to see if the number already exists in row, col, or box
5. if cell is empty and it doesn't exist in row,col, or box then plug in the number
6. if it does exist, cross it off the list for those row,col,box and set Grid[r,c]=0
7. repeat until total count of grid[r,c]=81

This sounds ok on paper but it's getting the grid about 70% done and starts over because it runs out of options. What can I do to keep it simple but make it do what it's supposed to? Thanks

Anthony

Ruud · Site Admin

Hi Anthony,

been there, done that.

It does fail because you are just using only the basic rules to check if a cell is valid. This is fine for the first few digits, but after a while, the depencencies start to work and you are filling digits that should not go there. One normally uses a backtracking solver to check whether there is still a valid solution, then remove the digit when that is not the case.

There is a way to bypass this, that is when you start counting the number of digits that can still go into a cell. When you give priority to cells that have the least number of candidates, you will see that the program does not fail so often.

Ruud.
_________________
Meet me at sudocue.net

King Wonka · Posted: Tue Dec 20, 2005 8:41 pm Post subject:

Well I got the generator working and didn't use any code from here! That was my goal. Here's how it works:

1. make the grid[9,9]
2. set up arrays for Row and Col to store what's been used where(didn't use box and it's just fine)
3. break the grid up into nine 3x3 mini grids
4. start placing 1s first...one in each mini grid
5. then do 2s, 3s, etc placing all 9 of each number at once
6. if there's a conflict...delete the current number and previous number from the grid and start again with the previous number
7. when n=10 then we have a successful sudoku

Cranks em out at about 1 every 20-50ms. I've seen faster generators but this will do nicely (plus I'm proud of it Very Happy

)

Now to move onto to a solver so I can start removing clues and doing symmetry. Twisted Evil

King Wonka · Posted: Thu Dec 22, 2005 6:29 pm Post subject:

Here's what my generator is putting out now. Symmetry is in...the basic rules are in. So how do these look?

Ruud · Site Admin

The basic rules say:

There should be a 7 there, right?

The other 4 also fail at the basic rules.

You need to check remaining candidates, Anthony.

Ruud.
_________________
Meet me at sudocue.net