If you are going to write a Sudoku solver, write a brute force, depth first search. You can get it running fast enough.

But what if you couldn’t? What if the puzzles were so big that solving them by brute force was not computationally feasible? A Sudoku puzzle is build on a basis of 3: The Blocks are 3X3, there are 3X 3 of them in the puzzle, and the rows and columns are are 9 cells (3 * 3) long. This approach scales up. If you were to do a basis of 4, you could use the Hexadecimal digits, and have 16 X 16 puzzles.

A Basis of K leads to a puzzle size of (K^4). The basis can be any integer. A Basis of 10 would lead to a puzzle size of 1000.

The Sudoku puzzle shows exponential growth. https://en.wikipedia.org/wiki/Combinatorial_explosion#Sudoku

What could you do for a complex puzzle? Use heuristics to reduce the problem set to the point where a the brute force algorithm can complete.

Continue reading →