Sudoku Solver

The above is a Sudoku solver I wrote in Java a while back. Here it is running in the browser. The Java has been converted to in-browser Javascript by Google Web Toolkit.

Please feel free to type in the hardest Sudokus you can find anywhere, and let me know if it can solve them, I haven’t found any it can’t yet.

I assume the in-page Javascript will not work in RSS readers, email notifications, etc. If that’s the case, click here to get to the original Sudoku solver page on my blog.

The algorithm works by backtracking, i.e. simply going through all squares from top-left to bottom-right, and finding the set of “candidate numbers” for that square (i.e. which numbers are not already used on that row, column or 3×3 block). The first candidate number is “applied” by placed it into the square, and the algorithm moves to the next square. If there is a square where the set of candidate numbers is empty (i.e. no number would work, given the candidates applied in previous squares) then the system returns to the previous square and tries the next candidate for that square. Once the system has gone “beyond” the bottom-right square, then the set of applied candidates consitutes a solution. However, backtracking continues, if the system reaches beyond the bottom-right square again, then the previously found solution
was not unique, and the algorithm terminates. Once the system has backtracked back to the start, if a single solution was found then it is a “unique solution” (success case), otherwise if there are no solutions then the Sudoku is unsolvable.

By the way, Internet Explorer really isn’t that fast; I appreciate that is well-known to anyone who’s ever read Google Chrome marketing material! But the Sudoku here takes 708ms to solve on IE8, 334ms on Firefox 3.6, about 100ms on Safari 4 and Opera 10, and 49ms on Chrome 4, on this 2.3GHz/core Intel Windows Vista computer.

Update: Alas there were Sudokus which took too long for the original synchronous approach (i.e. user clicks, do calculation, update the screen with the results). So now, in the case the calculation takes too long, a “worker” is spawned, which does the calculation, and the spinner is displayed in that case.

See the source on github.

4 Responses to “Sudoku Solver”

  1. Your wife Says:

    Ha! I just typed in the last sudoku in my sudoku magazine (presumably the most difficult one), pressed the “calculate” button. But it shows “This is not a reasonable sudoku” which can’t be true, because I’m confident that I can solve it. ;)

  2. adrian Says:

    @ My wife ;-) … OK should be working now …

  3. Your wife Says:

    Wow! It really works! Well done hubby! :)

  4. Justin Says:

    That’s cool, I like.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

For inserting HTML or XML please remember to use &lt; instead of <