There is no 16-clue puzzle

Everything about Sudoku that doesn't fit in one of the other sections

There is no 16-clue puzzle

Postby moschopulus2 » Sun Jan 01, 2012 12:53 pm

I would like to announce that we have solved the sudoku minimum number of clues problem.

We have verified by exhaustive computer search that a 16-clue puzzle does not exist.

For further details see the article and source code at
http://www.math.ie/checker.html

A big thank you to all contributors on this forum, where many of the ideas came from.

Happy New Year!

Gary McGuire
moschopulus2
 
Posts: 3
Joined: 02 December 2011

Re: There is no 16-clue puzzle

Postby dobrichev » Sun Jan 01, 2012 5:33 pm

Great job!

Finally we got the answer in yes/no form.

On first sight I have 2 questions
1) Did you ever experiment processing grids in pairs, where the pair differ in only one unavoidable set, say the largest from the clique?
2) What is the difference in efficiency of the code between pure C++ compiler generated code and assembly code? Are the assembler instructions mixture of code generated from different compilers, selecting the best piece from each of the compilers?

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Postby eleven » Mon Jan 02, 2012 12:07 am

<deleted>
Last edited by eleven on Tue Jan 03, 2012 7:06 pm, edited 2 times in total.
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: There is no 16-clue puzzle

Postby moschopulus2 » Mon Jan 02, 2012 11:28 am

dobrichev wrote:Great job!


Thank you!

dobrichev wrote:On first sight I have 2 questions
1) Did you ever experiment processing grids in pairs, where the pair differ in only one unavoidable set, say the largest from the clique?


No. What we did investigate is processing multiple grids at a time which are neighbours in the catalogue, i.e., grids that appear next to each other in lexicographic order. For the enumeration of hitting sets, we used only those unavoidable sets that were common to both grids.

This seemed to work well for some of the grids occuring early in the catalogue, but not at all for grids occurring later, so we did not pursue that idea.

dobrichev wrote:2) What is the difference in efficiency of the code between pure C++ compiler generated code and assembly code?


I can't answer that question exactly now, because we never tried using SSE in the C++ version of checker.

In GridChecker, you use the intrinsics the C++ compiler provides in order to execute SSE instructions. But that is something we never actually tried - whenever we used SSE, it was always in the assembly code only. In fact, part of the reason for switching to assembly code was that we felt it would allow us to get the most out of SSE.

dobrichev wrote:Are the assembler instructions mixture of code generated from different compilers, selecting the best piece from each of the compilers?


All of the assembly code is handwritten.
moschopulus2
 
Posts: 3
Joined: 02 December 2011

Postby eleven » Mon Jan 02, 2012 1:22 pm

<deleted>
Last edited by eleven on Tue Jan 03, 2012 7:07 pm, edited 1 time in total.
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: There is no 16-clue puzzle

Postby coloin » Mon Jan 02, 2012 4:59 pm

Indeed very well done. We can all rest now !
It means you checked approx 200 solution grids per second ! Amazing !

Maybe the 17 check might just elude us for a bit longer ..... !

Did we ever understand why some solution grids wth similar MCN took significantly longer ?

MD also did work which catalogued the min clues for the 3 horizontal bands and 3 vertical bands [2-6 clues]
Simplistically if a solution gtid was a {6,6,5./x,x,x.} it cant have a 16.
Effectivly the six regions are 27 clue "higher degree unavoidable sets"
I see this may well indirectly have been employed.

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: There is no 16-clue puzzle

Postby Red Ed » Mon Jan 02, 2012 6:23 pm

Excellent! Well played, Gary + team, and Happy New Year 8-)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: There is no 16-clue puzzle

Postby moschopulus2 » Tue Jan 03, 2012 10:22 pm

Red Ed wrote:Excellent! Well played, Gary + team, and Happy New Year 8-)


Thanks Ed.

