The New Sudoku Players' Forum

[P.O.]

this puzzle is from one i found in an old post from the forum, to which i applied some permutations and relabeling; it is solvable in two steps; the shortest-depth first path from my algorithm is 40 chains with depth <= 3.

Code: Select all

. 3 .   . . 7   9 . .
. . .   4 . .   . . 8
6 . 5   . 1 .   . 4 .
2 . 7   . 3 .   . . .
. . 1   5 4 .   . . .
. . .   . . .   . . .
. . .   . . .   . 8 .
. . 3   9 2 .   . . 7
. 4 .   . . 1   6 . .

.3...79.....4....86.5.1..4.2.7.3......154....................8...392...7.4...16..


[yzfwsf]

Almost Locked Set XZ-Rule: A=r8c128 {1568},B=r279c3 {2689}, X=68, Z=/ => r8c7<>1 r1c3<>2 r8c6<>5 r8c7<>5 r7c2<>6 r9c1<>8 r6c3<>9 ;stte

[jco]

Almost Locked Set XZ-Rule: A=r8c128 {1568},B=r279c3 {2689}, X=68, Z=/ => r8c7<>1 r1c3<>2 r8c6<>5 r8c7<>5 r7c2<>6 r9c1<>8 r6c3<>9 ;stte

Nice and powerful ALS-xz move!
An alternative way to see this move starts with the fact that (6)r7c3 == (8)r9c3
(guardians that avoid having three 29s in c3). Then,

Code: Select all

.------------------------------------------------------------------.
|  148    3         48-2| 268   568  7     | 9      1256    1256   |
|  179    1279    B(29) | 4     569  23569 | 12357  123567  8      |
|  6      2789      5   | 238   1    2389  | 237    4       23     |
|-----------------------+------------------+-----------------------|
|  2      5689      7   | 168   3    689   | 145    1569    14569  |
|  389    689       1   | 5     4    2689  | 237    23679   2369   |
|  3459   59-6      46-9| 1267  679  269   | 8      123569  123569 |
|-----------------------+------------------+-----------------------|
|  1579   12579-6 B(269)| 367   567  3456  | 12345  8       123459 |
|A(158) A(1568)     3   | 9     2    468-5 | 4-15 A(15)     7      |
|  579-8  4       B(289)| 378   578  1     | 6      2359    2359   |
'------------------------------------------------------------------'

Code: Select all

(8)r9c3 - (8=156)r8c128 - (6=2|9)r7c3
||                                                  Loop
(6)r7c3 - (6=158)r8c128 - (8=29)r29c3 - (2|9=6)r7c3

(same eliminations)

[denis_berthier]

this puzzle is ... is solvable in two steps; the shortest-depth first path from my algorithm is 40 chains with depth <= 3.

Hi P.O.
I don't know how you count depth, but I think you must be counting the application of any Subset as depth +1, because with no Subsets embedded in chains, length 5 is required. Could you write a few of these 40 chains with depth = 3 in the nrc notation?
If you de-activate Subsets in your algorithm, I bet you need depth 5.

As for the number of steps (your 40 chains), it is not an intrinsic property of a puzzle. In DFS, it highly depends on the order candidates are tested. In my simplest-first strategy, I find only 10 chains (of lengths ≤ 5). But, still in W5, there is a solution with only 1 step.

Code: Select all

Resolution state after Singles and whips[1]:
   +----------------------+----------------------+----------------------+
   ! 148    3      248    ! 268    568    7      ! 9      1256   1256   !
   ! 179    1279   29     ! 4      569    23569  ! 12357  123567 8      !
   ! 6      2789   5      ! 238    1      2389   ! 237    4      23     !
   +----------------------+----------------------+----------------------+
   ! 2      5689   7      ! 168    3      689    ! 1458   1569   14569  !
   ! 389    689    1      ! 5      4      2689   ! 2378   23679  2369   !
   ! 34589  5689   4689   ! 12678  6789   2689   ! 12358  123569 123569 !
   +----------------------+----------------------+----------------------+
   ! 1579   125679 269    ! 367    567    3456   ! 12345  8      123459 !
   ! 158    1568   3      ! 9      2      4568   ! 145    15     7      !
   ! 5789   4      289    ! 378    578    1      ! 6      2359   2359   !
   +----------------------+----------------------+----------------------+
