Saturday, January 07, 2012

Sudoku: uniqueness requires 17 or more hints

Sudoku has appeared on this blog in March 2007 when a student at Harvard – where I was working – won the Sudoku world title in Prague and was congratulated by Czech president Klaus who is a passionate Sudoku solver himself. (Interestingly, I met President Klaus in Washington D.C. during the same month.) In this entry, we will be more technical. We will talk about a preprint
There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem

Physics arXiv blog (review of the preprint)
Using brute computer force, Gary McGuire et al. (Dublin) showed that all Sudoku problems with at most 16 hints have at least two (or zero) solutions. First, let me explain what is Sudoku.




Sudoku is a problem where you have to fill it numbers 1-9 into a 9-by-9 square in such a way that each digit from the list 1-9 occurs exactly once in every row, every column, and each of the nine 3-by-3 blocks. Here is the first problem that I optimized for climate alarmists and string theory critics:



It has 80 hints. But in the middle, there is a missing figure, the white square. A climate alarmist will refuse to solve the puzzle because he would have to breath and produce extra CO2 emissions; meanwhile, his fart will surpass the Arctic degassing of methane by two orders of magnitude (Real Climate shows that such an increase of methane would still be safe).

The string theory critic will complain for 10 years that the table above is not even wrong and then he finally gets the idea. He looks at the rows or columns or the middle block and using any of the three methods, he will figure out that "7" is missing in the white square.

Brighter and/or more experienced Sudoku solvers are able to complete Sudoku boards with a far lower number of hints than 80. In fact, it's been believed – and now proved by a computer program – that the minimum number of hints that allows a unique solution is 17. An example is here:



It's surely tough for inexperienced solvers such as myself. The easier Sudoku may be solved if you look at the most promising rows, columns, or blocks i.e. those with the highest number of hints. The hints leave a limited number of possibilities for the remaining empty squares. You try to look at all these remaining squares and find those that are uniquely determined by the Pauli exclusion principle applied to their row, column, as well as block at the same moment. You repeat this reasoning many times: it should be getting easier in average as the board becomes more full.

This simplest strategy will fail for really tough Sudoku such as one above. For those, you have to think think about the future moves, ahead of time, and try various possibilities: you won't be able to add the numbers one-by-one just by thinking about them locally, I guess.

Now, various Sudoku problems are clearly equivalent to each other. If we permute the rows 1-3 (6 possibilities) or 4-6 or 7-9, we will get another problem (or another solved problem). The same comment applies to columns 1-3, 4-6, 7-9. We may also permute the blocks of rows 1-3, 4-6, 7-9 with each other; the same comment applies to columns. And we may permute the digits 1-9. If these operations were always independent, they would produce
\[ (3!)^{3+3+1+1} \times 9! \sim 6 \times 10^{11} \] i.e. about half a trillion equivalent solutions to a given one (which is counted). That's a rather large equivalence class. However, the number of wrong ways to fill in the digits 1-9 is much higher still. Note that
\[ 9^{81} \sim 1.97 \times 10^{77}. \] There are various large numbers included in such considerations. The actual number of solved Sudoku boards is 6,670,903,752,021,072,936,960 (seven billions of trillions) but they fall into 5,472,730,538 equivalence classes (five billions). They literally went through these 5 billion solved Sudoku boards and looked for one that could be uniquely specified by 16 hints, and there weren't any. (This trivially implies that fewer than 16 hints is also too few, a point that the famous Physics arXiv blog initially found hard to understand.)

I encourage the TRF readers to find a simple proof that 16 hints can't be enough for uniqueness. You may also play Sudoku in Flash.

Sudoku was originally invented by Czech king Charles IV in 1348, under the name "Sud do doku" ("A barrel for a docking facility"), and it became a hit again in Japan of 2005.

2 comments:

  1. One frequently occurring requirement for a sudoku is that the hints are located symmetrically in respect to the center cell (the origin, if you wish). The example above does not fulfill this requirement. For an odd number of hints, like here, obviously the center cell has to be one of the hints.

    ReplyDelete
  2. I'm surprised this wasn't solved some while ago by manipulating factorials with pencil and paper, I wish I could gin up some enthusiasm, I can't.

    ReplyDelete