Solver App for Android and iPhone
Strategies for Number Puzzles of all kinds
Print Version Page Index
Solvers
Puzzles
Latest Apps
Str8ts
Other

There is no 16-Clue Sudoku



A recent paper by Gary McGuire, Bastian Tugemann, Gilles Civario "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem" (PDF) shows a new and interesting approach to the problem of the minimum numbers of clues to a normal Sudoku. This has been highlighted in a number of news outlets and scientifc journals (eg Nature). (Note: Nature's article tries to reproduce the 17 Clue example from the paper but they get the 43 in the wrong place, giving an invalid puzzle with 9734 solutions. The Sudoku in the paper is correct).

It has been conjectured for some time that 17 clues is the minimum number of necessary clues to make a single solution Sudoku puzzle. There are about 50,000 such puzzles collected from various sources out and about on the Internet. One such set I use for calibrating and testing.

'Proof' though needs to be qualified. This is not a mathematical proof as such but a brute force computer search through the number space within the Sudoku set, and the author admits that a mathematical proof is still be discovered. What is interesting about the paper is the algorithm to search the space. To search through all possible combinations would take an impractical amount of time. The author identifies the Unavoidable Sets as the key to reducing the search space. These are sets of four cells which potentially could be interchanged to make two solutions - and therefore, minimally, one of those cells must be a clue.

Even with this insight, it is still a challenging algorithm to run. First you must obtain (or generate) all possible unique filled-in Sudoku boards, of which there are 5,472,730,538. The algorithm must also take into account higher order Avoidable Sets (with nine numbers instead of 4). So it is understandable that the computing time was still considerable.

Nevertheless, to get a result in a practical time is an achievement. I have been running some tests on my Solution Count program which shows how the time to check a puzzle using a brute force method becomes exponential with the reduction in the number of clues. Anyone familiar with the solver will know this feature. 17 clue puzzles take on average 6 seconds - although the exact orientation and placement of numbers can make this vary from 0.5 seconds to 30 seconds. Given 22 clues the average time is 0.037 seconds and becomes millisecond or less with 25 clues or more. So a practical search of this space without using a trick like Avoidable Sets is impossible.


Some comments on the Nature page (comments down at the time of writing) assert that the number of clues determines the grade. This is not true - if you using logical strategies for grades as I do. It is possible to have very easy 17 clue puzzles and 'extreme' 30 clue ones. The only effect of clue density it to increase the number of operations required to solve (which is one mildly additive heuristic in my grading).

Overall, an exciting paper.

Andrew Stuart


Comments

Your Name/Handle

Email Address - required for confirmation (it will not be displayed here)

Your comment or question

Please enter the
letters you see:
arrow		Enter these letters Remember me


Please keep your comments relevant to this article.
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. Line breaks and paragraphs are automatically converted - no need to use <p> or <br> tags.
Comments Talk

Saturday 22-Dec-2012

... by: bartlm

As only a very recent sudoku addict I was quite surprised that the mathematics had not been fully worked out for what seems a not too complicated combinatorial problem. Clearly it has inner complexity.
Where I would take issue with your comment on the 16 clue paper is that it is not a mathematical proof. An exhaustive search may not be elegant but if the search results are incontrovertible and anyone can check them, then the conjecture has been proven. I seem to remember that the four colour theorem was proved in this way about 25 years ago.
Andrew Stuart writes:

I too remember reading about the four color map solution. Perhaps I'm thinking too much within my own skillset which is programming rather than mathematics where I'm much weaker. But I thought I understood the difference between a mathematical proof and a mechanical one. The conjecture here may be expressed mathematically and the mechanical proof sound, but in order to qualify as a mathematical description it shouldn't really include every instance of the object it wishes describe (ie it would be nice if it was much smaller). That's the whole point of maths - it’s a shortcut to the truth. We/They are lucky the Sudoku problem is finite otherwise a mechanical proof would always remain out of reach, in contrast to, say, the Pythagorean theorem where we can't examine every triangle. I think they have used some very attractive maths/logic to reduce the search space and get to the proof in a reasonable time but I wanted to make a layman distinction in this area of proof.
Have a great Christmas

Article created on 9-January-2012. Views: 44426
This page was last modified on 12-February-2012.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles Inc, 2012