SuDoku

Version 1.0 (16-Mar-05)

What is it?

SuDoku is a solver for the Su Doku puzzles which appear daily in the T2 supplement to the Times (and elsewere, I'm sure). The puzzle consists of a 9x9 grid (subdivided into 9 3x3 gridlets); at the beginning, some cells contain numbers from 1 to 9, others are blank. The goal is to fill each cell with a number from 1 to 9, such that:

Each row contains the numbers 1 to 9
Each column contains the numbers 1 to 9
Each gridlet contains the numbers 1 to 9

This means that once a number has been used once in a row/column/gridlet, it cannot be used again. The puzzle can get very difficult for a human, but its logical nature makes it ideal for a computer solver.

How do I use it?

Running SuDoku will open a window containing a grid equivalent to that in the paper. Enter the numbers as they appear in the paper; if you want to save a grid once you have entered it, the menu lets you (likewise you can load a grid by dragging it to the window). Pressing Clear will clear the grid (as you might expect). Pressing Go!, on the other hand, will make the computer attempt to solve the puzzle. Fairly straightforward, really. If the computer finds more than one solution to a puzzle, it will alert you to the fact in the status bar at the bottom of the window (it only looks for 3 solutions then stops, to avoid time-wasting).

Pressing 'Hint' makes things a little more interesting: the program switches to 'Hint mode'. First, it works out the puzzle but doesn't show you the answer. From then on until you next press Clear or Go! (which still work as expected), you can do two things:

Adjust-click on any square to display the correct number for that square (clicking again hides it):
Fill in some squares and press 'Check' to have them compared to the computer's stored answer; if they match it will display 'Correct' in its status bar, if not it will display 'Incorrect' and highlight the incorrect answers in red.

Note that by its very nature (it compares your answers to a stored, pre-calculated grid) this system may not work if a) there are two possible answers to a puzzle, or b) you alter any of the initial 'given' numbers used to work out the puzzle.

How does it work?

The computer keeps a track of what numbers are allowed in each square; if at any point only one is allowed, it will put it in and rescan. If not, it makes a choice, tries it out, and if it fails (i.e. leads to a grid which breaks the rules), backtracks and tries a different choice. The 'levels' display shows how many levels of choices the system has to make to solve the current puzzle. If you're interested, look at the source-code (although it is a bit messy in places). The way the system works means it is actually possible to put a solution to a blank grid!

Who wrote it?

Mark Hutchinson. Look at my website for more wonderful, astonishing and gravity-defying programs: http://hutchies.iconbar.com