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.

6 comments:

a future student 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.

Martindale said...

Introduced to Sudoku by your blog, I did some surfing and the best site I found was www.SudokuPC.com

The site provides a free 7-day evaluation for a neat Sudoku game with a super Scrap Pad facility. I'm hooked, try it too!

Blue said...

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

martindale 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.

tyrellbatty said...

I followed the advice from martindale. The downloadable version of the game is brilliant and really easy to use. I've been waiting for a pc version for ages.

Prettypen said...

I've had a look at various sites. I am new to sudoku and the most user-friendly I've found is the one at www.sudokupc.co.uk