Sudoku Solver

So once upon a time I had a need to create a sudoku solver. I wrote it in Lua, which might not have been the most efficient thing to do. Either way, here it is now for your viewing pleasure.

The solver is broke into two pieces: the first part that solves all forced coloring by a process of elimination, and the second part that solves using backtracking.

Here is how the first part works: Associated with each tile is a set of nine flags for what values the tile might be. When solving for forced coloring the algorithm runs through all the spaces in the board with unknown values and sets all of their the maybe flags on. After this the algorithm goes through all spaces with known values. For each of these spaces, the maybe flag indexed by the value of the known space is cleared. Once this is done any space without a known value will have a maybe flag set for all values it could possibly be. Any unknown space with only one maybe flag set has to be the value of that maybe flag, so we set it and continue on. The algorithm continues until no more spaces can be deduced this way.

The second part works like anyone would expect it to. After the board has been run through the first part, all spaces with still no known values are put into a list. They are each given their own list of indexes for each maybe flag set. Next the solver recursively runs through the list of unknown spaces. For each space it cycles through all possible indexes that it can be, setting itself to the index so long as a maybe flag will allow it to. If it continues like this to the end of the list then it wins. If not then it returns back through the recursion and the previous space in the recursion tries on the next value in its index list.

This solver requires Lua to be installed. To run the solver, type the following command:

`lua sudoku.lua`

I got one sudoku database from Dr. Prasad Tadepalli. He can be reached at tadepall@engr.oregonstate.edu. His database comes with boards, skill levels, and authors, but sadly no puzzle solutions. You will have to rely upon the solver to find these.

To run the solver on a specific problem from Dr. Tadepalli, run the following command, for \$n being the one-based index of the puzzle you want:

`lua -e 'prasad=\$n' sudoku.lua`

To run the solver on a certain skilled puzzle of Dr. Tadepalli's database, run the following command, for \$n being the index of the puzzle and \$m the skill:

`lua -e 'prasad=\$n skill="\$m"' sudoku.lua`
Valid skills are easy, medium, hard, and evil

Another good place for sudoku puzzles is this place, which holds all possible isomorphisms of 17-hint sudoku puzzles known to mankind: http://people.csse.uwa.edu.au/gordon/sudokumin.php Sadly these puzzles don't have solutions. They don't even have difficulty levels. I think this is because they are impossible to solve without the use of a computer.

To run the solver on a 17-hint puzzle run the following command:

`lua -e 'seventeen=\$n' sudoku.lua`