224 candidates.

1) SIMPLEST-FIRST SOLUTION:

Code: Select all

biv-chain[2]: r3n9{c2 c6} - c5n9{r2 r6} ==> r6c2≠9
biv-chain[2]: r8n6{c6 c2} - c3n6{r7 r6} ==> r6c6≠6
z-chain[4]: r2c3{n2 n9} - c5n9{r2 r6} - r6n7{c5 c4} - c4n2{r6 .} ==> r2c6≠2
whip[5]: r8n8{c2 c6} - r8n6{c6 c2} - c3n6{r7 r6} - c3n8{r6 r1} - c3n4{r1 .} ==> r9c1≠8
whip[5]: c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - r8n8{c2 c6} - r8n6{c6 .} ==> r7c2≠6
whip[5]: r2c3{n2 n9} - r9c3{n9 n8} - r8n8{c2 c6} - r8n6{c6 c2} - r7c3{n6 .} ==> r1c3≠2
whip[5]: r2c3{n9 n2} - r9c3{n2 n8} - r8n8{c2 c6} - r8n6{c6 c2} - b4n6{r4c2 .} ==> r6c3≠9
whip[5]: c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - r8n8{c2 c6} - c6n4{r8 .} ==> r7c6≠6
whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠5
whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠4
stte

2) 1-STEP 1-ELIMINATION SOLUTIONS:
There are 1-step solutions which eliminate only one candidate per step, but they use absurdly long chains for a puzzle in W5:

Code: Select all

whip[10]: r6n4{c3 c1} - r1n4{c1 c3} - c3n8{r1 r9} - r8n8{c2 c6} - c6n4{r8 r7} - c6n5{r7 r2} - c6n3{r2 r3} - r3n9{c6 c2} - b4n9{r6c2 r5c1} - c1n3{r5 .} ==> r6c3≠6
stte

Code: Select all

whip[11]: c3n6{r7 r6} - r6n4{c3 c1} - r1n4{c1 c3} - c3n8{r1 r9} - r8n8{c2 c6} - c6n4{r8 r7} - c6n5{r7 r2} - c6n3{r2 r3} - r3n9{c6 c2} - b4n9{r6c2 r5c1} - c1n3{r5 .} ==> r8c2≠6
stte

3) SIMPLEST 2-STEP SOLUTION, unique one in W5, which happens to be 1-step with 2 eliminations:

Code: Select all

whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠5, r8c6≠4
stte

[DEFISE]

3) SIMPLEST 2-STEP SOLUTION, unique one in W5, which happens to be 1-step with 2 eliminations:

Code: Select all

whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠5, r8c6≠4
stte

Hi Denis,
My “Few Steps” solver found two identical whips [5] of target 4r8c6 and 5r8c6 (The ones you gave in your Simplest-first path). So I concluded like you that a single whip could be enough to eliminate the 2 candidates.

But I have a remark:
your solver directly gave this multi-target t-whip
t-whip[4]: c1n2{r9 r8} - c4n2{r8 r2} - r2n6{c4 c1} - c1n5{r2 .} ==> r9c1≠4, r9c1≠3, r9c1≠1
in the Simplest-first path of the Cobra Roll puzzle.
cobra-roll-t39294.html#p308720

Why your solver doesn't give this multi-target whip below in the Simplest-first path of this Puzzle 7 ?
whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠5, r8c6≠4

[denis_berthier]

3) SIMPLEST 2-STEP SOLUTION, unique one in W5, which happens to be 1-step with 2 eliminations:

Code: Select all

whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠5, r8c6≠4
stte

My “Few Steps” solver found two identical whips [5] of target 4r8c6 and 5r8c6 (The ones you gave in your Simplest-first path). So I concluded like you that a single whip could be enough to eliminate the 2 candidates.
But I have a remark:
your solver directly gave this multi-target t-whip
t-whip[4]: c1n2{r9 r8} - c4n2{r8 r2} - r2n6{c4 c1} - c1n5{r2 .} ==> r9c1≠4, r9c1≠3, r9c1≠1
in the Simplest-first path of the Cobra Roll puzzle.
cobra-roll-t39294.html#p308720

