Search of 17 clues puzzles in a solution grid

 

P Band 3 process “part 2”

 

This chapter starts with a call to the process of a band 3 in  the following conditions:

 

Bands 1+2 (XY) is valid (unique solution) against the gangster of the band3.

Valid GUAs for the XY have been extracted and applied to the studied band 3

We named

           “field1” all band3 cells belonging to the set of GUA2s GUA3s

           “filed2” the other cells in band 3.

The minimum number of clues coming out of GUA2s GUA3s is <= 6 the number of clues expected in band3.

Band3 UAs and GUA4s GUA6s have been split in

T1” T2” ,

The first  (T1) for UAs having one or more cells in “field 1”

The other (T2) for UAs having no cell in “field1”

We defined as “critical”  A situation where the minimum number of clues is equal to the expected number of cells to assign in band 3

The situation is “critical at the start” if still valid GUA2s GUA3s have at the very beginning the expected number of clues (6).

 

P1 partial “critical status”

 

Even if the band 3 is not globally “critical”, a stack can be in critical status. This is when the stack would have a minimum of 6 clues with GUA2s GUA3s.

 

In a “stack critical status “,

In a mini row with 2 pairs, the common cell can be assigned

The field 2 can be reduced. No cell can be added in the stack.

 

 

P 2  Distribution of the clues not in GUA2s GUA3s

 

For a better understanding of the choices made, it’s good to have in mind the weight of GUA2s GUA3s in the process

 

The following data give an average view for an entry out of a sample of 10 000 entries with an average 13 bands per entry. The sample is spread over the first 350 bands (out of 416). The last bands have a minor contribution in volume, likely a very big XY count and an average number of bands 3 below 2 per entry.

 

The  average result per entry was the following

 

97042   bands 1+2                     producing

342069 bands 3                          average 3.5 bands 3 per “XY” far below the 13 average number of bands3

 

326056  bands 3 remained after the test “critical with no UA in field 2”

 

146854        45.04%        in “critical status” at the start

119838        36.75%        with 5clues in GUA2sGUA3s          1 clue missing

46974          14.41%        with 4 clues/2 clues missing

10798           3.31%        with 3clues/3clues missing

 

And less than 0.5% for the rest, with average three bands3 having no GUA2 GUA3.

 

P 3 Applying the general strategy

 

As said earlier, the general strategy is to keep for the last steps the critical status.

 

If we have no clue in GUA2s GUA3s, we have a special process. T1 is empty, T2 has good chances to have many GUA4s GUA6s.

 

“critical status at the start” is a special case of the most general situation “ending in critical situation” after other assignments.

 

Other assignment will be done in priority in field 2 hitting smallest UAs of T2 in priority.

If  T2 becomes empty (all UAs in T2 hit) after assignments in field2, then missing clues to reach the “critical situation” must be taken in field 1. This is called the sub critical situation. This status is the more complex and will be seen after .

 

One clue missing is a special case. To have an assignment in “field 2” ,  all UAs in T2 must be hit and we can’t have a sub critical status except if T2 is empty. If T2 is empty, then any cell of “field 2” can be assigned and  the sub critical status must be considered as well.

 

I don’t have stats, but if more clues are missing, T2 is bigger, so we have nearly no chance to enter in sub critical mode with more than 2 clues missing.

 

In all cases, if T2 is or becomes empty, all the field 2 can be used and the subcritical mode is applied at the end.

 

So in “part 2” the process starts in one of three mode

 

No clue in GUA2s GUA3s

Missing clues in GUA2s GUA3s

“critical” with all clues in GUA2s GUA3s

 

Except for the first case, the process last steps are always in “critical mode”,  and if an “empty T2” condition appears before the “critical “ status, a “sub critical phase “can take place in the middle. The “sub critical phase outlet is always a “critical status”.

 

The comments cover the process starting with “the critical status” and going upstream to the assignment of clues in field 2.  The first situation, “no clue in GUA2s GUA3s”  comes after. For practical reasons (the most delicate process needing more checking) the sub critical phase is described at the end.

 

P 4 Critical “status”.

 

The process for the “critical status” is called directly in about 45% of the  bands 3 processed. It can be called later either directly from the assignment of cells in field 2 or from a “sub critical” phase.

 

The common status at entry is done of

 

Assigned cells at entry (known_b3), an empty 27 bits field if we start in critical mode

The current  situation for GUA2s GUA3s. Described in a G17TB3GO structure.

 

 

Assignment of cells in field 2 does not change the G17TB3GO so, unless a “sub critical phase took place”, the process when the “critical status” is called is identical to the call at the very beginning with a known_b3 not empty.  The active_b3 status is here the field 1

 

 If the process is called from a sub critical mode, several things happened

 

