Search of 17clues Bands Generation

http://pagesperso-orange.fr/gpenet/SK17GCAT/gcat.htm

The search of 17 clues puzzles uses some variant of the catalog of solution grids.

Usually, this catalog is shown in minimal lexical mode.

 

The number of ED solution grids is  5 472 730 538. Using another canonical form does not change the count.

 

Catatlog variants

 

In my search of 17’s derived from blue’s finding, three variant of the catalog are used.

 

If the band 1 is always shown as lexically minimal,  the main sorting sequence is the count of valid band 1 having 6 clues.

 

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 clue distribution per band can be 566 656 665. As the case 665 is expected to be too long to solve, a specific version of the catalog is used to stay in the mode 656; To make it simple, bands 2/3 are exchanged, but as the catalog is created on the spot, this is done with the appropriate code.

 

For puzzles having at least one band/stack with more than 6 clues,  each band/stack must appear once as band 3, blue reported  983 959 110  ED bands 1+2 out of his code as entry of this process .

 

Sorting sequence for the bands

 

As written above, the sorting sequence in this process is not the minimal lexical order as in the classical catalog.  The first criteria is (in ascending order) the number of valid bands against the band gangster.

 

For the main entry of the 665 distribution (566 656) 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.

 

In the search with a band /stack with more than 6 clues, The rule is still valid for bands 1 and 2. Band3 has no constraint except (automorphisms) to be lexically minimal for the given bands 1+2

 

For the second entry file in the distribution  665, the entry file is strictly equivalent to the main entry sorted after inversion of bands 2 and 3.

 

Built in catalog

 

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

 

A) “Entry” for the basic 566;656 search  following the above rules,

B) ”Second entry” for the 665 distribution with a band2/band3 exchange avoiding  the 665 cases

C) The entry file for the case where band3 has >=7 clues.

 

In each case, the code (written for a unique band 1 as start) must deliver in sequence bands 2 and the relevant sets of bands3. A checkpoint (restart point) is written every 64 bands 2

 

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.

 

In fact, the code is very similar for the three cases. In the released version, the case C) is missing, cases A) and B) are merged in the same code.

 

The code comments are focused on the case A)

 

Built in generation of the entry for the 566 656 cases

 

 

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. In other words, the highest count of bands 3 attached is for pairs bands1+2 were the number of valid bands 1+2 is expected to be lower.

 

 

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.

 

The variants B) and C) have other rules for the band 3

 

Band identification

 

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

 

go_17sol_tables.cpp

 

The call to the process is

 

int BANDMINLEX::Getmin(int * b0,PERM * pout_user)

 

Where

b0 if the band (27) to analyze

PERM * is the structure receiving the data

 

 

The PERM structure is quite simple  int rows[3], cols[9], map[9],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

 

bandminlex.GetAutoMorphs(it16, t_auto_b1);

 

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 3. Then the perm band2 band3 must be checked.

 

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.

 

Note, in the bottom part of the table 2 items have been put per line for technical reasons

 

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.