The New Sudoku Players' Forum

[champagne]

SKMPP2 SK_BFORCE SK_17P2A

I open this thread to tell more about several programs on which I am working
All of them are in the same repository here
and are sharing many files.

Currently, the repository can produce three programs

SK_BFORCE
SK_17P2A
SKMPP2

SK_BFORCE is the stand alone version of the brute force in use in other programs. The source is based on the code posted here
by user zhouyundong_2012. No copyright is specified.

This version uses a guess intensively focused on bi value cells. As far as I can see, it is significantly faster than my previous version.
I built a true stand alone version of this program in a specific repository for 2 reasons
a) to have a code easier to decipher and reuse by others
b) to have a code where some experimentation can be done
this code is described here
to avoid redundancy, this code will not be discussed here

SK_17P2A is one of the three programs needed to search 17 clues in the solution grids in the “as of blue” mode see here
The first program searching 17 clues sudokus with one band/stack having more than 6 clues was run last year and did not show new 17s.
The first version of the search of grids having a band distribution 566 or 656 (no stack >6 clues) is working, but still too slow in my opinion. The current program is a revised version of the former one with an attempt to halve the runtime.

One key issue in the search of 17 clues puzzles “as of blue” is the unavoidable sets generation. I learned from mladen Dobrichev several years ago how to do that using the brute force. A special chapter will describe all the ways used here to produce the most efficient unavoidable sets.

SKMPP2 the last program is the last version of the multi tasks package mainly oriented on
Logical solution of puzzles (including a clone of Sudoku Explainer)
Generation of puzzles using mainly the vicinity approach
Canonicalization of grids
And miscellaneous tasks in the Sudoku field.

The frame is now 100% in line with the brute force frame, but the solver rewriting is still very partial., Only the cloning of Sudoku Explainer below nested chains is covered. This is the code (80% or more) that I use to play in the patern game

Work on this program will restart later, when the SK_17P2A program is ready.

Next posts are locked to give more details on he following topics

unavoidable sets collection using the brute force
17 clues search
skmpp2

I lock 10 posts to be safe

[champagne]

This first set of comments is for the collection of UAs in the program sk_17p2a.
The primary UA collection is common to the whole project “search of 17 clues puzzles “as of blue”. It is a key task and the code is now stable.

The collection of UAs used here can be re used in other projects, this is why the code is esplained here

The draft of comments is now available on my website here

The second topic having a wider scope is the generation of ED solution grids.
In the search of 17 clues puzzles "as of blue" (as in the proof that no 16 clues exists), the basis is more or less an entry file made of ED solution grids.

In the search of puzzles having a 566 656 distribution, the optimal entry file has exactly the count of ED solution grids, 5 472 730 538, but with a sorting sequence specific to each program. The entry file for the search of puzzles having a band with >=7 clues has redundant solution grids.

The draft of comments is now available on my website here

As the code available in sk_17p2a is for the distribution 566 656, this is the file generation explained in the comments.

In the sk_17p2a program, the entry file is by far not a critical code, so, the program creates ex nihilo the piece of catalog needed in the batch processed;

EDIT march 22th 2019
I added new socket UAs in the 17 clues search. A later comment update will describe the properties of the corresponding socket UAs (sockets 2 6/7 digits band 1 or 2 limited to a mini row 2 cells)

[champagne]

This post will give more details about the process used to search 17 clues in solution grids.
Subjects having a wider scope have comments in the previous post.
This post is more focused on parts of the process specific to the 17 clues search.

In the program sk17_p2a, the first part of the process starts with the generation of a "band 1 + band 2" basis and the relevant table of bands3
The "entry" generator is explained in the previous post.

The program try then each "possible band1" with "each possible band2", one with 5 clues, one with 6 clues. If this band can not be cleared, all "valid bands 3 for this pair" are sent to the next phase.

This is the critical code in the process. How more than 99% of the { valid bands 1 x valid bands 2 } are cleared is explained here