Why your solver doesn't give this multi-target whip below in the Simplest-first path of this Puzzle 7 ?
whip[5]: r8n6{c6 c2} - c3n6{r7 r6} - c3n4{r6 r1} - c3n8{r1 r9} - b8n8{r9c4 .} ==> r8c6≠5, r8c6≠4

Good remark.

Whips don't have several targets. I could write a version with possibly multiple targets, but this happens so rarely when these whips are not t-whips that it would be globally very counter-productive when the only goal is to solve the puzzle with the simplest patterns (the original raison d'être of CSP-Rules). When two equivalent whips eliminate two candidates, I manually fuse them into one for publication.

T-whips may have several targets (if their "blocked version" is chosen), but t-whips are not compatible with my 1-step, 2-step or fewer-steps functions, because these functions require focusing on targets.
Note that all these functions are recent additions to SudoRules and they correspond to an approach that is radically opposed to the goal of finding a pattern-based solution. All these functions rely on finding anti-backdoors or anti-backdoor pairs and they are derived forms of T&E. In spite of several people regularly posting such solutions, the sheer numbers of a priori possibilities prove that very few of these solutions can be found manually.

Finally, why focusing on targets doesn't work for t-whips is a matter of both pure logic and coding:
- as a direct expression of their common logical structure (as explained in the [BUM] graphics) and for global efficiency reasons of pattern-matching in CLIPS, the implementation of partial-whips is shared between t-whips and whips;
- for reasons of coding efficiency of the focus function (which is called many times in the 1-, 2- or fewer- step functions), the focus restrictions are put on the partial-whips (and this would not imply the correct restrictions for t-whips).

[P.O.]

Could you write a few of these 40 chains with depth = 3 in the nrc notation?

hi Denis,
the depth count start at 0 but the links are counted from 1 so depth n gives at least a count of n+1 links; also only the rlc is output by the solver except at depth 0 where the first link is a llc; the others llc are found with the help of the 'code'.
here are four chains of depth 3: two with triplet, one without subset and the last one with singles from pair.

Code: Select all

148     3       248     268     568     7       9       1256    1256             
179     1279    29      4       569     3569    12357   123567  8               
6       2789    5       238     1       2389    237     4       23               
2       5689    7       168     3       689     1458    1569    14569           
389     689     1       5       4       2689    2378    23679   2369             
34589   568     4689    12678   6789    289     12358   123569  123569           
1579    125679  269     367     567     3456    12345   8       123459           
158     1568    3       9       2       4568    145     15      7               
5789    4       289     378     578     1       6       2359    2359             

chain n°: 6  depth: 3  candidate: 6  from cell
(((7 6 8) (3 4 5 6)))

((6 0) (7 3 7) (2 6 9))
((6 0) (6 3 4) (4 6 8 9))                            c3n6{r7 r6}
((9 1 2 62) ((4 2 4) (5 6 8 9)) ((5 2 4) (6 8 9)))   c2{r4r5r6}{n5n8n9}
((9 2 14) (3 6 2) (2 3 8 9))                         r3n9{c2 c6}
((6 3 2 62) ((4 6 5) (6 8 9)) ((5 6 5) (2 6 8 9)))   c6{r4r5r6}{n2n6n8}


c3n6{r7 r6} - c2{r4r5r6}{n5n8n9} - r3n9{c2 c6} - c6{r4r5r6}{n2n6n8} => r7c6 <> 6
when r6c3 is set to 6 a triplet (589)(89)(58) is found at c2{r4r5r6} which gives three distinct links at the same depth of 1: (5)()(5) - (8)(8)(8) - (9)(9)(). the last one becomes a rlc for this chain.

Code: Select all

148     3       248     268     568     7       9       1256    1256             
179     1279    29      4       569     3569    12357   123567  8               
6       2789    5       238     1       2389    237     4       23               
2       5689    7       168     3       689     1458    1569    14569           
389     689     1       5       4       2689    2378    23679   2369             
34589   568     4689    12678   6789    289     12358   123569  123569           
1579    125679  269     367     567     345     12345   8       123459           
158     1568    3       9       2       4568    145     15      7               
5789    4       289     378     578     1       6       2359    2359             