At least one checks of UAs in T1 has been done

The G17TB3GO has been modified during the assignment process

The known_b3 is not empty.

And we can have dead cells coming out of upstream previous “trial”. The active_b3 status is supplied by the calling sequence

 

P 4.1 Global multiple solution in “critical status”

 

As said in the overview, usually, if one digit is assigned in a GUA2 or in a GUA3 the other one will come in the brute force, so, in fact, the second one is redundant and assigning both will not reduce the number of solutions of the brute force.

 

This is usually true for the entire “critical situation”, so checking a solution where all field 1 is assigned can clear in bloc the critical solution. (no 17 clue)

 

As some GUA2s GUA3s can be assigned using UAs in T1 or other properties in a cheap way (see below) the compulsory assignments are made first, increasing the chances to find a global multiple solution.

 

If the solution is unique at the start, the brute force can be restarted after each “trial”, again assigning first the new compulsory cells

 

Note: the brute force here has many special properties.

The bands 1+2 have a unique solution against the gangster in band 3, so if the given in band 3 have the same gangster, bands 1+2 will have a solution.

If one fill of another gangster is tested giving 0/#0 solution, all other fills of the same gangster will give the same result.

A special brute force using such properties should be considered to optimize the results. This is not done here.

 

P4.2 assignment in a critical situation

 

When a cell is assigned in critical mode, the corresponding mini row can not receive another UA except for mini rows with 3 pairs.

 

If the mini row has  2 GUA2s then as the minimal count is set to 1 the common cell must be assigned. This is the first compulsory assignment;

 

Assignment in sub critical mode is more complex.

 

The “active_b3” status is updated at each assignment.

 

P 4.3 Assigning a single cell for a UA in T1

 

The main compulsory assignment comes from UAs in T1.

 

In the “critical situation”, we can have UAs in T1 hit by only one cell belonging to the current “active_b3”, the updated situation of “field 1”. The single cell is assigned, changing the “active_b3” status.

 

Then, another UA can appear with one or no cell in “active_b3”.

 

And if a UA of T1 has no cell in “active_b3” we have a dead branch.

 

Each time a cell has been assigned,  the loop can be restarted with remaining UAs.

 

This gives a loop asynchronous toward the main process. The loop is halted when a cycle is made with no assignment or if all UAs have been hit.

 

During the process, UAs not yet hit are copied to a new table located just after the current one.

 

 

P 4.4 General process to solve the critical status

 

The general process in critical status is relatively clear.

 

a) Do as many compulsory assignments as possible

b) Check the global situation using the brute force, exit if multiple

 

In a very small number of cases, the global control will give a unique solution so we have  to continue with 2 cases

 

If T1 is not yet empty

           Make a “trial” on the lowest count UA_T1 or GUA

           restart steps a) b) in the new branch 

If T1 is empty, Make a “trial” on GUA2s GUA3s

 

 Note: as the brute force remains a costly process, optimization of the calls to the brute force can be tried later. In the released code, the first call  is done after a first pass in the T1 table, a test prevents to restart later a brute force with the same set of cells.

 

A new call to the brute force (out of the final test when a 17 clues is reached) is done

 

If  more assignments are done in the T1 loop at the start

After a “trial” and following compulsory assignment.

 

P 5 Add 1 to 5 clues in field 2

 

Note the code released here will be reviewed on 2 main points

The T2 table will be reduced at each step as in the critical mode

The case T2 empty (or becoming empty) will be simplified

 

The process applied to add clues in field 2 is relatively simple

 

Take the smallest UA in T2, or the full field 2 if T2 is empty

Reduce the count to active  cells and start a “trial” on the set of cells, calling the next step

If T2 is empty, call the sub critical process to select the cell to add in field 1

 

In all cases, active cells is the field 2 reduced to the stacks not yet in critical status (<=6 clues including the clues reserved for the critical status). Each assignment can create a new critical stack, so the active cells status is updated along the process.

 

The first active status is the same for any number of cells to add, It is worked out before the call to the appropriate process.

 

Adding one clue is special just because all UAs must be hit. Only cells hitting all UAs in T2 are used.

 

A global brute force call is done when less than 3 cells must be added. No test has been done so far to see whether this is good for the performance.

 

 

P 6 No GUA2 GUA3

 

Having no GUA2 GUA3, the T2 table contains all UAs of the band 3 plus GUA4sGUA6s.

This happens with an extremely low frequency, so the main target is to have a reliable code

 

The code is a classical “band expansion” with always the limit of 6 clues per stack allowing a reduction in the cells to use .

 

The process is done in recursive mode

 

When conditions seem good and anyway before the last step, a global brute force is done. Again, no test have been done to see if this has a positive effect.