Sudoku solver written in Java
2009-05-16 00:52 by Ian
Sudoku solver and the puzzle class file that goes with it. This was written as a conceptual exercise for a friend who was curious about the creative freedom that can be found in programming. It is not glamorous, but it can correctly solve a valid sudoku 100% of the time. And it can do it 4000 times faster than you can. It can even guess semi-intelligently if it doesn’t know where to move with certainty.
The data structure employed is a three-dimensional array of size (n x n x n+1), where n is the number of unique symbols in the puzzle. Yeah, it uses brute-force recursion to achieve a solve in 100mS, but it chooses which cell to guess for based on which cell has the highest probability of a successful guess.
Below is a conceptual sketch that I wrote out before writing the program. It explains things much better than I can with words alone.
Click for full-size image:
Previous: HC11 32-bit by 32-bit multiplication routine
Next: IDE Interface in a Xilinx 9572 CPLD