Search of 17 clues puzzles in a solution grid

CONTEXT and General overview page 3

G band 3 search strategy

 

The first part

Selection of a valid XY; Pre filter of bands 3 still possible

is done

 

We have now to process a band using mainly the following data

 

XY solution necessary for the final check

GUA2s GUA3s  set still valid

Count of the minimum number of clues needed to hit GUA2sGUA3s and count per stack

UAs specific to band 3

GUA4s GUA6s to add to them

 

 

The “part1” was basically very simple

 

Combine 2 valid bands

Apply UAs filters to see if it is a valid band 1+2

Apply more filters to reduce the count

  Number of disjoints GUA2s GUA3s still valid

  Minimum number of clues per stack

And finally apply the brute force adding UAs appearing for non valid bands 1+2.

 

The “difficult” issue in part 1 was to benefit as much as possible of the “cache” potential. This is somehow a pure coding topic.

 

“part 2” is more complex and the wording of blue showed that some areas of the code should be checked carefully to assess that they are “bug free”.

 

To understand the choices suggested by blue, it’s good to have in mind the average number of disjoint GUA2s GUA3s appearing in the process.

 

Here is a distribution of the Band 3 problem out of the sample of 10 000 entries  for an average of 13 bands per entry

 

The average number of bands 3 to process per entry is 326 056

 

45% of the total have enough compulsory clues (here below “critical status”) to produce a possible 17

For the rest, the distribution per “minimum number of clues in GUA2s GUA3s is the following

 

5 clues (miss 1 clue)                 119 838

4 clues (miss 2 clues)                  46 974

3 clues (miss 3 clues)                  10 798

2 clues (miss 4clues)                     1 475

1 clues (miss 5 clues)                       111

0 clues (miss 6 clues)                           3

 

In the last case, (miss 6 clues) we are in a well known situation with a list of UAs for band 3 (pure band 3 UAs plus GUA4s GUA6s added)  the only special feature is that no stack can pass the limit of 6 clues.

 

For cases “miss 1” to  “miss 5”  the general strategy is to keep as long as possible the GUA2s GUA3s .

 

The main reason is that we have here a known minimum number of clues, but we will see another key reason.

 

 

The GUA23s field  “field1” is made of all cells belonging to any of the GUA2s GUA3s. Other cells in the band (if not yet assigned as clues) will be “field2”.

 

the “critical situation.”

 

A situation is “critical” if the minimum number of clues needed to solve GUA2s GUA3s is equal to the number of missing clues. In the above table, 45% of the bands 3 processed start in a “critical” status.

 

A band 3 can be globally “critical” or can have “critical stacks”

 

In a critical situation  all clues must be in field1 (or the part of field 1 within the stack) and in a mini row with 2 GUA2s, the cell to assign is the cell hit by both GUA2s.

 

Consequence of the general strategy, if we are not in a critical situation, cells will be assigned in priority in field2.

 

 

When the possibilities to assign a cell in field 2 are exhausted, we enter in the most difficult status called “subcritical”. Missing cells must be taken in field 1.

 

During the process, after each assignment of a new cell, the stack “critical status” must be updated.

 

Entering a stack critical status has 2 consequences :

 

A mini row with 2 GUA2s has the common cell assigned

The field 2 is reduced and can not contain any more the cells of the critical stack.

 

 

 

Brute force in a “critical situation”

 

In my code, the general process is to add clues using UAs and GUA’n’s till the moment where the limit is reached and then, if the UAs/GUA’n’s list is exhausted, to use the brute force to test the solution.

Blue describes a process going in the reverse way. To make it simple I could say “start from a full band 3 and reduce the number of clues till the moment where you reach a situation with more than one solution”

 

My first results seemed far from blue’s achieved performance and I suspected that the hidden reason was in the above different strategy.

 

 The GUA2s GUA3s have a hidden property. In most cases, if one clue of a GUA2 in a mini row is given, then the other one is solved. Similar effect will appear with GUA3s

 

Consequently, in most cases, if no 17 exists (nearly all cases) applying the brute force using all cells in “field1” (all cells forming GUA2s and GUA3s) will show a multiple solution.

 

 The yield can be improved if compulsory assignments are done first. This includes

 

Assignment of the common cell in mini rows with 2 pairs GUA2s

Assignment of the cell for Band 3 UAs (including GUA4s GUA6s) having only one cell in field 1.

 

The same strategy can be applied when missing cells have been first applied leading to a “critical residual situation.

 

To show how efficient can be an early brute force, in the former example of 10 000 entries 130 000 bands 3,

An average 511 337 calls per entry to the critical status was made and only 11 in average gave a valid band applying that policy.

 

