Sudoku Solver

This is a first preview of the next version, but it is not even half way finished yet. I started on it in August, so it will require several more months of hard work, but I wanted to release something before the end of the year. Latest additions: Solution Count and Minimal (see below). The source code is in src0.zip, but may be hard to follow before I have tidied it up, which is one of the next steps.

Version 4.5 (beta)   20 December 2009

Solution Count: This is the same function that Andrew Stuart has on his site. After entering an incomplete sudoku, it will find all solutions (full boards) with the given digits as a subset. Three options: (1) Brute force is the same method that Stuart uses. It works OK on average but the worst case is terrible. Even if there is only one or a few solutions, it may take hours on a PC. (Try this example with 17 clues and 20,791,091,016 recursions: ........1..5...........7..3.........1....2.......5.84...4.6.....56.....7.....1.32) (2) Singles solves as far a possible with naked and hidden singles, and then bifurcates with singles. This is the same as Ariadne's thread. Even though each recursion takes much longer, it is often faster than brute force, and is guaranteed to finish within a short time. (3) Pattern first solves with singles and then switches to doing one digit at a time. For each digit 1–9 all remaining patterns are calculated (from 46,656 possible), and then combined in a nested for-loop. This method is by far the fastest when there are many solutions (thousands or millions).

Minimal: Starting with a large set of givens, for instance 27 or 32, this function finds all minimal (irreducible) puzzles by removing as many clues as possible (with still only one solution). This is kind of the opposite of solution count, where you have too few givens. One use for this is to count (or rather estimate) the total number of minimal sudokus that can be derived from a full board. To do this I produce random sets with fixed size and count the number of minimals with different number of clues. Finding all minimals from 45 or 48 clues may take some days of computing time, so I only have preliminary results yet from one tested full board.
I struggled for several weeks to make the minimal function faster but only succeded partly. There are two major parts: finding possible minimals to test and solution count, or rather solution test, to see if there is one or more than one solution. In the latter case we stop after the second found solution and conclude that the latest removed clue must be put back. Normalized to a 1.0 GHz processor my first attempt took 32 minutes for this test case: 4..2..95.83..6.7...6.1....27.5..8.2....432........91686.....39124.5...8..1..7....   The second attempt took 20 min, the third attempt failed because the basic idea didn't hold, but I could use part of it in the fourth attempt, which took 7 min. This method stores all minimals in a big search tree, so I don't have to try again a set of clues that contains an already found minimal. In the fifth attempt I turned to the solution test part, storing found solutions so I don't have derive them over and over again. The time for the test case with 32 clues is now 2 minutes, which is alright. One problem remains though, the enormous memory requirement for the search tree, which is why I have set a limit of 33 clues. Java only allows for 64 MB. I will try again to reduce the search tree after I have done some other things, so be patient. With the improved solution test I could go back to the second attempt and reduce the time from 20 to 5 min. One benefit of this method is that the produced minimals are strictly numerically ordered.
In order to avoid printing thousands of minimals, it is possible to limit which ones are printed out. With initial settings only those with at most 22 or at least 30 clues are printed, but this can be changed at any time, even when runnning.

To interrupt "Solution Count" or "Minimal" press one of the buttons again.

Mats Anderbok 2009