Search of 17clues Bands Generation
In the search of 17 clues Sudoku “as of blue” the basis for the search is a solution grid.
In the search of puzzles having the distribution 665 in both directions, The search is made on the set of ED solution grids (exactly 5 472 730 538 solution grids).
The sorting sequence in this process is not the classical catalog‘s one. The first criteria is (in ascending order) the number of valid bands against the band gangster. This is valid for the three bands (band1 count <= band2 count; band2 count <= band3 count)
For the rest, the classical minimal lexical order is used to avoid redundancy.
As the valid ED solutions generation is by far not a critical task, the “entry” file is created in the program.
Three different “entry file” generators are needed for the total project
“Entry” for the basic 566;656 search following the above rules,
A band2/band3 exchange the avoid the 665 cases
The entry file for the case where band3 has >=7 clues. In this last case, each band/stack must be once “band3”, so we have several morphs of the same ED solution grid.
The in line “entry” generator is derived from a code supplied by blue years ago for the XY27 process.
The target is have the “entry file” minimizing the process.
The strategy applied here is to attach as many as possible bands3 to the pairs bands1+2 having the smallest XY.count. This is expected to give a lower count of attached bands 3 for high XY counts and consequently a better chance to kill some XY when all bands3 are cleared through the 6 clues limit in stack.
Main loop basis
The basis for the generation is done of three loops combining all solutions for band1 to all solutions for band 2 and to all solutions for band3. Filters are applied to avoid redundancy.
The outer loop is the band 1. In fact, as a batch is limited to one “band 1”, the outer loop does not exists.
The band1 is always one of the 416 min lexical bands. To be in line with the design, the band is identified by the sequence order towards the count of valid band against the gangster.
A table of possible auto morphs is built at the start.
The middle loop is for band2. Each band created is first identified (416 bands id and morph ) the band is ignored if the index is > index band 1. Auto morphs of band 1 are applied and the band 2 ignored if a smaller (min lexical band ) morph appears.
If band1 and band2 have the same index, perms band1/band2 have also to be studied.
The inner loop is for band 3. Again, all valid possibilities are scanned
In the 566;656 distribution, band3 index must be <= band 2 index. And again, all auto morphs are studied to see if the band3 is equivalent to another band 3 having a smaller min lexical form.
If the 3 bands have the same index, more perms have to be considered.
Given a valid band, we want to identify the corresponding min lexical band (one of the 416) and receive back the mapping information.
The process uses the table of min lexical bands, the code is located close to the table, in the file
The call to the process is
int BANDMINLEX::Getmin(int * b0,PERM * pout_user)
b0 if the band (27) to analyze
PERM * is the structure receiving the data
The PERM structure is quite simple int rows, cols, map,i416;
Mapping rows, columns and digit and sending back the 416 min lexical Id
Getmin() cheks the minirows and split immediately the process depending on the possibility to have a min lexical
123456789 456 or Getmin6
123456789 457 Getmin7
In both cases, the strategy is the same,
Try each perm of the boxes/columns/rows
Map first row to 123456789
Check if you find one entry in the 416 table.
Auto Morphs Table
We have an auto morph if exchanging rows column stacks and relabeling row1 to 123456799 we get the original band.
We have to consider band 1 auto morphs to clear redundant bands 2 and bands 3.
The auto morphs are expressed in the same way as the PERM described above.
The table of such perms is built in
Each box is move to box1, then all rows/columns perms are done and the band is relabeled to have the original sequence in box1.
Row 1 (box 2;3) is then reshaped to 123456789 and the other mini rows compared to the band.
Band 2 redundancy and auto morphs
A new band 2 is always ignored if the band2 index is > band1 index.
With band 1 index 0, all band2 will pass this filter, with band 1 index 415, only bands 2 of index 415 will pass this filter.
So, in average, the band2 count decreases sharply with the band 1 index. This is true in average. As the number of auto morphs for a given band 1 can vary in a wide range, Bands 1 with many auto morphs will produce less bands 2.
A new band2 is always ignored if using a morph of band 1 we can produce a band 2 with a lower min lexical status.
If a morph of band 1 can produce the same band 2 (reordering and relabeling band 2,) Then, we have a band 1+2 auto morph to be considered later for bands 3
And with the same index for bands 1 and 2, We can also see redundancy and auto morphs exchanging bands 1 2 .
At the end, we have a new band 2
plus the band1+2 auto morphs
plus the band2+1 auto morphs if we have the same index.
Band3 redundancy distribution 566 656
This is the “entry” for the program sk_17p2a searching 17 clues with the distribution 566 656 on the catalog having band 1 index <= band 2 index <= band 3 index
Again, all bands 3 are produced for each bands 1+2 accepted.
The band 3 is discarded if band 3 index > band2index
If the three band have the same index, we can find a diagonal situation where all three bands have again the same index with a lower global max lexical value. Then the band 3 is ignored
In the general case, we have just to check if a lower lexical value appears with a band 1+2 auto morph.
We can also find index band2 = index band. Then the perm band2 band3 must be checjed.
The case ( index b1= index b3) !=(index b2) is not possible here. It will come in other entries.
When this case can appear, the diagonal situation must be explored as well.
Table of Bands1 2 3 per band 1
Just for information, here is the table giving the expected status of the 5 472 730 538 bands 3 to process in the 566 656 search.
Column 1 is the index (increasing order of valid 6 clues for the band)
Column 2 is the correspond ding classical 0-415 min lexical index
Column 3 in the count of bands 2 attached to the band1
Column 4 is the count of bands3 attached to the band 1
This table can be produced using the process Go_c17_80(). This enumeration process has been used to check the validity of the in line generator.
The overall average number of bands 3 per bands 1+2 is close to 9.
On the top of the list, where the count of XY is small, the average is in the range 16-19.
With and index>250, the average falls below 2 bands 3 per bands 1+2. This is also the area where the count of XY is much bigger. Around 2 x 500 000 000 here, more later.