Search of 17 clues puzzles in a solution grid
CONTEXT and General overview
The proof that no Sudoku with 16 clues can be produced has been published in august 2013 by Gary McGuire .
The corresponding article should still be available at the following location
That process was very costly in computer resources and as of to-day, it seemed impossible to extend it to a proof that all 17 clues puzzles are known (or to produce missing ones.)
However, many pieces of that process have a wider scope. The reader should have downloaded it locally.
Several other ways to achieve the task have been tested, but nothing showed up having the required performance to make a full scan of the 17 clues field until recently when “blue”, an active member of the “http://forum.enjoysudoku.com” came with a completely different approach and published impressive partial results.
At the time I open this thread, blue did not publish his code, but he gave many indications in public and in private on the new process. We lost the contact with blue in March 2017.
Meantime, I worked on blue’s findings, trying to achieve something similar. I have now in hands a process applied to one of the 2 majors cases described by blue, and this is what I intend to share.
I’ll try to express the process “as I understood it in the messages delivered by blue” and to describe what I did .
I start with a short description of the overall process. Each chapter will be developed later
As we will see, blue’s process works on solution grids. The entry for an elementary process is an ED band 1+2 plus the relevant set of bands3.
The search itself is divided in 2 parts (X is the set of clues giving a valid first band Y the set of clues giving a valid second band)
“part 1” finding, basically all groups of clues ‘XY’ in bands 1+2 of a given size leading to a valid band 1+2 .
“part 2” searching a 17 in each band 3 of the set for the found XY.
“part1” can have to process billions of possible XY. The process basis is relatively simple, Optimization of the search can make it tougher to follow. Chapters A to G will give a quick overview ignoring the optimization in part 1
The process is also split in 2 pass (for blue) or 3 pass (for me) differing by the number of clues in band 3.
The general overview is done in chapters A to G.
Chapter H is the key chapter for the part 1 re visiting the process 1 with all optimization issues.
(click on the link to go to the corresponding page and click on “back” on top to come back here)
The headings will be
A Solving Strategy
B Finding solutions for bands 1+2
C Unavoidable Sets (UAs) filters for bands 1+2
D Stack Filters in 656 mode and final XY validation
E Band 3 collection , “first filter” and cache isue
F Bands 3 gangster Unavoidable sets (GUAs)
G band 3 search strategy
H Process optimization
H1 timing considerations
H1 sorting entries
H2 Optimizing cache
H3 Adding a layer 2cells X;2 cells Y
I entries (bands1+2) and band3 generation
J Compilation and compatibility constraints
K bands expansion
L Uas generation
M Gangster UAs generation
N 2X2Y loop
O1 Chunk process, the critical code
O .. End of part 1, valid band 1+2 and Start of “part 2”
Page 9 P Band 3 process “part 2”
P Band 3 process “part 2” sub critical process
Q Brute force use
================ pass 1 puzzles with a band/ stack having >= 7 clues
Searching 16 clues puzzles