But in fact, the effect on the global performance decreases when assignments outside “field1” are done, just due to the fact that the residual “critical situation” would give less final solutions to test.

 

Note : the brute force filter becomes then the bottleneck for the part 2. The current code is likely not optimal for that situation.

 

Early brute force extensions

 

Applying brute force to a bundle of cells can be considered in other situations, but this must be done only with a good chance to get a global situation with still multiple solutions.

 

Basically, if the situation is not “critical” at the start, we have less cells in “field1” but we have many cells in field2. The number of cells in field 2 shrinks when some stacks can not accept more clues, and we have for the last clue to assign in field 2  some special conditions.

 

Defining the optimum is an open point. In the current code, an early brute force is done

 

 For the last clue in band 2 with a bundle of

           already assigned cells

           plus cells hitting all relevant UAs   

           plus field 1

In the process specific to the case where field1 is empty after several assignments if some stack limitations reduce the count in field3

 

 

Split of Band3 UAS

 

 

Addition of clues is made using UAs specific to band 3

 

.We have 2 families  of such UAs

 

General UAs specific to band 3

GUA4s GUA6s found analyzing the list of still valid GUAs.

 

These UAs are merged (with at the top GUA4sGUA6s generally smaller) and then split in 2 sub tables

 

Having as general strategy to assign missing clues first  in “field 2”, We have for each new band 3 to split the list  in two sub tables :

 

UAs having no cell in field 1 (table 2 in the code ) T2 here below.

UAs having one cell or more in field 1 (table 1 in the code) T1 here below.

 

Note: if the situation is critical at the start, the table T2 must be empty to have a chance to produce a 17.

 

T2 will be in use to add clues in field 2.

T1 will be in use after all clues in field 2 have been assigned, so all cells in field2 can be ignored.

 

In the process, the table T1 will shrink after each assignment. At each step in the process, if a UA is reduced to one active cell, the corresponding cell is assigned. This can come at the very beginning in the critical process, especially when the common cell of 2 GUA2s sharing the same mini row has been assigned.

 

The general strategy will be to use these tables to select cells to add in the same way as in the McGuire process, using in priority the smaller UA.

 

Doing so, “dead cells “ appear progressively and some UAs can be reduced to one cell (forced assignment) or be empty (dead branch).

 

Adding missing cells in field2 and subcritical status

 

When the situation is not critical at the start, we have in priority to assign cells in field2.

If “n” clues” are missing, 0 to n clues can be assigned in field 2, the rest being redundant in field 1. Assigning missing clues in field 1 is called “subcritical process”, It is the most delicate part of the band 3 process.

 

The subcritical process has to be called only if the residual T2 is empty. If T2 is not empty, the corresponding UAs will never be hit by assignments in field 1.

 

In the code, the function adding the clue “n” is called;

           one clue is added in field 2 and the function adding the clue “n-1” is called first

         If all UAs in T2 are hit, then the sub critical process is called.

 

Selecting a cell is very similar in all cases except for the last cell to assign.

Any cell out of active field2 can be used. Active field 2 is updated considering dead cells (already assigned earlier in the same branch) and stacks having reached 6 clues.

 

If we still have non hit UAs in T2, a UA having the minimum number of cells is selected and used. If no UA exists, all active cells are considered (and the subcritical process must be applied after)

 

 

Adding clues in a subcritical situation

 

Adding clues in field 2 or solving the critical status is relatively easy. Addition of clues in a subcritical situation must be done very carefully.

 

In the process, the table T1 is reduced step by step and the part still valid copied at the end of the current table.

 

In the sub critical process, we have to consider the active cells in the sub critical process itself, but also the future situation when the “critical step” is called. This is valid for the UAs of T1 copied. They must be in the valid status for the future “critical process”.

 

Another difficulty here is that a clue assigned in a GUA2 GUA3 has to be seen in priority as an extra clue.

 

The priority is given to T1.

 

Based on T1 UAs needs, a clue is often  added in pairs of triplets not yet hit, then the “critical status” must be updated. But the other cells in the pair/pairs/triplets remain free for more additions.

 

When a clue is added in cells released after a previous assignment, then the count for the critical situation changes

 

The count changes also if the cell assigned in not the common cell in a mini row with 2 GUA2s not yet hit;

 

And if T1 is empty, any cell must be tried,

 

Final check

 

If the expected count in band 3 is reached with an exhausted file of known UAs, The brute force must be applied.

 

As for bands 1+2, the first non valid solution (not equal to the solution grid) delivers a new UA for the band 3. Again, these new UAs are used as additional filters. The validity of such UAs  is limited to a given band, but when cells have to be added in field2 (which seems frequent in solution grids having 17 clues puzzles), this can play a key role