Three mathematicians — Gary McGuire, Bastian Tugemann, and Gilles Civario — spent a year working on a sudoku puzzle. Well, it’s a bit more complicated than that. The essential question they sought to answer: what is the minimum number of clues one must be provided to solve a sudoku puzzle? Turns out that one must see 17 clues (out of a total of 81 squares on a sudoku board) to solve the puzzle uniquely. From their paper, here is the 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

If you aren’t familiar with sudoku…the puzzle solver is presented with a 9×9 grid, some of whose cells already contain a digit between 1 and 9. The puzzle solver must complete the grid by filling in the remaining cells such that each row, each column, and each 3×3 box contains all digits between 1 and 9 exactly once. It is always understood that any proper (valid) sudoku puzzle must have only one completion. In other words, there is only one solution, only one correct answer.

And hence the interest in the minimum number of clues problem: What is the smallest number of clues that can possibly be given such that a sudoku puzzle still has only one solution?

There are exactly 6,670,903,752,021,072,936,960 possible solutions to Sudoku (about 6.7 * 10^21) . That’s far more than can be checked in a reasonable period of time. But due to various symmetry arguments (also known as equivalency transformations), many grids are identical, which reduces the numbers of grids to be checked to 5,472,730,538.

I am always on the lookout of mathematicians doing fun things, so if I find any papers on solving other types of games or puzzles, I will post the results here.

###

(via Technology Review)