Java Sudoku Solver and Wikipedia Exaggeration

9 01 2009

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.

sodokuSolving 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.

Advertisements

Actions

Information

4 responses

20 03 2009
Project Euler « PherricOxide’s Technology Blog

[…] Most of my solutions are very hacked together and brute force, but they work well enough. I’ve been focusing more on solving each problem quickly and correctly, rather than coming up with the best code, resulting in a lot of code that falls into the burn after compiling catagory. I’ve been doing most of them in C, but some I’ve resorted to Java and other languages to make things easier, or to reuse code (there’s one challenge to write a program to solve Su Doku puzzles, something I wrote in Java and mentioned here). […]

27 01 2010
isyldur

i have written C++ sudoku solvers ( one brute force, the other choosing the empty square with the least possible choices)

the 1st one solved that grid in 259 sec, the 2nd one in 10 sec (my programs dont stop at the first solution found,they eplore the entire tree for multiple solutions)

now i’m only a beginner and i’m sure there are improvements to my programs,but these time were made on my G4 1,42 GHz mac mini. I guess they DID exagerate, or these testers really cant make an efficient program.

my source code can be found in this forum link ( sorry the forum and any comment in my source are in french)

http://www.developpez.net/forums/d862071/c-cpp/cpp/programme-cpp-fonctionne-mac-pc-ubuntu/

10 06 2010
Santosh B

You can send me the simple java codes without the GUI.

10 08 2010
Kevin Coulombe

Here’s an optimized implementation and the explanation for everything. It takes under 3 ms on my netbook for any problem I tried.

http://www.byteauthor.com/2010/08/sudoku-solver/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: