Search of 17 clues puzzles in a solution grid


Pass 1 searching puzzles with band 3 >= 7 clues


The pass 1 is supposed done to give some sense to the pass 2 explained earlier.

In the comments, we assume that the pass2 comments have been understood.


The process in the pass 1 differs from the process in the pass 2 on the following points


The “entry file” is different;

We have to combine x,y (valid band 1; valid band 2) for all x+y <=10 ( 5+6 or 6+5 in the pass 2a)

Consequently, the band expansion has to cover all valid bands from 3 to 7 clues

And we have no stack constraint. All the corresponding code has been suppressed


The rest could be the same except that tables dimensions have to be adjusted to the new context


Entry file


Although the entry is worked out on the spot, it is easier to comment as if the file was actually created ;


 In the pass 3 we have exactly N= 5 472 730 538 solution grids to consider, in the pass 1 each of the bands/stack of the solution grids have to be searched for more than 6 clues.  So we have close to 6*N bands 3 to consider, attached to all possible ED bands 1+2.


The process applied in pass2 already considered al ED bands 1+2, but only kept those having bands 3 attached.


Here, each band 1+2 will have some band3 attached, so we have 983 959 110 ED bands 1+2.

The band 3 attached are the valid bands 3 after elimination of auto morphs. Blue announced 32 835 497 303 such band 3 and this is exactly was comes out of the current code when the band 3 filter is limited to auto morphs.


This is an average 33.37 bands 3 per ED band 1+2, and, opposite to the pass 2, the average count does not changes much for the last “band 1” (however, the max number of bands 3 attached is higher)


Note : an ED band 1+2 with a minimum number of clues >10 can be ignored


Band expansion and 2X2Y index



Now, the 2X2Y index has to consider 5 cases and we have to store up to 5 tables.

In fact, knowing the minimum number of clues in band1, the expansion of band 2 can be reduced as soon as this minimum is >3 (most tables have more than 3 clues as minimum)


The code has been slightly changed to handle the new situation.

The first position of the index is now made of the 2 cells in the right order

Handling of the dead 2X2Y branches has been revised in line.


Trying all x+y<=10


The code in pass 2 was already open to a variable number of clues in band 3 (to allow the case 665). So, nothing changes in the part 2 (band 3 process) except that we can start with more missing clues out of GUA2s GUA3s (the theoretical maximum of missing clues in the “critical count” is 14 in a 3+3+14 clues solution, but this will never happen; the “no GUA2 GUA3” situation was already uncommon in the pass 2.


The main change is in the G17B::Go routine where the steps 566 and 656 were launched.


We have now 9 possible ways to combine x and y, 6 of them, not symmetric having to be applied twice


7,3  6,3  6,4  5,3  5,4  5,5  4,3  4,4  3,3


For the top bands 1 (minimum  6 clues), only the first 3 are possible (nothing to do if the band 2 has a minimum of clues >=5


For the last bands (band 1 minimum <=4 clues) all cases will be valid. Again, we can expect a huge difference in processing times between the top bands 1 and the bottom bands 1. However, we have to keep in mind that the total count remains lower than the count 5;6 + 6;5 and that the number of valid bands 1+2 will be lower as well. (this was the reason to have a pass 2b avoiding the 6+6 case).


With  the worse band, the band 29 (rank 415 in the sorting sequence used here) the ratio

xy pass2a/xy pass1

Is above 2.2


Adding UAs GUAs in a 2X2Y step



In the pass 2a  process, it appeared interesting to switch to the vector mode for fresh UAs GUAs. In the current process, this is not done, but the question is open.


In option, the process can easily be replicated at the middle of the 2Y2Y step.



Timings estimates


 The same sample file as in the pass 2a has been used to get an estimate of the process  power consumption. The test has been done on my best processor, with 7 cores saturated working in parallel.


The average runtime per entry has been  281 milliseconds  corresponding to 51 milliseconds per solution grids with an average 11 milliseconds per entry for the preliminary tasks (UA search, bands expansion ...) corresponding to an average 2 milliseconds per solution grids.


The sample file prepared for the pass2a was already slightly biased. Last bands were missing. Here the bias is bigger just because we have more ED bands 1+2 with a high count of valid bands.


My rough estimate is that a 10% penalty should be applied to the data collected. On the other side, if we compare to the data published for the pass 2a, we have to consider the penalty of the parallel process (20% ???). The priority has been given to the scan, another estimate will be done later.


Searching 16 clues puzzles


A 16 clues puzzle can have one band stack with more than 6 clues or has exactly 5 5 6  or 4 6 6 clues in bands and stacks.


The pass1 program will work with the optimal performance for the 16 clues search doing the following


x+y<=9 and band 3 having missing clues to reach 16

x=5;y=5  or  x=4;y=6 or x=6;y=4  with 6 clues in band 3


Blue announced  a code doing this with an average 43 ms per entry (ED bands 1+2), Starting from 11 ms for preliminary tasks, this seems to be achievable with the code released after adjustments to the 16 clues search. Blue worked with a  smaller set of UAs GUAs, but as far as I can see, with this code, it would not pay.