Search of 17 clues puzzles in a solution grid

 

K Band Expansion

 

The band expansion is done on a morph of one of the 416 valid bands.

In the global project, we have to consider all valid bands having 3 to 7 clues.

The code shown here is specific to the 566 656 case and only bands having 5 or 6 clues are produced.

 

The process is done in 2 steps

 

First, using the morph “cells remapping table”, the band UAs are morphed to the actual morph. In fact, for band1 in that process, we have directly the min lexical morph, so the remapping is neutral. This would not be true when the search is done in test mode on a given entry.

 

Then the UAs are used to create the valid bands and the index.

 

The process applied is the same as in Gary McGuire project: expansion of the list of uas;

 

Note : Blue was using a huge table with all valid solutions in the base morph.

 

Expansion of a band is not expensive at all and using a base morph expansion force to use a remapping later. For me, building the table of valid bands on the spot should be better at the end. Here, we have another reason to do it live. During the expansion phase, the index used later to split the process in 2X2Y steps is built.

 

Valid bands are stored  in relevant tables(struct XY_EXPAND tables xye6, xye5, one of each per band  1-2)

 

For each item of the extended table, the following information is stored

Cells in the generation order ,

A cell bits field in a 64 bits field

A count per stack.

 

This table is a big one and is still bigger in the pass1 where expansion must produce as well bands with 7 clues.. Band N° 29 has 237762 valid bands with 6 clues and 803574 valid bands with 7 clues.

 

The morphed uas of the band, the morphing table and the index are stored in  band3[256],

 

Later on, other tables will be added with UAs information. These tables (all sized to 256 as first index) are stored in genb12 the occurrence of the class GEN_BANDES_12 encapsulating data for the primary tasks

 

L UAs generation

 

 

In this process all UA generation is done using brute force a process that I learned from mladen Dobrichev.

The topic has a wider scope so I opened recently a specific thread to explain how it works

.

http://forum.enjoysudoku.com/uas-for-a-17-clues-puzzle-search-in-a-solution-grid-t33744.html

 

A serious update of the thread has to be done for 2 main reasons

 

UAs generation for bands 1+2 has been extended to more digits and to special patterns

The process has been simplified and must still be improved.

 

Digging in the code can be differed. Even if we don’t catch all small UAs, the risk to have non valid UAs is close to 0 after all test made. The priority should be given to the main process.

 

Here the main difference with blue’s process is that many more UAs are produced at the start for bands 1+2.

With the current code, the first set of UAs is limited to 600 UAs.

 

As the process is split in 2X2Y groups (first 2 cells in one band,  first 2 cells in the other band), The interesting limit as we will see is the maximum number of UAs not hit by the 2X and 2Y. The current code has a limit of 256 UAs for a 2X2Y. This is likely much too low just considering that UAs out of the scope of the initial collection are added later.

 

As far as I know, blue worked with 64 UAs plus something special for small UAs in bands 1+2. (knowing that UAs located in one band are anyway ignored as they are redundant with the valid bands)

 

As the brute force used is heavily “band oriented”, UAs are stored as 2 x27 bits fields in a 64 bits field.

 

Note: in other cases, as in the GUAs below, the 54 bits are grouped. In some places in the code, the remapping of the 54 cells must be done.

 

L1 small UA 2-5 digits

 

Normally all UAs with a limited number of digits are searched with 2-4 digits and with small restrictions with 5 digits.

 

The size limit (number of cells in the UA) here is usually 14 cells increased to 16 cells with 5 digits. Is seems of very low interest to use a bigger size, but I have no idea of what could be the optimal set of UAs . The current set follows 2 rules working pretty well:

 

Take smallest UAs

Take cheapest UAs

 

L2 more UAs

 

In the process, Uas are added when a band 1+2 “XY”) is seen with more than one solution. The first “false” solution gives an UA. The brute force guess process has been adjusted  in this case to produce new UAs as small as possible.

 

Analyzing the result of the first runs, and having in mind the gangster effect, it appeared interesting to consider UAs limited in one band to one or 2 mini rows.

 

Doing so, we can limit the brute force to the other band, a cheap process, and find relatively small UAs with more than 5 digits.

 

The size limit to store such UAs is  18 cells (for both bands)

 

M Gangster UAs generation

 

Gangster UA collection can be seen in 2 different aspects.

 

GUas have to be collected for the whole set of bands

 

Each band must be analyzed to see what GUAs are valid for the band and how they can be translated in GUA2s GUA3s GUA4s GUA6s.

 

M1 preparation of GUAs generation and of valid GUAs used

 

We have seen in the general overview that we have 81 sockets for pairs and 81 sockets for triplets.

 

Triplets are only valid in a given  band 3 if the 3 digits are located in a mini row.  For pairs, we have to consider patterns of size 4 or 6 in band 3 having the 2 digits in 2 different rows (GUA4s GUA6s)

 

To understand what is done in the preliminary task, we have to consider 2 different situations.

At the start, we don’t have to process sockets that have no use in the set of bands 3.

Later, after a valid XY has been seen use of the still valid sockets in a specific band 3 must be as simple as possible.

 

When a XY is sent to “part2”, we know all sockets still valid for the set of bands 3.

For a given band, if the socket correspond to a mini row, It becomes one of the GUA2s GUA3s of the band and it contributes to the definition of the minimum clues found in band 3. If the socket has a corresponding GUA4 GUA6 in the band, the GUA4/GUA6 pattern is added to the list of UAs of the band3.

 

Each band3 is scanned to see what sockets are valid. Valid sockets are stored in 2 x 128 bits fields (used 3x27 bits in 3 x32 bits sub fields.)

The same work is done for GUA4s GUA6s.

 

 

Combining these fields by a logical “or” , we get the final list of sockets to process. (bands-pairs; bands-triplets)

 

In the same time, information for the next phase is stored in the tables tindex... These tables have a second index set to 96 due to the fact that the index will come out of a 3x27 bits field.

 

For a pair, 2 values are stored : the bit pattern of the pair; the unused bit in the mini row. Both play a role later.

For a triplet as for GUA4sGUA6s, the bit pattern of the cells is stored.

 

M2 searching and storing GUAs

 

A process very similar to the search of UAs is launched for each possible socket. All GUAs having a subset in bands 1+2 are ignored. (the band 3 receives a valid bands 1+2). As the subset can be in a band, the search must consider UAs located in one of the band,1-2. These  UAs are not in the final list. As GUAs searched are limited to 5 digits as well, the search is done before the “more UAs” generation. (see L2)

 

All GUAs are identified by the 64 bits pattern in bands 1+2 plus a 0-80 id corresponding to the gangster socket.

 

In the 2X2Y loop, GUA2s and GUA3s are loaded in the same table, with then a socket id set to 81-161 for the 3 digits socket.

 

Contrary to UAs, the 54 bits are here located in the first bits of the 64 bits field and the highest byte is used to store the socket id..

 

In the process, it seems better to keep as many UA’s as possible. The primary table can receive to-day 1000 GUAs;

 

At the 2X2Y level, the limit is kept very high, currently 640 GUAs. Most often, the actual values will be much lower. Contrary to UAs bands 1+2 and later UAs in band 3, No brute force  check will add fresh GUAs later, so keeping as many GUAs as possible seems to be the right policy.