Sudoku puzzles must have at least 17 clues to have a valid solution

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/