[Turkmath:8119] sudoku

[Muhammed Uludag]

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

Mathematicians Solve Minimum Sudoku Problem
Sudoku fanatics have long claimed that the smallest number of starting
clues a puzzle can contain is 17. Now a year-long calculation proves there
are no 16-clue puzzles

KFC 01/06/2012

10 COMMENTS

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.



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.

-- 
--
A. M. Uludag
http://math.gsu.edu.tr/uludag/
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://yunus.listweb.bilkent.edu.tr/cgi-bin/mailman/private/turkmath/attachments/20120108/b19daf33/attachment.htm>