Mathematicians use computer to solve minimum Sudoku solution problem

Sudoku, for the uninitiated, is a puzzle whereby a square is created with 9x9 rows and columns of boxes to be filled in with numbers (1 through 9). The puzzle is further divided into nine 3x3 sections. The trick to solving the puzzle is that each row and column cannot have repeating numbers and neither can any of the 3x3 sections. Also, when a puzzle is created, a certain number of the boxes are prefilled, creating in essence, a unique puzzle each time. Thus, to solve the puzzle, all a person has to do is figure out how to fill in the rest of the boxes.

The thing about Sudoku puzzles though, is that those that make them can pre-fill as many boxes as they choose, the more clues they give, generally, the easier the puzzle will be to solve. Thus, creators who want to make their puzzles as hard as possible want to fill in the fewest possible clues that will still allow for a unique single solution.

To prove that 17 is the magic number, Gary McGuire and colleagues at University College, Dublin, took the brute force approach. After all with every Sudoku puzzle there is a solution, to find it, all a computer would have to do is try every possible scenario for every possible configuration. Unfortunately, that approach would take too long, so the team had to figure out a way to trim down the number of possibilities they’d have to check for.

Throwing out grids that are equivalent helps, that reduces the number of tests dramatically. But that’s still not enough, so the team wrote a software routine that tests to see if certain subsets of the puzzle are equivalent to others, which would mean not having to test for the others if the first are found. This reduced the amount of testing as well. But even so, it took almost all of a full year of computing to test all of the possible scenarios.

But when the program stopped, the researchers had their answer. To create a Sudoku puzzle that is unique, you have to give at least 17 clues.

More information: There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, arXiv:1201.0749v1 [cs.DS] http://arxiv.org/abs/1201.0749

Abstract
We apply our new hitting set enumeration algorithm to solve the sudoku minimum number of clues problem, which is the following question: What is the smallest number of clues (givens) that a sudoku puzzle may have? It was conjectured that the answer is 17. We have performed an exhaustive search for a 16-clue sudoku puzzle, and we did not find one, thereby proving that the answer is indeed 17. This article describes our method and the actual search.
The hitting set problem is computationally hard; it is one of Karp's twenty-one classic NP-complete problems. We have designed a new algorithm that allows us to efficiently enumerate hitting sets of a suitable size. Hitting set problems have applications in many areas of science, such as bioinformatics and software testing.

via ArxivBlog

© 2011 PhysOrg.com