Search of 17 clues puzzles in a solution grid

http://pagesperso-orange.fr/gpenet/P17/p17.htm

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

 

http://arxiv.org/pdf/1201.0749.pdf

 

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.

 

See  http://forum.enjoysudoku.com/bands-and-low-clue-puzzles-t30218-120.html

 

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 .

 

Process SUMMARY

 

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

Overview page 2

           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)

Overview page 3

           G band 3 search strategy

Overview page 4

           H Process optimization

                      H1 timing considerations

                      H1 sorting entries

                      H2 Optimizing cache

                      H3 Adding a layer 2cells X;2 cells Y

Page 5

           I entries  (bands1+2) and band3  generation

           J Compilation and compatibility constraints

 

Page 6

           K bands expansion

           L Uas generation

           M Gangster UAs generation

 

Page 7

           N 2X2Y loop

 

Page 8 end of part 1

        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”

 

Page 10      

           P Band 3 process “part 2” sub critical process

           Q Brute force use

 

 

================ pass 1 puzzles with a band/ stack having >= 7 clues

 

Page 11

           General overview

           Searching 16 clues puzzles