davidbau.com

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