How Many Possible Combinations to an Easy Sudoku Puzzle

Sudoku is a number puzzle consisting of a 9 x 9 grid in which some cells contain clues in the form of digits from 1 to 9. The solver's jobs is to fill in the remaining cells so that each row, column and 3×3 box in the grid contains all nine digits.

There's another unwritten rule: the puzzle must have only one solution. So grids cannot contain just a few starting clues.

It's easy to see why. A grid with 7 clues cannot have a unique answer because the two missing digits can always be interchanged in any solution. A similar argument explains why grids with fewer clues must also have multiple solutions.

But it's not so easy to see why a grid with 8 clues cannot have a unique solution, or indeed one with 9 or more clues.

That raises an interesting question for mathematicians: what is the minimum number of Sudoku clues that produces a unique answer?

This is a question that has hung heavy over the Sudoku community, not least because they think they know the answer. Sudoku fanatics have found numerous examples of grids with 17 clues that have a unique solution but they have never found one with 16 clues.

That suggests the minimum number is 17 but nobody has been able to prove that there isn't a 16-clue solution lurking somewhere in puzzle space.

Enter Gary McGuire and pals at University College Dublin. These guys have solved the problem using the tried and trusted mathematical technique of sheer brute force.

In essence these guys have examined every potential 16-clue solution for every possible Sudoku grid. "Our search turned up no proper 16-clue puzzles, but had one existed, then we would have found it," they say.

That's an impressive feat. There are exactly 6, 670, 903, 752, 021, 072, 936, 960 possible solutions to Sudoku (about 10^21) . That's far more than can be checked in a reasonable period of time.

But as luck would have it, it's not necessary to check them all. Various symmetry arguments prove that many of these grids are equivalent. This reduces the number that need to be checked to a mere 5, 472, 730, 538.

So McGuire and co wrote a program called Checker to check each one of these grids for a 16-clue solution.

But the process of checking a single grid is itself tricky. One way to do it is to examine every possible subset of 16 clues to see if any of them lead to a unique solution. The trouble is that there are some 10^16 subsets for each grid.

Once again, a little mathematics come in handy. McGuire and co used some clever reasoning to show that certain subsets are equivalent to many others and this dramatically reduces the number of subsets that need to be checked.

Nevertheless, the resulting calculation is still a monster. The Dublin team say it took 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December.

The whole exercise may sound like a bit of mathematical fun but this kind of problem solving has many important applications. McGuire and co say the problem of Sudoku grid checking is formally equivalent to problems in gene expression analysis and in computer network and software testing.

So the Dublin team's methods for speeding up the calculation will have a direct impact in these areas too.

But while the result is clearly impressive, the Minimum Sudoku Problem isn't entirely laid to rest.

This problem is crying out for an elegant proof that allows us to "see" why the minimum number must be 17; rather like the proof that there can be no unique solutions for 7 or fewer clues.

A big ask, I know, but surely one worth aiming for.

Ref: arxiv.org/abs/1201.0749: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem

Correction: this post was edited on the 6 January to reflect the argument that if an n-clue grid is uniquely solvable then adding a digit to make an n+1-clue grid must also be uniquely solvable. So if there are no uniquely solvable 16-clue grids, there cannot be any grids with fewer clues that are uniquely solvable. Thanks to RealMurph and abooij.

youngreatunat.blogspot.com

Source: https://www.technologyreview.com/2012/01/06/188520/mathematicians-solve-minimum-sudoku-problem/

Share this post