I am sure everyone has seen Sudoku puzzles: it was quite a fad a few years ago. The puzzle begins with an 9×9 grid, partially filled with numbers from 1 to 9 (the “givens”). The goal is to complete the grid so that that every row, column, and the nine 3×3 subgrids in the corners and center all contain the numbers 1 through 9 with no missing and none repeated. There was a time in my life where I loved Sudoku puzzles. I had to give them up when I started to dream solely in Sudoku.
The puzzles can be difficult or easy depending on straightforward it is to deduce missing values. A grid with many givens tends to be very easy, since there are few choices for missing values (though there can be hard problems with many givens and easy ones with few). If too few values are filled in, however, the solution may not be unique, and it is a fundamental precept of puzzle-creators that the solution must be unique. So, how many givens are needed to ensure uniqueness? It has been known for a long time that there exist problems with 17 givens that lead to unique solutions.
Gary McGuire, Bastian Tugemann, Gilles Civario of University College Dublin proved this result is the best possible: there is no problem with 16 givens with a unique solution. They do this in a very interesting way: they did an exhaustive search. Given the number of possible solutions, it is surprising that exhaustive search works, but they were clever in organizing the search, and had access to a ridiculous amount of computational power. This combination let them run through all the choices. They didn’t find a 16, therefore there is not a sixteen!
Fascinating work, and a sign of how fast computing can change how we look at research problems. Technology Review has an article on this; the technical report is at arXiv.
Interesting result! Even more interesting would be if we could extract some kind of understanding of why this number is the magic number.. If there is something to be understood.