Sudoku Solver Algorithm

[x-ice]

Hi,

I have written out the steps to a sudoku solver, do you think I am missing anything?

-Find empty cell
	    -Check current cell
	    -If current cell not empty, move to next
	    -Stop when empty cell is found
	    -If not empty cells exist the puzzle is solved
-Try possible numbers
	    -Start at 1 and work way to 9
	    -Build list of possible numbers
	    -Check if possible number already exists in row, column and segment
	    -If above is true number is eliminated as it can't go in the cell
	    -Place the number in the cell if it is the ONLY possible number
-Repeat this process until the board is solved

Thanks

[si_the_geek]

Your "repeat" should ideally only be for the 3 steps before it (but you will need to store the possible numbers for each cell).

It should also have two exit conditions - when the board has completely filled, or when no work has been done in the latest loop.


Your methods will also not solve every Sudoku, as some of them require more advanced ways... but I think it should do most of them.

[x-ice]

Your "repeat" should ideally only be for the 3 steps before it (but you will need to store the possible numbers for each cell).

It should also have two exit conditions - when the board has completely filled, or when no work has been done in the latest loop.


Your methods will also not solve every Sudoku, as some of them require more advanced ways... but I think it should do most of them.

Sorry i'm not sure I understand where you are coming from, can you alter the steps to show what you are suggesting?

[si_the_geek]

It would be something like this:

-Find empty cell
	    -Check current cell
	    -If current cell not empty, move to next
	    -Stop when empty cell is found
	    -If not empty cells exist the puzzle is solved
- Add possible numbers to all empty cells
            -Store all numbers 1 to 9 for each empty cell
- Solve 
            - For each empty cell, check if the possible numbers already exists in row, column and segment
	    -If above is true number is eliminated as it can't go in the cell
	    -Place the number in the cell if it is the ONLY possible number
-Repeat the 'Solve' section until the board is solved, or no work was done

[Golgo1]

The problem with looping only the solve section is that there are sometimes situations where, given the information available on the grid, there is more than ONE possible number for squares.
Obviously there is only one CORRECT answer, but with limited information, there is no indication which is correct.
This would result in an endless loop given the above process (unless you consider that 'no work'?)
I think that is one of the challenges when making sudoku solvers, you have to build in at least a little bit of speculation and experimentation.

[si_the_geek]

For each of the 'empty' squares you would keep track of all possible numbers for that square.

The 'no work' would mean that none of the possible numbers were eliminated (which includes placing the final number) for any of those squares during the latest iteration.


While speculation and experimentation can be necessary in some Sudoku's, they aren't for most.

In terms of programming those are rather complex, as you need to be able to backtrack to the last 'guess' and try the alternative options from that point (and if necessary, backtrack to an earlier guess). That would require several extra copies of the data, and some extra variables for keeping track of the guesses too.

[Golgo1]

Yeah, adding in even a small level of 'guessing' would be a fair bit of work. It would depend how many levels deep you wanted to go.
As mentioned by the geek, as long as the condition is in there to exit if nothing has changed then I think this process should work for most situations.

To save a few checks, I'd add a bit of logic to skip the 'empty cell' if it already has it's unique value assigned. (Its not in the above psudocode, maybe it was just assumed?)

[si_the_geek]

To save a few checks, I'd add a bit of logic to skip the 'empty cell' if it already has it's unique value assigned. (Its not in the above psudocode, maybe it was just assumed?)

My assumption of "empty" is that it is a cell that doesn't have its final value yet.