An Irish mathematician has used a complex algorithm and millions of
hours of supercomputing time to solve an important open problem in the
mathematics of Sudoku, the game popularized in Japan that involves
filling in a 9X9 grid of squares with the numbers 1–9 according to
certain rules.

Gary McGuire of University College Dublin shows in a proof posted online on 1 January that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given.

The rules of Sudoku require puzzlers to fill out a 9X9 grid with the
numbers 1–9 so that no digit is repeated within the same column, row, or
3X3 subgrid. The clues are the numbers that are filled in to begin
with, and enthusiasts have long observed that although there are some
puzzles with 17 clues, no one has been able to come up with a valid
16-clue puzzle. That led to the conjecture that 16-clue puzzles with
unique solutions simply do not exist.

A potential way to demonstrate that could be to check all possible
completed grids for every 16-clue puzzle, but that would take too much
computing time. So McGuire simplified the problem by designing a
'hitting-set algorithm'. The idea behind this was to search for what he
calls unavoidable sets, or arrangements of numbers within the completed
puzzle that are interchangeable and so could result in multiple
solutions. To prevent the unavoidable sets from causing multiple
solutions, the clues must overlap, or 'hit', the unavoidable sets. Once
the unavoidable sets are found, it is a much smaller—although still
non-trivial—computing task to show that no 16-clue puzzle can hit them
all.

Having spent two years testing the algorithm, McGuire and his team used
about 7 million CPU hours at the Irish Centre for High-End Computing in
Dublin, searching through possible grids with the hitting-set algorithm.
“The only realistic way to do it was the brute force approach,” says
Gordon Royle, a mathematician at the University of Western Australian in
Perth who had been working on the problem of counting 17 clue puzzles
using different algorithms. “It’s a challenging problem that inspires
people to push computing and mathematical techniques to the limit. It’s
like climbing the highest mountain.”

A consequence of the approach taken is that it will take some time for
others to get enough computing time to check the proof, says Laura
Taalman, a mathematician also at James Madison University, who
co-authored the book

*Taking Sudoku Seriously: The Math Behind the World’s Most Popular Pencil Puzzle*with Rosenhouse. Taalman notes that the book, which came out last week, is already outdated: it says that the problem remains open and that whoever solves it will be a “rock star.”Here is the official paper[PDF].

Source: http://www.nature.com/news/

Just read the PDF. It's pretty interesting.

ReplyDeleteHmmm, I never knew that, although I've been looking into making a sudoku game-maker in Java. that's gonna help with the solutioin set. After all my program has to be able to check if there's a valid solution :D.

ReplyDelete