The New Sudoku Players' Forum

[moschopulus2]

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

[dobrichev]

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

[eleven]

<deleted>

[moschopulus2]

Great job!

Thank you!

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.

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.

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.

[eleven]

<deleted>

[coloin]

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

[Red Ed]

Excellent! Well played, Gary + team, and Happy New Year

[moschopulus2]

Excellent! Well played, Gary + team, and Happy New Year

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).

[gsf]

great achievement Gary & team

[dyitto]

What's the status of independent check/review?

[dobrichev]

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.

[Ton Smeets]

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?".

[Serg]

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.

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

[eleven]

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.

[coloin]

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