Sudoku Helper 1.3
There are huge changes in the solving algorithm. It now solves 9×9 Sudoku (or finds out that it is unsolvable) in less than 15ms. It also solves 99% of Sudoku 16×16 with 40 random numbers in less than 1 second. The remaining 1% is solved in over 5 minutes, but I have also found such a Sudoku that my algorithm was unable to solve in 30 minutes. If you like challenges and would like to show me that your skills are much better than my programming skills, feel free to solve it – you will find it below. Solving algorithm also now has a 2 second timeout, so the program will no longer freeze, but will display a message “too complex puzzle”. I am going to implement over the weekend a Sudoku generator that generates puzzles with one unique solution. But for now, here is a jar file and here is the code.
- added: advanced automatic suggestions removal.
- added: if solving/validating the puzzle takes more than 2 seconds, the puzzleis considered too complex and the algorithm stops.
- fixed: solving algorithm improved – it now undoes its changes rather than making a grid’s copy before each change. It works about twice as fast as the previous algorithm, and moreover do not use that much memory.
- fixed: sudoku is now in a scroll pane – it is possible to play 16×16 Sudoku in low screen resolution.
- changed: filling a cell clears all suggestions in this cell if auto suggestions remove is on – it can be undone.
How do solving algorithms work:
The grid consists of N*N x N*N cells (e.g. in Sudoku 9×9 N = 3 and there are 81 cells). The zone is a row, a column or a square, it contains N*N cells. The square is a NxN large part of the grid (in 9×9 there are 9 squares of size 3×3). The neighbours are all those cells that share the zone with the cell. Also each cell contains a filled number and the set of possibilities (candidates).
1. Basic suggestions removal:
for each cell C for each possibility P in C if any neighbour of C is filled with P remove P from C' possibilities
2. Basic auto fill:
for each cell C if there is only one number in C' possibilities fill it in
3. Advanced auto fill:
for each zone Z for each number N if there is no N in Z and there is only one cell C in Z where N can be put fill C with N
4. Advanced suggestions removal:
for each cell C for each zone Z that contains C for each cell D in Z if there are exactly X cells in Z where X is the number of D's possibilities remove all D's possibilities from all other N*N-X cells' possibilities in Z