27.6.07

MARKING OFF. Work on this.


Last year at about this time, I promised some details on a Sudoko-generating algorithm. This puzzle is the third application of the algorithm. The fourth estate has discovered mathematicians applying some serious number theory to the Sudoko, including others working on algorithms.

Many have written their own Sudoku puzzle generators and solvers. Jonathan Kane, a professor of mathematics and computer science at the University of Wisconsin-Whitewater, wrote a program to generate and solve puzzles of one of six degrees of difficulty. His program uses logic rules and guessing to create a puzzle and then rates the puzzle based on the difficulty of the logic rules needed to solve it and on the number of guesses required.

Laura Taalman, associate professor of mathematics at James Madison University in Harrisonburg, Va., has written a computer program with her husband, Phil Riley, to generate Sudoku puzzles. Their puzzles often incorporate some variation in the grid as well as symmetry of the clues. To rate a puzzle, the computer plays the puzzle a thousand times in different ways, and then a difficulty rating is assigned based on the average time it takes the computer to solve the puzzle.

My own puzzle-generating algorithm is much simpler. In working on it, however, I've begun to wonder whether there aren't puzzles out there that are simply mappings of other puzzles. That is, given a pattern of clues and a pattern of numbers, aren't there other puzzles with the same pattern of clues that simply change the values of the numbers.

I'm also intrigued by this.

They still aren't sure, though, about the minimum number of clues needed to guarantee a puzzle will have only one solution. More than 40,000 mathematically distinct Sudoku puzzles with 17 initial clues have been found, but not a single one with 16 or fewer clues is known to exist.

Gordon Royle, associate professor of computer science at the University of Western Australia, has been collecting these 17-clue puzzles since 2005. Royle and other Sudoku enthusiasts have written computer programs to generate Sudoku puzzles in search of the elusive 16-clue puzzle that has just one solution.

Just for fun, I'm tempted to create a 16-clue puzzle and invite readers to find "cooks" (chess-problem language for more than one solution) to it.

No comments: