Friday, June 17, 2005

Sudoku

It was in today's LA Times and today's Science News online. Here's the Science News description.
The puzzle typically consists of a nine-by-nine grid. Some of the spaces contain numbers; most of the spaces are blank. Your goal is to fill in the blanks with digits from 1 to 9 so that each row, each column, and each of the nine three-by-three blocks making up the grid contains just one of each of the nine digits.
It started out in Japan. Then it moved to Great Britain. Now it's invading the US.

There are numerous websites devoted to Sudoku, including sites with solvers. Here's one written in JavaScript from Sudoko Solver by Logic, which runs right in your browser with no downloads. You can copy the example problem above into it's grid, and it will solve it.

This site even explains the solutions it finds. The overall strategy is to keep a list for each cell of the numbers that aren't eliminated by their appearance elsewhere in the same row, column, or block.

For example, number the columns from left to right 1 - 9, and label the rows from top to bottom, A - I. Cell A3 has the following possibilities: 2, 3, 8, and 9 since none of those number appear in row A or in column3 or in the top left block of 9 cells. But cell A3 is the only cell in column 3 that still has a 2 as a possible value. Therefore, that cell must be 2. By the same reasoning, F4 must also be 2. And the same is true for C6. Originally A6 could have had a 2, but the 2 in A3 eliminated the possibility of putting a 2 in A6. So the 2 in column 6 must be in C6. This entire problem can be solved this way.

In some problems, the solution is not so easy. There may be a point at which no value is determined. At that point, one must guess and proceed. If one ever gets stuck, then one must backtrack and try a different value. Because the problem may require this sort of backtracking, it has been shown (see the Science News story) that Sudoku is NP complete.

3 comments:

Anonymous said...

These are great. But they've been in the US a while. Pick up a puzzle book in the supermarket and they'll have a ton of these.

Russ Abbott said...

The best one I've found is http://www.paulspages.co.uk/sudoku/index.htm

Anonymous said...

Yes, the paulspages site is also good, although the background colour is a bit bright for this time of day in the UK!
The main advantages of SudokuPC are its use of 'point and click' as an alternative to keyboard entry, and its scrap pad. As a newcomer to Sudoku, I also found its help pages very useful.