November 28, 2008

Sudoku Help

When you get stuck on a Sudoku, you want a little hint not a whole solution - you want Dave's Sudoku Help Page.

The tool is also handy for analyzing and building Sudoku puzzles by hand.

Set up the puzzle by clicking in the grid, or just use the arrow keys and type the numbers in. The gadget won't let you enter an illegal number. (It will solve the board all the way to the end every time you click to make sure it is allowed.)

(Find the Sudoku Help Page here.)

Once the puzzle is set up, you can reveal the answer in any spot with another click - this is handy to figuring out where you have made a mistake.

As you fill in the puzzle, the squares are color-coded. Green means "come on, you can figure out this square." Yellow means "figure this out after the green squares." Blue means "if you need to guess, try guessing here."

It is all javascript. If you find it too slow, then you should be running Chrome.

The code is basically an exercise in depth-first search, but it uses one unusual technique. Usually depth-first search finds a sudoku solution or proves impossibility after just a few dozen backtracks. But since a depth-first search that starts off badly within an illegal board can get "lost" in a twisty maze of hundreds of thousands of possibilities, we do an interesting thing to escape that sort of trap. We randomize the search traversal order, and if the exhaustive "turtle" depthfirst search takes too long, we start running short, randomly different "rabbit" depthfirst searches in parallel. This trickery frees us from being held hostage by an unlucky search order, and it is what lets us quickly enforce solvability on every click.

If you want to print out some puzzles, you can use my Printable Sudoku Generator.

Have fun. Posted by David at November 28, 2008 11:11 AM


Peter Norvig wrote a great solver in Python. Brendan Eich ported it to JavaScript. I ported it to C#/LINQ. All of these will be findable by your favorite search toolbar...

There will be no problem with it being slow. It's super fast.

Posted by: RichB at November 28, 2008 03:15 PM

Yah, here is my python attempt from 2006: - it's also fast, and it also generates puzzles, which is more subtle than just solving them.

It turns out that an interactive hinter is a harder problem than solving puzzles. The trouble occurs when trying to detect an illegal entry in an incomplete board. You never run into exponential problems solving correct and fully-constrained puzzles. But if you let the user fill in an incorrect square before fully filling out the rest of the board, a solver can run into search explosions convincing itself that the position is illegal.

Avoiding the exponential catastrophe in an underconstrained yet illegal board turns out to be an interesting problem.

Posted by: David at November 28, 2008 04:00 PM


Posted by: at November 21, 2009 02:16 PM

How can I have a completed puzzle and be told I
have three (letters)to go? Thanks.


Posted by: Elsa Byrnes at April 12, 2010 11:37 PM

Maybe a bug? If you think you see a bug, can you cut and paste the URL into a comment here, or email it to me?

Posted by: David at April 13, 2010 05:21 AM

no tips? =[

Posted by: langdon at September 14, 2010 11:59 PM
Post a comment

Remember personal info?