By the way, you sent me some blueprints of unavoidable sets years ago. We wrote a tool that enumerates all blueprints of a given size. We confirmed that for size up to and including 11, you had ALL blueprints. You probably have all the blueprints for size 12 also, but we haven't got around to running the programme yet to confirm that (we didn't need to).
moschopulus2
 
Posts: 3
Joined: 02 December 2011

Re: There is no 16-clue puzzle

Postby gsf » Mon Jan 09, 2012 3:04 pm

great achievement Gary & team
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: There is no 16-clue puzzle

Postby dyitto » Mon Mar 26, 2012 11:30 am

What's the status of independent check/review?
evert on the crashed forum
User avatar
dyitto
 
Posts: 118
Joined: 22 May 2010
Location: Amsterdam

Re: There is no 16-clue puzzle

Postby dobrichev » Tue Jul 31, 2012 10:22 pm

dyitto wrote:What's the status of independent check/review?


I spent several days digging in the published code and found it is no easy to follow the machine instructions and undocumented data structures.
I found the authors left several redundant checks like validation of UA sets and comparison of the eventual puzzle's solution with the original solution grid (which actually never happened).
As an effect of the manual optimizations made, some of the offsets within the data structures have been replaced with constants, which makes the code highly compiler-specific. Also some registers are used across the function calls.
After few minor editions in the code I succeeded in compilation and the program respectfully answered "zero puzzles found" for the few test grids I ran, which means nothing by itself.
The only compiler warning was a missing emms instruction at the end of one inline assembly code block. This omission is unlikely to cause invalid processing results since only the time progress calculations are based on floating point arithmetics.

The same team has plans to extend the search to 17-clues, see http://garymcguire.files.wordpress.com/2012/06/sudoku_demo_isc.pdf.
I wish them success.

It would be curious if they discover some exotic 17-clue island with a valid 16-clue puzzle within.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: There is no 16-clue puzzle

Postby Ton Smeets » Thu Dec 13, 2012 5:53 am

A 16 clue puzzle would only be possible if there was no redundancy between the 27 Sudoku constraints (row, clumn, block). But as shown by Bart Demoen and Maria Garcia de la Banda (Theory and Practice of Logic Progamming, July 2012), a maximum of six constraints is redundant. As a result a 17th clue seems to be necessary. Obviously one extra clue is sufficient to solve the redundancy problem. But why just one? This is still a hard question to answer, or otherwise "why not two extra clues?".
Ton Smeets
 
Posts: 4
Joined: 11 December 2012

Re: There is no 16-clue puzzle

Postby Serg » Thu Dec 13, 2012 5:22 pm

Hi, Ton Smeets!
Welcome to this forum!
Thank you for the link to interesting paper (see http://www.cs.nmsu.edu/ALP/tplp-our-journal/tplp-accepted-papers/2012-05/). I studied this article with great interest.
Ton Smeets wrote:A 16 clue puzzle would only be possible if there was no redundancy between the 27 Sudoku constraints (row, clumn, block).

Why? Please, clarify your statement.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: There is no 16-clue puzzle

Postby eleven » Fri Dec 14, 2012 10:17 pm

Yes, the paper looks nice, thanks, hope i can find the time soon to read it carefully.
Once i had to use Prolog in a project. The first thing i tried to implement was a "for" or "while" loop, not easy :) (all is recursive backtracking there).

I also can't see, why a 16 clue could not exist with redundant constraints.
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: There is no 16-clue puzzle

Postby coloin » Mon Dec 17, 2012 11:15 pm

Well i cant quite see the proof.

However maybe the theory can be extended to show the minimal clues for a full box9-plus-x
Code: Select all
+---+---+---+
|...|...|.18|
|6..|...|..7|
|.4.|...|...|
+---+---+---+
|...|123|...|
|1..|456|...|
|...|789|3..|
+---+---+---+
|..8|.1.|...|
|.2.|...|4..|
|...|...|.6.|
+---+---+---+ box9plus12

or other patterns
C
coloin
 
Posts: 1629
Joined: 05 May 2005

Next

Return to General