Feeling like programming, I decided to work on another puzzle solver other than my Rubik’s Cube program. This time I decided to tackle Sodoku in Java instead. I used two stacks and a pure brute force method of solving. First off I made the grid with a simple 9×9 array, filled it with some test numbers. I used 0’s for unkowns. I created a pair object to store (x,y) values into the stacks, and then made two stacks. The program located all the unknowns, adds them as pairs to the first stack, and gets to work checking for legal values when told to solve. It starts at the first number, checks to see if it can be a 1, 2, 3, etc. When found it moves on. Once it reaches a number it can’t find, it goes back one and increases that number to the next legal one. It does this until the main stack is empty.
Most puzzles it can solve in less than a second, even the ones rated “evil”, but I decided to try and find hard ones for it. On Wikipedia I found the “Near worst case sudoku puzzle for brute force solver”, located below.
Solving this puzzle by brute-force requires a large number of iterations because it has a low number of clues (17), the top row has no clues at all, and the solution has “987654321” as its first row. Thus a brute-force solver will spend an enormous amount of time “counting” upward before it arrives at the final grid which satisfies the puzzle. If one iteration is defined as one attempt to place one value in one cell, then this puzzles requires 641,580,843 iterations to solve. These iterations do not include the work involved at each step to learn if each digit entered is valid or not (required for every iteration). Based on the specific construction of the computer code, programmers have found the solution time for this puzzle to be between 30 and 45 minutes with a computer processor running at 3 GHz.
“Perfect!” I thought to myself, and plugged it in, thinking it was time to go get a cup of coffee and read my latest Asimov novel for 30 minutes. However, before I even look away, my results pop up.
Solved puzzle below
9 8 7 |6 5 4 |3 2 1 |
2 4 6 |1 7 3 |9 8 5 |
3 5 1 |9 2 8 |7 4 6 |
1 2 8 |5 3 7 |6 9 4 |
6 3 4 |8 9 2 |1 5 7 |
7 9 5 |4 6 1 |8 3 2 |
5 1 9 |2 8 6 |4 7 3 |
4 7 2 |3 1 9 |5 6 8 |
8 6 3 |7 4 5 |2 1 9 |
Elapsed time in milliseconds: 134015
740,190,074 values were tested
Wait, it solved it in just over 2 minutes? If for some reason I got an answer that less than 640,000,000 iterations were tested, I would start wondering how it solved it differently, but I had nearly 100 million MORE iterations than the Wikipedia article said was needed, and I still solved it much faster, with only a 1.4ghz Intel Core 2 Duo.
Apparently some Sodoku fans like to exaggerate about how hard their puzzles really are… Either that, or they really sucked at writing the code to check if a value is legal.
Note: I’ll throw up a link to my solver once I get a GUI together and put up an applet.