Search of 17 clues puzzles in a solution grid
CONTEXT and General overview page 2
A Solving Strategy
The general strategy applied by blue is to find all solutions to bands 1+2 then to search in relevant bands3 the missing clues.
As in the Gary McGuire project, the search is done on solution grids.
The problem is divided in 2 cases
Puzzles with at least a band/stack having 7 clues or more
Puzzles with no band/stack having more than 6 clues.
The first task will be to create a file of non redundant solution grids with the relevant bands 3 having a number of ED bands 1+2 as small as possible. This is outside the scope of the general overview, but will come later as “side task”. In fact, the file is created on the spot producing several “entries” (band 1+2) and the corresponding relevant set of band 3, so the corresponding code is compulsory for the planned task;
For a given bands 1+2 (“Entry”) the start is a pair of “valid solutions grids” in bands 1 and band 2..
Lets call ’X’ and ’Y’ the corresponding partial solutions and ‘x’ ‘y’ the corresponding number of clues
In the case 1, the band 3 has >= 7 clues, so we are looking for x+y <= 10 clues. We know that a 17 clues puzzle can not have a band with 2 clues, so we have to test all possible
3 <= x <= 7 3 <= y <=7 and x+y=10
In the case 2, having no band/stack with more than 6 clues, and expanding in priority bands, stacks “size” control will play a key role.
Here, we focus on case 2.(6,6,5). As we will see, the process is highly sensitive to the total number of XY and to the number of valid bands 1+2. Moreover, the weight of preliminary tasks is relatively small, so, the process is again split in 2 pass:
One pass for the distributions 656 and 566 using the same “entry” file
Another pass to avoid the distribution 665 on the same “entry” file.
In both cases, the entry file produces 5 472 730 538 bands 3 corresponding to the ED solution grids count. These band 3 are linked to the appropriate ED band 1+2 depending on the pass done.
In the pas 566;656, the number of ED bands 1+2 is 610 163 364 for an average 8.97 bands 3 per ED band 1+2 .
Note, in the pass with band 3 >= 7 clues each band/stack of the 5 472 730 538 must appear once as band3. Blue found 983 959 110 ED bands 1+2 .
B Finding solutions for bands 1+2
In our case 2 first pass, we can have :
‘x’ clues band 1 =5’ ‘y’ clues band2 =6 band3=6
‘x’ clues band 2 =5’ ‘y’ clues band 1=6 band3=6
Such an ‘X’ ‘Y’ solution has both bands valid against the relevant band gangster.
In most (>90%??) cases, this is not enough to be a solutions for bands 1+2.
To be a solution, all unavoidable sets “UAs” having cells in both band 1 and band 2 must be hit.
Combining each ‘X’ to each ‘Y’ is a problem highly “cache sensitive”. Blue did not express it in this way, but, in fact, used temporary interim tables optimizing the cache situation.
Cache optimization is tightly linked to the processor used. In that process, some of the cache optimization possibilities are used. The corresponding parameters have been located in “define constants.
The number of ‘XY’ varies widely and the number of valid bands 1+2 as well. Using the lexically minimal list of the 416 ED bands
Band 1 has no valid solution with 5 clues and 726 with 6 clues
Band 30 has 51516 valid 5 clues and 237762 valid 6 clues.
C Unavoidable Sets (UAs) filters for bands 1+2
We can not build a table containing all UAs, for bands 1+2; we don’t have enough memory available and the process would be too costly.
Instead, we can work with 2 sets of UAs (what did blue)
- UAs defined at the start of a new “band 1+2”. For such UAs, vectors can be initiated (same as in Gary McGuire use of high degree UAs) giving a quick status of UAs still valid when a cell is assigned.
- UAs appearing when a ‘XY’ is not valid (first solution not equal to the studied solution grid). This is one among the key ideas brought by blue. Such UAs can not be economically used in the same way as the former lot,. A short table of such UAs is built to save brute force consumption in the vicinity of a former checked solution for bands 1+2.
In fact, the second group is split in 2 tables of given size loaded in FIFO mode (oldest UA replaced by a fresh one when the table has the maximum size).
And (see chapter H) in the optimized process, the smallest UAs of the second group are added to the first one, to benefit of the vectors power
D Stack Filters in 665 566 656 mode and final check for bands 1+2
In the case 2, each stacks has a maximum of 6 clues. A small part of the XY will pass the limit. As this remains a relatively cheap control, the stack filter will be applied immediately after the filter based on the UAs created at the start.
But the stack filtration will also play a major role in this mode in the band 3 process.
As soon as a stack has reached 6 clues ( either as assigned or as “ reserved “) the stack is locked for addition of clues.
The corresponding situations will be detailed in the band 3 chapter.
Having applied the stack filter, the last thing we can do is to apply the brute force to verify that the solution for bands 1+2 is unique.
Use of the brute force remains very costly, and one can think of postponing that control for later.
Here as written earlier, we use the brute force in a specific way to catch, if the solution is not unique, the first non valid solution as UA. So a brute force will clear some XY produced later.
E Band 3 collection , “first filter” and cache issue.
In the opening task for each “entry” (band 1+ band 2), the relevant table of possible bands 3 has been built.
The number of band 3 varies again and can be in the range 1-288 (288 is a maximum given by blue for the case 1, here, the maximum is lower).
The average number of bands3 is 9 in the 566/;656 process using bands sorted on the minimum count of valid 6 clues bands.
For each XY passing the previous filters, we have to consider each of the possible bands 3.
From now on, clues can only be added in band 3, so any global UA can be reduced to the cells belonging to band 3;
The major tool used in band 3 is the set of such UAs having 2 or 3 cells in the same mini row (see next chapter for more details).
Such UAs are “native disjoint” in the following conditions
A mini row can have 1,2 or 3 pairs of cells belonging to existing UAs with 2 cells in band 3.
If the mini row has no such identified UA, A mini row can have the 3 cells belonging to an existing UA with 3 cells in band 3 (if a pair exist, the triplet would be a superset of the pair)
1 pair and 1 triplet will force each one clue
3 pairs will force 2 clues
2 pairs can force 1 or 2 clues (one if the clue is the cell common to both pairs). The count is set to 1, the minimum
Assuming that we have identified most of such UA (again, more details in the next chapter), we have the minimum count of clues needed in band 3 and the split per stack.
Comparing the count to the known limits (number of clues expected in band 3 and limit of 6 clues per stack) we can already clear most of the possible bands 3.
Blue used here interim buffers with a claimed significant improvement in the performance. This means that again, we will be “cache sensitive” in that part (having in mind that we have to go to the end of the band 3 analysis for each valid band)
All optimization options are discussed in chapter H.
F Bands 3 gangster Unavoidable sets (GUAs)
We have seen in chapter E) how important are UAs having 2 or 3 cells in a mini row in band3.
As we have usually a collection of band 3 (9 in average) for an entry band 1+band2, we have to collect them, if possible in once for all bands 3. This is the gangster collection of UAs, another key finding from blue.
Let’s develop the case of a pair in a mini row; The triplet is a similar logic.
We take 2 columns of the same box in band 3. and a pair of digits in the possible digits in band 3. We have in total 81 such pairs (3 boxes x 3 pairs of columns x one of 3 digits in first column x one of 3 digits in second column)
Several bands can have the corresponding pair in one of the 3 mini rows of the box.
We can then define a sub family of UAs of the full solution grid having all cells in band 3 equal to the solution except our 2 cells. Corresponding UAs will only differ by the location of the 2 cells in band 3.
The Band 1+2 part of the UAs is the same for all band3.
Band 1+2 is limited to the “double gangster” of the solutions grid, except in the 2 column where the 2 digits can be exchanged. I’ll call “socket n” the corresponding link between band1 1+2 and the gangster band 3
I’ll call GUA an UA of the socket. Such an UA will have the bands 1+2 pattern plus the 0-80 id of the socket
Such GUAs can be collected at the very beginning and vectors of GUAs hit by a cell in bands1+2 prepared in the same way as for UAs in bands 1+2 (chapter C)
I’ll call GUA2 GUA3 the band 3 part of such GUAs in the appropriate band.
If the pair is not in a mini row for a specified band 3, we can still have simple patterns in band 3 becoming UAs band 3 for the specified XY
We consider 3 such patterns of size 4 GUA4 or 6 GUA6
a.. b.. ... || a.. c.. b.. || a.. b.. ...
.b. a.. ... || b.. a.. c.. || .b. ... a..
... a.. b..
If such GUA4 GUA6 exist for a specific band 3 (and for a given XY), it is known nearly for free looking for GUA2s GUA3s.
Then they can be used as band 3 UAs to define the possible band 3 solutions.
Triplet in a mini row
The logic for a triplet is very similar. The main difference will be in the generation of the corresponding GUAs
Again, we have 81 possible triplet with now
3 boxes x one of 3 digit in column 1 x one of 3 digits in column 2 x one of 3 digits in column 3
The program analyze at the start the band 3 validity of pairs and triplets.
Also at the start, possible GUA4s GUA6s are identified.
Selecting GUAs to search
A band 3 has a maximum of 27 pairs and 9 triplets. We could add about 20 GUA4 GUA6 patterns. This is far from the 81+81 possible GUAs sockets.
When the number of bands 3 is small, it is important for the performance to limit the GUA generation to sockets having a potential use.
Validity of GUA2s to GUA6s for a given XY.
When a XY has been defined, each of the GUAs sockets is scanned to see if at least one GUA of the socket is still valid. If so, the corresponding GUA2s—GUA6s are valid for the XY