chain n°: 7 depth: 3  candidate: 5  from start
 
((6 0) (8 2 7) (1 5 6 8))                                           
((6 0) (8 6 8) (4 5 6 8))                                             r8n6{c2 c6}
((9 1 2 62) ((4 6 5) (6 8 9)) ((5 6 5) (2 6 8 9)) ((6 6 5) (2 8 9)))  c6{r4r5r6}{n2n8n9}
((9 2 14) (3 2 1) (2 7 8 9))                                          r3n9{c6 c2}
((5 3 2 62) ((4 2 4) (5 6 8 9)) ((6 2 4) (5 6 8)))                    c2{r4r5r6}{n5n6n8}


r8n6{c2 c6} - c6{r4r5r6}{n2n8n9} - r3n9{c6 c2} - c2{r4r5r6}{n5n6n8} => r8c2 <> 5
same analysis.

Code: Select all

148     3       48      268     568     7       9       1256    1256             
179     127     29      4       569     3569    12357   123567  8               
6       2789    5       238     1       2389    237     4       23               
2       5689    7       168     3       689     1458    1569    14569           
39      689     1       5       4       2689    2378    23679   2369             
3459    568     4689    12678   6789    289     12358   123569  123569           
1579    1257    269     367     567     345     12345   8       123459           
158     16      3       9       2       4568    145     15      7               
5789    4       289     378     578     1       6       2359    2359             

chain n°: 13  depth: 3  candidate: 3  from start
 
((7 0) (5 8 6) (2 3 6 7 9))
((7 0) (5 7 6) (2 3 7 8))                            r5n7{c8 c7}
((7 1 1) (3 2 1) (2 7 8 9))                          r3n7{c7 c2}
((9 2 2 11) ((4 2 4) (5 6 8 9)) ((5 2 4) (6 8 9)))   c2n9{r3 r4r5}
((3 3 20) (5 1 4) (3 9))                             r5c1{n9 n3}


r5n7{c8 c7} - r3n7{c7 c2} - c2n9{r3 r4r5} - r5c1{n9 n3} => r5c8 <> 3
no subset here.

Code: Select all

48     3      48     2      56     7      9      156    156             
19     17     2      4      569    35     357    567    8               
6      79     5      8      1      39     237    4      23             
2      5689   7      16     3      689    1458   1569   4569           
3      689    1      5      4      2689   278    2679   269             
49     568    46     167    789    28     12358  1235   1256           
157    2      69     367    57     45     1345   8      13459           
158    16     3      9      2      4568   145    15     7               
57     4      89     37     578    1      6      2359   2359

chain n°: 40  depth: 3  candidates: (9)  from start
 
((7 0) (6 5 5) (7 8 9))
((7 0) (6 4 5) (1 6 7))         r6n7{c5 c4}
((6 1 22) (7 4 8) (3 6 7))    [ r9c4{n7 n3} ] - r7c4{n3 n6}
((8 2 22) (9 3 7) (8 9))      [ r7c3{n6 n9} ] - r9c3{n9 n8}
((8 3 1) (6 5 5) (7 8 9))       c5n8{r9 r6}


r6n7{c5 c4} - [ r9c4{n7 n3} ] - r7c4{n3 n6} - [ r7c3{n6 n9} ] - r9c3{n9 n8} - c5n8{r9 r6} => r6c5 <> 9
written this way the chain has length six but in fact the two links in bracket are not part of the chain.
at depth 0 when r6c4 is set to 7 r7c4 become (36) and r9c4 become (3) that is a set with 2 candidates for two cells which upon analysis gives two links: 3 in r9c4 and 6 in r7c4: these two links are put in the stack of next links with the same depth of 1 and only one becomes a rlc for this chain.
it is the same analysis for the next link: a set of two candidates for two cells (9) (89) that gives two links at the same depth of 2.
so a set of length n gives always n distinct links that can become rlc for n distinct chains.
the same analysis can be applied to the forty chains of this resolution path, this puts the chain maximum length at 4.