Search of 17 clues puzzles in a solution grid
P Band 3 process “part 2” continued
P 7 Sub critical status
In the process, the sub critical status comes usually after assignments in field 2. But it can be called directly if T2 the table of UAs fully located in field 2 is empty.
In all cases, T2 is either empty or fully hit by the assignments done in field 2
At the entry in this mode
Assigned cells at entry (known_b3), reflects previous assignments if any
The current situation for GUA2s GUA3s. Described in a G17TB3GO structure is identical to the start status
And the T1 table is in the start status, as well.
In the sub critical status, the target is to add clues keeping as many as possible GUA2s GUA3s before a call of the critical status.
P 7 1 Global brute force in the sub critical steps
We have seen in the critical chapter that the brute force applied to already known clues plus all pending GUA2s GUA3s (“field 1”)gave very often a multiple solution.
In the “critical status”, compulsory clues were first searched.
Here, we have less GUA2s GUA3s (much less if missing clues have been assigned in “field 2”) Searching compulsory clues creates confused situations for the expected process, so the brute force is immediately applied to “known clues + field 1”). As far as I can see, less than 1/1000 of the calls will give a unique solution.
P 7.1 General Strategy applied in the sub critical steps
Clues must be added in stacks where we have room for more clues. This is a reduced “field 1” first worked out in active_sub, a 27 bits field.
Adding the first clue is done in a very simple way. One mini row is entirely solved in all possible ways with one clue added. We can have one of the following cases.
1 GUA2 in the mini row both cells assigned
2 GUA2s in the mini row This is counted as one for the “critical status”. 2 of the 3 cells are assigned, one cell remains free for later use
3 GUA2s in the mini row the three cells are assigned (counted as 2 in the “critical status”)
1 GUA3 in the mini row 2 of the 3 cells assigned 1 free for later use
Doing so, the “critical count” is reduced by 1 or 2, the global count increased by one, and the stack status is updated.
If more than one clue must be added, the next loop will be very similar.
We can have a mini row with still one free clue (normally the last one) and no GUA2 GUA3.
Assuming that the first loop covers in sequence the 9 mini rows, it’s enough to avoid redundancy to restart with the same index (one free cell alone).
And if all clues have been added, the “critical” step in entered.
Q brute force uses
I just open the chapter, the brute force use in this program is worth efforts to improve efficiency.
Brute force appears everywhere in the program, for various tasks.
A 2 bands brute force is intensively used to produce UAs and GUAs at the start.
At the start as well a 1 band brute force is used to produce UAs with more than 5 digits of special kinds.
For each XY passing filters, a 2 band brute force is called to verify the uniqueness, producing a new UA if the XY has more than one solution.
And the classical 3 bands brute force is applied in “part 2”
Mainly in a global form (with clues in excess in band 3),
For the final check when a 17 clues puzzle is produced. In this case, a new UA can appear as for a XY. It is in the code, but with a poor coding.
All the brute force in the program is derived from the code proposed by zhouyundong_2012 a member of the New Sudoku Player’s Forum. Special versions of the code have been written for the 2 bands 1 band cases and specific guess sequences have been done to optimize each of the previous tasks.
The optimization of the 3 bands brute force is the specific conditions found here is in the to do list. The comments on the brute force will be done after, for all uses of the brute force.
Q 1 Optimization to do in the band 3 process
In this program, the full brute force is applied after the check that the XY has a unique solution against the “double gangster” of the bands 1+2.And the clues in bands 1+2 are stable during the “part 2” process for all the bands 3 still valid. Last but not least, a huge majority of the calls are done with all valid GUA2s GUA3s in band 3, and we know that in most cases, the puzzle still has more than one solution.
All this open the door for some optimization of the process. We have one evidence, if guesses are done in priority for the band 3 and if the band 3 is solved “equal to the studied band3”, we have the valid solution. More can be done inside the limits of the XY using gangsters.