The second phase in the program processes a band 3. The general stratefy is to keep untouched GUA2s GUA3s as long as possibile, adding in priority clues in other places.
The comments for the phase 2 are here


band expansion

Each of the band 1 and bands 2 (one band 1 per batch) must be expanded to produce all valid bands of n clues against the relevant gangster. For the 566 656 distribution, we need all valid 5 clues and all valid 6 clues bands. This includes redundant clues as explained in the general comment of this phase.

Again, the valid bands generator can be used in other programs. In blues approah, a huge table of such bands was loaded in memory. Here, the table is built starting from the morphed table of uAs of the band. (morphed out of the table of UAs for lexically minimal bands).

During the expansion process (finding all valid 5 clues and 6 clues bands), an index of all 2 cells entries is worked out to cut the process in smaller pieces.

As we have the full set of UAs for each band, the expansion process itself is relatively simple.
Each UA is solved starting from the smallest. A redundancy control is done to avoid

ba... when ab... has been seen.
bac bca cab cba when abc has been seen
.....

[champagne]

code to run

The original sources are part of the skmpp2 repository, but this is my working repository and it includes among others

a lot of debugging code
fresh code added to preprare the future (eg pass 2 b, avoiding the 665 case)

I loaded in my website the sources cleane of most of unused code and of the debugging sequences (except for the validation test)
A separate file contains a readme and the file of puzzles used for the validation test. this file contains known puzzles having the 665 distribution

The code can be downloaded here
The second file is here


Test implementation

the tests implementation for the 17 clues search project is a key task.
The code is now stable (unless new bugs show up, but the tests will continue.

The primary set of tests was done on the file of known 17 having the 665 distribution
The current test is done using the code released above on the band 1 index 6 (number 224 in the 0-415 classical order) .
This band will deliver 5 417 000 band 2 and 98 249 555 bands 3. Several 17 clues must show up.

This test is somehow the biggest "debugging test" to do. Run on my laptop, It could still be active when I go back in France. I can not run more than 2 cores without risks of heating problems and my laptop shows already a significant loss in perlormance with 2 cores saturated.

Another test will come later with a higher index to see the effect of the 2x3y steps and have a better evalution of the timings witha high index.

The tests done are described here

[champagne]

lock4

[champagne]

lock5

[champagne]

lock6

[champagne]

lock7

[champagne]

lock8

[champagne]

lock9

[champagne]

lock10

[champagne]

The search of the 566 656 clues distribution will not start before mid April, when I am back from this long stay in the southern hemisphere.

The version of code to use is now nearly ready. I made recent additions after an analysis of the results of the previous version.

I am still thinking of an optional increase of the number of GUAs produced in the head tasks. This will be for bands 1+2 having a reduced number of bands 3 attached (likely 1-2)

The code in the repository reflects the current version. It includes a lot of debugging code, which can be needed if any anomaly comes in the ongoing tests.

I have drafted comments (see posts 2 and 3 in this thread). The last changes are not yet in the comments and the second part of the process (analyzing a full puzzle passing all bands 1+2 controls) is not yet drafted.

The 2 additions recently made and not in the comments are :

An extension to 512 of the UAs used in the first control. The previous limit of 256 seemed too low with bands having a huge number of valid 6 clues solutions. The effect is neutral for the bands with a low index.
An optional step 2x3y applied when the step count 2x2y (number of 5 clues * number of 6 clues) is very high.

Both intend to improve the situation for the “bad cases”. First test are positive, but more tests are needed for the final decision.

[champagne]

The code to run the search of a 17 clues in 566;656 mode is now stable. (no freash idea and a high price to pay to test any new code)
I cleaned it from part of the unused and debugging sequences and created to .zip files

One for the sources (just the files necessary tocompile it with Microsoft Visual C++ here

One for comments and validation test (known 17 665 distribution)here


The sources have been compiled using gcc 64 bits and this is the code run in the ongoing test.
As far as I can see, there is no big difference in performance using gcc /O2 option and the equivalent optimization in Microsoft Visual C++

I still have to test a Linux code, but I have no way to do it alone.