## Fully supersymmetric chains

Advanced methods and approaches for solving Sudoku puzzles

### Re: Fully supersymmetric chains

yzfwsf wrote:I found that the search cost of g-whip is much larger than that of whip. I wonder if SudoRules has the same situation. Searching for g-whip of the same length usually traverses many times more nodes than searching for equal-length whip.

Right. Which is not surprising: as the number of possible right-linking objects in increased, so is the number of left to right extensions.
That's one of the reasons why, when g-whips are active, I always print the numbers of candidates and g-candidates.
That's also the main reason why I haven't chosen to consider g-candidates as candidates for additional CSP-Variables (which would be an obvious theoretical step). Whips (that can be considered as g-Singles) would become mere Singles. But that would IMO blur a fundamental difference in complexity.

Now, in which proportions the numbers are increased is totally puzzle dependent.
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re: Fully supersymmetric chains

Mauricio's sample puzzle
Code: Select all
`........1.2...3.4...4.5.3......3.1....67...8..7...2..5..78..9...4..1..2.8....6...`

Code: Select all
`Whip: Supposing 6r1c4 would causes 4 to disappear in Column 4 => r1c4<>66r1c4 - 6c5(r2=r6) - r6c7(6=4) - r5c7(4=2) - 2r1(c7=c5) - r7c5(2=4) - r7c6(4=5) - 5c4(r9=r4) - 4c4(r4=.)Whip: Supposing 9r1c5 would causes 4 to disappear in Box 9 => r1c5<>99r1c5 - r5c5(9=4) - r5c7(4=2) - 2r1(c7=c4) - 4c4(r1=r9) - r7c5(4=2) - 2c1(r7=r4) - 4r4(c1=c9) - 4b9(p3=.)Whip: Supposing 5r4c1 would causes 4 to disappear in Row 4 => r4c1<>55r4c1 - 5r5(c2=c6) - r7c6(5=4) - r7c5(4=2) - 2r9(c4=c3) - 2r4(c3=c9) - 7r4(c9=c8) - 6r4(c8=c4) - 4r4(c4=.)Whip: Supposing 9r5c1 would causes 4 to disappear in Box 9 => r5c1<>99r5c1 - r5c5(9=4) - r7c5(4=2) - 2c1(r7=r4) - 4r4(c1=c9) - r5c7(4=2) - 2r1(c7=c4) - 4c4(r1=r9) - 4b9(p7=.)g-Whip: Supposing 9r4c8 would causes 4 to disappear in Row 4 => r4c8<>99r4c8 - 7r4(c8=c9) - 6r4(c9=c4) - 5c4(r4=r89) - r7c6(5=4) - r7c5(4=2) - 2r9(c4=c3) - 2r4(c3=c1) - 4r4(c1=.)g-Whip: Supposing 9r4c9 would causes 4 to disappear in Row 4 => r4c9<>99r4c9 - 7r4(c9=c8) - 6r4(c8=c4) - 5c4(r4=r89) - r7c6(5=4) - r7c5(4=2) - 2r9(c4=c3) - 2r4(c3=c1) - 4r4(c1=.)Hidden Pair: 39 in r5c9,r6c8 => r5c9<>24,r6c8<>6Whip: Supposing 6r3c9 would causes 7 to disappear in Box 6 => r3c9<>66r3c9 - 2c9(r3=r4) - r5c7(2=4) - r5c5(4=9) - 9c9(r5=r2) - r3c8(9=7) - 7b6(p2=.)Whip: Supposing 9r6c1 would cause cell r7c5 to be empty => r6c1<>99r6c1 - 9b6(p8=p6) - r5c5(9=4) - 4b4(p4=p1) - 4r6(c1=c7) - r5c7(4=2) - 2c1(r5=r7) - r7c5(2=.)Whip: Supposing 3r8c9 would causes 4 to disappear in Column 4 => r8c9<>33r8c9 - 3c4(r8=r9) - 3c8(r9=r6) - r5c9(3=9) - r5c5(9=4) - r5c7(4=2) - 2c9(r4=r3) - 2c4(r3=r1) - 4c4(r1=.)Whip: Supposing 3r5c1 would causes 4 to disappear in Box 9 => r5c1<>33r5c1 - r5c9(3=9) - r5c5(9=4) - r7c5(4=2) - 2c1(r7=r4) - 2r5(c1=c7) - 2r1(c7=c4) - 4c4(r1=r9) - 4r4(c4=c9) - 4b9(p3=.)Whip: Supposing 7r1c8 would causes 4 to disappear in Box 4 => r1c8<>77r1c8 - 7r4(c8=c9) - 2b6(p3=p4) - 4b6(p4=p7) - 6b6(p7=p2) - r3c8(6=9) - 9c9(r2=r5) - r5c5(9=4) - r7c5(4=2) - 2c1(r7=r4) - 4b4(p1=.)Whip: Supposing 3r7c9 would cause cell r5c7 to be empty => r7c9<>33r7c9 - 3r5(c9=c2) - 3r6(c3=c8) - 9b6(p8=p6) - r5c5(9=4) - r7c5(4=2) - 2r9(c4=c3) - 3r9(c3=c4) - 4c4(r9=r1) - 2r1(c4=c7) - r5c7(2=.)Whip: Supposing 7r9c8 would causes 4 to disappear in Box 4 => r9c8<>77r9c8 - 7r4(c8=c9) - 2b6(p3=p4) - 4b6(p4=p7) - 6b6(p7=p2) - r3c8(6=9) - 9c9(r2=r5) - r5c5(9=4) - r7c5(4=2) - 2c1(r7=r4) - 4b4(p1=.)Whip: Supposing 6r7c8 would cause cell r7c9 to be empty => r7c8<>66r7c8 - 1c8(r7=r9) - 3b9(p8=p9) - 3r5(c9=c2) - 3r7(c2=c1) - 3r6(c1=c8) - 9b6(p8=p6) - r5c5(9=4) - r5c7(4=2) - 2c1(r5=r4) - 4r4(c1=c9) - r7c9(4=.)Whip: Supposing 6r2c9 would causes 4 to disappear in Box 4 => r2c9<>66r2c9 - 6c8(r3=r4) - r6c7(6=4) - r5c7(4=2) - 2c9(r4=r3) - 9c9(r3=r5) - r5c5(9=4) - r7c5(4=2) - 2c1(r7=r4) - 4b4(p1=.)Whip: Supposing 5r9c8 would causes 6 to disappear in Box 5 => r9c8<>55r9c8 - 1c8(r9=r7) - 3c8(r7=r6) - 3r5(c9=c2) - 3r7(c2=c1) - 3r8(c3=c4) - 5c4(r8=r4) - 5r5(c6=c1) - 2c1(r5=r4) - 4b4(p1=p7) - r6c7(4=6) - 6b5(p8=.)Whip: Supposing 5r1c3 would causes 3 to disappear in Box 1 => r1c3<>55r1c3 - 5c8(r1=r7) - 1c8(r7=r9) - 3c8(r9=r6) - 3r5(c9=c2) - 3r7(c2=c1) - 3b1(p1=.)Whip: Supposing 6r8c9 would cause cell r7c8 to be empty => r8c9<>66r8c9 - r7c9(6=4) - r7c6(4=5) - 5c4(r9=r4) - 6r4(c4=c8) - 7r4(c8=c9) - r9c9(7=3) - r9c8(3=1) - r7c8(1=.)Whip: Supposing 6r3c1 would causes 6 to disappear in Box 3 => r3c1<>66r3c1 - 6r8(c1=c7) - r7c9(6=4) - r7c6(4=5) - 5c8(r7=r1) - 6b3(p2=.)Whip: Supposing 5r1c7 would causes 1 to disappear in Box 9 => r1c7<>55r1c7 - 5c8(r1=r7) - r7c6(5=4) - r7c5(4=2) - 2r1(c5=c4) - 4b2(p1=p2) - r5c5(4=9) - r5c9(9=3) - 3c8(r6=r9) - 1b9(p8=.)Whip: Supposing 5r1c2 would causes 4 to disappear in Box 2 => r1c2<>55r1c2 - 5c8(r1=r7) - r7c6(5=4) - r7c9(4=6) - 6r8(c7=c1) - 5c1(r8=r5) - 2r5(c1=c7) - 4r5(c7=c5) - r7c5(4=2) - 2r1(c5=c4) - 4b2(p1=.)Whip: Supposing 9r6c4 would causes 1 to disappear in Box 5 => r6c4<>99r6c4 - 9b6(p8=p6) - 3r5(c9=c2) - 3r6(c3=c8) - r9c8(3=1) - r7c8(1=5) - 5r1(c8=c1) - 5r5(c1=c6) - 1b5(p6=.)Whip: Supposing 6r3c4 would causes 2 to disappear in Row 3 => r3c4<>66r3c4 - 6c5(r2=r6) - 8r6(c5=c3) - 9r6(c3=c8) - 3r6(c8=c1) - 1r6(c1=c4) - r2c4(1=9) - 9b3(p6=p9) - 2r3(c9=.)Whip: Supposing 9r2c5 would cause cell r6c4 to be empty => r2c5<>99r2c5 - r5c5(9=4) - r5c7(4=2) - 2c9(r4=r3) - r3c4(2=1) - r2c4(1=6) - r6c4(6=.)Whip: Supposing 9r4c4 would cause cell r6c4 to be empty => r4c4<>99r4c4 - r5c5(9=4) - r5c7(4=2) - 2c9(r4=r3) - r3c4(2=1) - r2c4(1=6) - r6c4(6=.)Whip: Supposing 9r6c3 would cause cell r9c8 to be empty => r6c3<>99r6c3 - 9r4(c2=c6) - 9r5(c5=c9) - 3c9(r5=r9) - 3c4(r9=r8) - r8c3(3=5) - 9r8(c3=c1) - r9c2(9=1) - r9c8(1=.)Whip: Supposing 6r1c8 would causes 6 to disappear in Box 1 => r1c8<>66r1c8 - r4c8(6=7) - r3c8(7=9) - 9r6(c8=c5) - 6c5(r6=r2) - 8c5(r2=r1) - 8r6(c5=c3) - 8c2(r4=r3) - 6b1(p8=.)Hidden Pair: 67 in r3c8,r4c8 => r3c8<>9Whip: Supposing 5r2c7 would causes 4 to disappear in Column 4 => r2c7<>55r2c7 - r1c8(5=9) - 9r6(c8=c5) - r5c5(9=4) - r7c5(4=2) - r9c5(2=7) - r9c7(7=4) - r5c7(4=2) - 2r1(c7=c4) - 4c4(r1=.)Hidden Single: 5 in b3 => r1c8=5Hidden Single: 9 in c8 => r6c8=9Hidden Single: 3 in b6 => r5c9=3Whip: Supposing 1r3c4 would causes 6 to disappear in Box 5 => r3c4<>11r3c4 - 2r3(c4=c9) - 9c9(r3=r2) - r2c4(9=6) - r6c4(6=4) - r6c7(4=6) - 6b5(p8=.)ALS Discontinuous Nice Loop: (9=1246)r1236c4 - (6=45892)r4c12346 - r4c9 = r3c9 - (2=9)r3c4 => r13c6,r89c4<>9Hidden Pair: 79 in r8c6,r9c5 => r8c6<>5,r9c5<>24AIC Type 2: (3=5)r8c4 - (5=4)r7c6 - (4=6)r7c9 - r8c7 = 6r8c1 => r8c1<>3ALS Discontinuous Nice Loop: (5=134792)r9c245789 - (2=4)r7c5 - (4=9)r5c5 - (9=475)r9c579 => r9c3<>5Whip: Supposing 9r3c2 would causes 2 to disappear in Box 3 => r3c2<>99r3c2 - r3c4(9=2) - 2r9(c4=c3) - 9r9(c3=c5) - r5c5(9=4) - r5c7(4=2) - 2b3(p1=.)Whip: Supposing 6r7c1 would causes 4 to disappear in Row 4 => r7c1<>66r7c1 - r7c9(6=4) - r9c9(4=7) - r9c5(7=9) - r5c5(9=4) - r5c7(4=2) - 2c1(r5=r4) - 4r4(c1=.)Whip: Supposing 6r4c9 would causes 4 to disappear in Row 4 => r4c9<>66r4c9 - r7c9(6=4) - r9c9(4=7) - r9c5(7=9) - r5c5(9=4) - r7c5(4=2) - 2r9(c4=c3) - 2r4(c3=c1) - 4r4(c1=.)Hidden Single: 6 in c9 => r7c9=6Hidden Single: 6 in r8 => r8c1=6Locked Candidates 2 (Claiming): 4 in r7 => r9c4<>4ALS AIC Type 1: (4=92)r13c4 - (2=354)b8p347 => r1c6<>4ALS Discontinuous Nice Loop: 6r2c45 = r2c7 - r6c7 = r4c8 - (6=23459)r13489c4 - (9=1786)b2p3459 => r1c5,r2c7<>6AIC Type 2: (7=8)r1c6 - r4c6 = (8-6)r6c5 = 6r2c5 => r2c5<>7Discontinuous Nice Loop: 6r2c5 = r2c4 - r4c4 = r4c8 - (6=7)r3c8 - (7=8)r2c7 - (8=6)r2c5 => r2c5=6AIC Type 2: 1r5c6 = r3c6 - (1=9)r2c4 - r2c9 = (9-2)r3c9 = r4c9 - r5c7 = 2r5c1 => r5c1<>1AIC Type 2: (4=2)r5c7 - r1c7 = r3c9 - (2=9)r3c4 - (9=1)r2c4 - r6c4 = 1r5c6 => r5c6<>4AIC Type 2: (9=4)r5c5 - (4=2)r5c7 - r1c7 = r3c9 - (2=9)r3c4 - (9=1)r2c4 - r6c4 = 1r5c6 => r5c6<>9Grouped AIC Type 1: 5r2c3 = (5-7)r2c1 = r2c79 - r3c8 = (7-6)r4c8 = (6-5)r4c4 = r89c4 - r7c6 = 5r7c12 => r8c3<>5XY-Chain: (4=5)r7c6 - (5=3)r8c4 - (3=9)r8c3 - (9=7)r8c6 - (7=9)r9c5 - (9=4)r5c5 => r4c6,r7c5<>4Hidden Single: 4 in r7 => r7c6=4Naked Single: r7c5=2Hidden Single: 2 in r9 => r9c3=2Locked Candidates 2 (Claiming): 5 in r7 => r9c2<>5Locked Candidates 1 (Pointing): 5 in b8 => r4c4<>5Naked Triple: in r4c2,r4c3,r4c6 => r4c1<>9,Locked Candidates 2 (Claiming): 9 in c1 => r1c2<>9,r1c3<>9,r2c3<>9X-Wing:1c34\r26  => r26c1<>1X-Wing:9r59\c25  => r4c2<>9XY-Cycle: (8=3)r1c3 - (3=9)r8c3 - (9=7)r8c6 - (7=8)r1c6 => r6c3<>3,r3c6<>7,r1c257<>8Hidden Single: 3 in r6 => r6c1=3Hidden Single: 8 in c5 => r6c5=8Naked Single: r6c3=1Hidden Single: 1 in r2 => r2c4=1Hidden Single: 1 in r5 => r5c6=1Hidden Single: 5 in c6 => r4c6=5Hidden Single: 9 in r4 => r4c3=9Hidden Single: 8 in r4 => r4c2=8Hidden Single: 9 in r5 => r5c5=9Hidden Single: 9 in r8 => r8c6=9Hidden Single: 9 in r9 => r9c2=9Hidden Single: 1 in r9 => r9c8=1Hidden Single: 3 in r9 => r9c4=3Hidden Single: 3 in r8 => r8c3=3Hidden Single: 3 in r1 => r1c2=3Hidden Single: 6 in r1 => r1c7=6Hidden Single: 2 in r1 => r1c4=2Hidden Single: 4 in r1 => r1c5=4Full House: r9c5=7Full House: r8c4=5Hidden Single: 9 in r1 => r1c1=9Hidden Single: 7 in r1 => r1c6=7Full House: r1c3=8Full House: r2c3=5Full House: r3c6=8Full House: r3c4=9Hidden Single: 9 in r2 => r2c9=9Hidden Single: 8 in r2 => r2c7=8Full House: r2c1=7Hidden Single: 2 in r3 => r3c9=2Full House: r3c8=7Hidden Single: 6 in r3 => r3c2=6Full House: r3c1=1Hidden Single: 2 in r4 => r4c1=2Hidden Single: 7 in r4 => r4c9=7Hidden Single: 4 in r4 => r4c4=4Full House: r4c8=6Full House: r6c4=6Full House: r6c7=4Full House: r7c8=3Full House: r5c7=2Hidden Single: 4 in r5 => r5c1=4Full House: r5c2=5Full House: r7c1=5Full House: r7c2=1Hidden Single: 7 in r8 => r8c7=7Full House: r8c9=8Full House: r9c7=5Full House: r9c9=4`
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Fully supersymmetric chains

.
Code: Select all
`Resolution state after Singles and whips:   +----------------------+----------------------+----------------------+    ! 35679  35689  3589   ! 2469   246789 4789   ! 25678  5679   1      !    ! 15679  2      1589   ! 169    6789   3      ! 5678   4      6789   !    ! 1679   1689   4      ! 1269   5      1789   ! 3      679    26789  !    +----------------------+----------------------+----------------------+    ! 2459   589    2589   ! 4569   3      4589   ! 1      679    24679  !    ! 123459 1359   6      ! 7      49     1459   ! 24     8      2349   !    ! 1349   7      1389   ! 1469   4689   2      ! 46     369    5      !    +----------------------+----------------------+----------------------+    ! 12356  1356   7      ! 8      24     45     ! 9      1356   346    !    ! 3569   4      359    ! 359    1      579    ! 5678   2      3678   !    ! 8      1359   12359  ! 23459  2479   6      ! 457    1357   347    !    +----------------------+----------------------+----------------------+ 224 candidates194 g-candidates, 1339 csp-glinks and 790 non-csp glinks`

As far as I can see, SudoRules starts the same way:
Code: Select all
`whip: r5c5{n9 n4} - r7c5{n4 n2} - c1n2{r7 r4} - c1n4{r4 r6} - c7n4{r6 r9} - c4n4{r9 r1} - r1n2{c4 c7} - r5c7{n2 .} ==> r5c1≠9whip: r5c5{n9 n4} - r5c7{n4 n2} - r1n2{c7 c4} - c4n4{r1 r9} - c7n4{r9 r6} - r4n4{c9 c1} - c1n2{r4 r7} - r7c5{n2 .} ==> r1c5≠9whip: c5n6{r2 r6} - r6c7{n6 n4} - r5c7{n4 n2} - r1n2{c7 c5} - r7c5{n2 n4} - r7c6{n4 n5} - c4n5{r9 r4} - c4n4{r4 .} ==> r1c4≠6whip: r5n5{c2 c6} - r7c6{n5 n4} - r7c5{n4 n2} - c1n2{r7 r5} - r5c7{n2 n4} - r6c7{n4 n6} - r4n6{c9 c4} - r4n4{c4 .} ==> r4c1≠5g-whip: c4n3{r9 r8} - c4n5{r8 r4} - b5n6{r4c4 r6c456} - r6c7{n6 n4} - r5c7{n4 n2} - c9n2{r5 r3} - c4n2{r3 r1} - c4n4{r1 .} ==> r9c4≠9g-whip: c4n3{r8 r9} - c4n5{r9 r4} - b5n6{r4c4 r6c456} - r6c7{n6 n4} - r5c7{n4 n2} - c9n2{r5 r3} - c4n2{r3 r1} - c4n4{r1 .} ==> r8c4≠9hidden-pairs-in-a-block: b8{n7 n9}{r8c6 r9c5} ==> r9c5≠4, r9c5≠2, r8c6≠5whip: r9n2{c3 c4} - c4n3{r9 r8} - r8c3{n3 n9} - b8n9{r8c6 r9c5} - r5c5{n9 n4} - r7c5{n4 .} ==> r9c3≠5whip: b8n9{r8c6 r9c5} - r5c5{n9 n4} - r1n4{c5 c4} - b8n4{r9c4 r7c6} - r7c5{n4 n2} - r1n2{c5 c7} - r5c7{n2 .} ==> r1c6≠9whip: r4n7{c8 c9} - r8n7{c9 c6} - r9c5{n7 n9} - r5c5{n9 n4} - r4n4{c4 c1} - r4n2{c1 c3} - b7n2{r9c3 r7c1} - r7c5{n2 .} ==> r9c8≠7g-whip: r4n7{c9 c8} - r4n6{c8 c4} - c4n5{r4 r789} - r7c6{n5 n4} - r7c5{n4 n2} - r9n2{c4 c3} - r4n2{c3 c1} - r4n4{c1 .} ==> r4c9≠9g-whip: r4n7{c8 c9} - r4n6{c9 c4} - c4n5{r4 r789} - r7c6{n5 n4} - r7c5{n4 n2} - r9n2{c4 c3} - r4n2{c3 c1} - r4n4{c1 .} ==> r4c8≠9hidden-pairs-in-a-block: b6{n3 n9}{r5c9 r6c8} ==> r6c8≠6, r5c9≠4, r5c9≠2whip: c9n2{r3 r4} - r4n7{c9 c8} - r3c8{n7 n9} - b6n9{r6c8 r5c9} - r5c5{n9 n4} - r5c7{n4 .} ==> r3c9≠6whip: b6n9{r6c8 r5c9} - r5c5{n9 n4} - c1n4{r5 r4} - b6n4{r4c9 r6c7} - r5c7{n4 n2} - c1n2{r5 r7} - r7c5{n2 .} ==> r6c1≠9whip: c4n3{r8 r9} - c8n3{r9 r6} - r5c9{n3 n9} - r5c5{n9 n4} - c4n4{r4 r1} - c4n2{r1 r3} - b3n2{r3c9 r1c7} - r5c7{n2 .} ==> r8c9≠3whip: r5c9{n3 n9} - r5c5{n9 n4} - r7c5{n4 n2} - c1n2{r7 r4} - b6n2{r4c9 r5c7} - r1n2{c7 c4} - c4n4{r1 r9} - c7n4{r9 r6} - c1n4{r6 .} ==> r5c1≠3whip: r9c5{n7 n9} - r5c5{n9 n4} - r5c7{n4 n2} - r1n2{c7 c4} - b8n2{r9c4 r7c5} - c1n2{r7 r4} - c1n4{r4 r6} - c4n4{r6 r9} - c7n4{r9 .} ==> r1c5≠7`

But then, instead of your whip, it finds a g-whip, and the two paths diverge:
Code: Select all
`g-whip: r7c6{n4 n5} - c4n5{r9 r4} - b5n6{r4c4 r6c456} - r6c7{n6 n4} - r4n4{c9 c1} - r5n4{c1 c5} - r7c5{n4 n2} - c1n2{r7 r5} - r5c7{n2 .} ==> r1c6≠4whip: r1n4{c5 c4} - b8n4{r9c4 r7c6} - r7c5{n4 n2} - r1n2{c5 c7} - r5c7{n2 .} ==> r5c5≠4singles ==> r5c5=9, r5c9=3, r6c8=9, r9c5=7, r8c6=9, r9c9=4, r7c9=6, r9c7=5, r1c8=5, r8c1=6biv-chain: r7n2{c1 c5} - r9c4{n2 n3} - b9n3{r9c8 r7c8} ==> r7c1≠3biv-chain: c7n2{r1 r5} - r4c9{n2 n7} - b9n7{r8c9 r8c7} ==> r1c7≠7z-chain: r5c2{n5 n1} - r5c6{n1 n4} - r7c6{n4 n5} - c2n5{r7 .} ==> r5c1≠5z-chain: r5c2{n5 n1} - r7c2{n1 n3} - r8n3{c3 c4} - c4n5{r8 .} ==> r4c2≠5biv-chain: r4c2{n8 n9} - b7n9{r9c2 r9c3} - c3n2{r9 r4} ==> r4c3≠8z-chain: r2c5{n6 n8} - r2c7{n8 n7} - c8n7{r3 r4} - r4n6{c8 .} ==> r2c4≠6biv-chain: r2c4{n1 n9} - b3n9{r2c9 r3c9} - r3n2{c9 c4} ==> r3c4≠1z-chain: c4n1{r2 r6} - c3n1{r6 r9} - b7n2{r9c3 r7c1} - c1n5{r7 .} ==> r2c1≠1z-chain: r2c5{n6 n8} - r6c5{n8 n4} - r6c7{n4 n6} - r2n6{c7 .} ==> r1c5≠6z-chain: c3n8{r2 r6} - c5n8{r6 r2} - b2n6{r2c5 r3c4} - c2n6{r3 .} ==> r1c2≠8biv-chain: r5n2{c1 c7} - b3n2{r1c7 r3c9} - b3n9{r3c9 r2c9} - r2c4{n9 n1} - b5n1{r6c4 r5c6} ==> r5c1≠1naked-pairs-in-a-row: r5{c1 c7}{n2 n4} ==> r5c6≠4t-whip: b7n9{r9c2 r9c3} - c3n2{r9 r4} - r5c1{n2 n4} - r4c1{n4 .} ==> r4c2≠9singles ==> r4c2=8, r6c5=8, r2c5=6naked-pairs-in-a-column: c7{r2 r8}{n7 n8} ==> r1c7≠8naked-pairs-in-a-column: c6{r4 r7}{n4 n5} ==> r5c6≠5singles ==> r5c6=1, r5c2=5, r2c4=1naked-pairs-in-a-row: r7{c2 c8}{n1 n3} ==> r7c1≠1naked-pairs-in-a-row: r6{c4 c7}{n4 n6} ==> r6c1≠4biv-chain: r3c4{n9 n2} - r9n2{c4 c3} - r9n9{c3 c2} ==> r3c2≠9biv-chain: r4c3{n9 n2} - c9n2{r4 r3} - c9n9{r3 r2} ==> r2c3≠9biv-chain: c1n1{r3 r6} - c3n1{r6 r9} - c3n2{r9 r4} - b4n9{r4c3 r4c1} ==> r3c1≠9hidden-pairs-in-a-row: r3{n2 n9}{c4 c9} ==> r3c9≠8, r3c9≠7stte`
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re: Fully supersymmetric chains

Sudorule may be a length-first strategy, while my solver is a technique-first strategy.
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Fully supersymmetric chains

yzfwsf wrote:Sudorule may be a length-first strategy, while my solver is a technique-first strategy.

Do you mean you try e.g. all the whips before all the g-whips?
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re: Fully supersymmetric chains

denis_berthier wrote:Do you mean you try e.g. all the whips before all the g-whips?

Yes.
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Fully supersymmetric chains

I realized that the cost of searching whips is to create new nodes, and the time spent searching for braids is mainly to correct the actual length of the chain, otherwise the braids found are not the shortest.
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Fully supersymmetric chains

yzfwsf wrote:I realized that the cost of searching whips is to create new nodes, and the time spent searching for braids is mainly to correct the actual length of the chain, otherwise the braids found are not the shortest.

In braids, compared to whips, there are many more possibilities at each step for the next llc. As a result, complexity of braids is much higher (length fixed).

If you watch resolution paths with both whips and braids, braids appear quire rarely. It means there's rarely a braid of shorter length that can replace a given whip of minimal length for a given elimination.
Conversely, the B rating is rarely different from the W rating. It means there's very often a whip that can replace a braid of same length (possibly for a different elimination).

Note however that there are rare puzzles (0.3% of the controlled-bias ones) that can be solved by braids but not by whips (see examples in PBCS).
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re:

denis_berthier wrote:
SOLVABLE BY NRCZT-BRAIDS <=> SOLVABLE BY T&E(ECP+NS+HS)

This post gives a precise answer to the question: what is the solving potential of nrczt-braids?
Given any resolution theory, such a question is generally very hard to answer. E.g., if I considered only whips instead of braids, I'd have no answer.

First, I need non ambiguous definitions. And for this, you must remember my distinction between a resolution rule and a resolution technique (see here:http://forum.enjoysudoku.com/viewtopic.php?t=5600&start=0).

Definition: Given a resolution theory T and a candidate z, T&E(T, z) is the following resolution technique:
- start a new grid by copying the current PM; add z to this new grid as a decided value; apply to this new PM all the rules in T;
- if a contradiction is obtained in this new PM, then delete z from the original one; if no contradiction is obtained, then merely go back to the original PM.

I think this is what everyone means by "using T&E(T) to eliminate candidate z".

Definition: Given a resolution theory T, T&E(T) is the following resolution technique (this is only conceptual, any implementation would optimise this):
- a) define phase = 1;
- b) apply all the rules in T;
- c) set changed-PM = false; mark all the remaining candidates as "not tried";
- d) if there is at least one "not-tried" candidate, then choose any one of them, say z; apply T&E(z); if it eliminates z, then set changed-PM = true and apply all the rules in T, otherwise un-mark z; in both cases, goto d;
- e) if there is no not-tried candidate:
----------- if changed-PM = true, then set phase = phase +1 and goto c);
----------- if changed-PM = false, then stop.
Notice that the procedure allows considering the same candidate z several times. This is reasonable, because any elimination on another candidate z' by T&E(z') may entail a new possibility of a contradiction appearing in a new application of T&E(z).

Definition: a puzzle P is solvable by T&E(T) if the above procedure leads to a solution.

We'll be interested only in T= ECP+NS+HS (with ECP = the rules for the elementary constraints propagation).

Notation: T&E designates T&E(ECP+NS+HS)

THEOREM: ANY ELIMINATION THAT CAN BE DONE BY AN NRCZT-BRAID WITH TARGET Z CAN BE DONE BY T&E(ECP+NS+HS, z)
COROLLARY: ANY PUZZLE THAT CAN BE SOLVED WITH ONLY NRCZT-BRAIDS (+ of course ECP, NS and HS) CAN BE SOLVED BY T&E(ECP+NS+HS).

Proof: obvious.
What is interesting is that the converse is true:

THEOREM: ANY ELIMINATION THAT CAN BE DONE BY T&E(ECP+NS+HS, z) CAN BE DONE BY AN NRCZT-BRAID WITH TARGET z.
COROLLARY: ANY PUZZLE THAT CAN BE SOLVED BY T&E(ECP+NS+HS) CAN BE SOLVED BY NRCZT-BRAIDS.

Notice that puzzles that can't be solved by T&E(ECP+NS+HS) are extremely rare.

We shall show that any elimination done by T&E, at any step in the resolution process, could have been done by an nrczt-braid.

Consider the PM generated by the T&E hypothesis z=n0r0c0 and take n0r0c0 as the target of the nrczt-braid we're going to build.
In the auxiliary PM generated by the T&E hypothesis, the T&E procedure is a well defined sequence of deletions of candidates based on ECP and of assertions of values based on NS or HS, until a contradiction is reached (if one is reached).

1) Consider the first step of T&E that is not an elimination by ECP.

Suppose first that the assertion made by this step relies on NS: say r'c'=n'
If this assertion can be made, it can only be because:
- n'r'c' is not nrc-linked to n0r0c0 (otherwise it would have been eliminated by ECP);
- all the other candidates for cell r'c' have been eliminated by the assertion of n0r0c0, which supposes that they are nrc-linked to n0r0c0, because only ECP can produce eliminations.
Take any of the candidates in cell r'c', different from n'r'c', say n1r'c'.
Then {n1r'c' n'r'c'} is the first cell of our nrczt-braid (and all the other candidates in cell r'c' are z-candidates).

The same reasoning applies if this step is an assertion by HS(row): instead of considering the rc-cell r'c', we consider the rn-cell r'n'.
The same reasoning applies if this step is an assertion by HS(col): instead of considering the rc-cell r'c', we consider the cn-cell c'n'.
The same reasoning applies if this step is an assertion by HS(blk): instead of considering the rc-cell r'c', we consider the bn-cell b'n'.

2) The sequel is done by recursion. If we have been able to replace the T&E procedure upto the nth assertion step, then we can replace it by a longer nrczt-braid upto the (n+1)th assertion step. Name n'r'c' the nth candidate asserted.
Suppose first that the (n+1)th assertion made by T&E relies on NS: say r'c'=n'
If this assertion can be made, it can only be because:
- n'r'c' is not nrc-linked to n0r0c0 or to any of the previous candidates asserted in any of the previous steps, i.e. to any of the right-linking candidates of the partial nrczt-braid we've already built (otherwise it would have been eliminated by ECP);
- all the other candidates for cell r'c' have been eliminated by the assertions of n0r0c0 and of all the previously asserted candidates, which supposes that each of them is individually nrc-linked to the target or to some of the previous right-linking candidates;
- there is a candidate n1r'c' in cell r'c' which is nrc-linked to n0r0c0 OR to a previous right-linking candidate n2r2c2. Take {n1r'c' n'r'c'} as the next cell of our braid. NOTICE THAT IT WOULD BLOCK HERE IF WE CONSIDERED WHIPS INSTEAD OF BRAIDS.

The new cell of our nrczt-braid, {n1r'c' n'r'c'}, is appended to the right of n2r2c2 (all the other candidates in cell r'c' are z- or t- candidates wrt to already existing branches of the net).

The same reasoning applies if this step is an assertion by HS(row): instead of considering the rc-cell r'c', we consider the rn-cell r'n'.
The same reasoning applies if this step is an assertion by HS(col): instead of considering the rc-cell r'c', we consider the cn-cell c'n'.
The same reasoning applies if this step is an assertion by HS(blk): instead of considering the rc-cell r'c', we consider the bn-cell b'n'.

3) End: a contradiction is detected by T&E when a cell (rc-, rn-, cn- or bn-) has no candidate left. Suppose it is an rc-cell.
How can that happen? Only via an ECP step. But it means then that the last asserted value is nrc-linked to a previous right-linking candidate or to the target, i.e. we have an nrczt-braid.

q.e.d.

Remark: for the first time, we thus have a set of resolution rules (the set of nrczt-braid[n] rules, for any length n, together with ECP, NS and HS) which is equivalent to T&E.

I have trouble converting T&E (ECP+NS+HS) into braids, that is how to delete redundant rlc.
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Re:

yzfwsf wrote:
denis_berthier wrote:SOLVABLE BY NRCZT-BRAIDS <=> SOLVABLE BY T&E(ECP+NS+HS)
[...]
Remark: for the first time, we thus have a set of resolution rules (the set of nrczt-braid[n] rules, for any length n, together with ECP, NS and HS) which is equivalent to T&E.

I have trouble converting T&E (ECP+NS+HS) into braids, that is how to delete redundant rlc.

This theorem doesn't say anything about that point. In order to understand it, some context is necessary:

1) Until I gave a precise definition of T&E (and also of T&E(T, n)), the only existing definition was: suppose a candidate is true; if this leads to a contradiction, then delete it. Of course, this has absolutely no sense. Any candidate that is not in the solution leads to a logical contradiction.
For a long time, people argued that my definition didn't coincide with what they understood by T&E - until finally the same people argued that it was not new and someone plagiarised it into sudopedia before the big crash.

2) Based on my precise definition, I found the above theorem (see http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.html, oct 2008]
Its importance is first of all theoretical. As I stated in bold: for the first time, we thus have a set of resolution rules (the set of nrczt-braid[n] rules, for any length n, together with ECP, NS and HS) which is equivalent to T&E. Note: a set of resolution rules - and an infinite one (because no unique rule can be equivalent to T&E).
It also has very useful practical consequences for the sub-classification of puzzles in T&E(2).

Starting from a T&E procedure, the theorem constructs some braid that does the same elimination. The proof is constructive - i.e. the theorem is valid in constructive logic.
It doesn't say anything about the length or minimality of that braid (apart from the obvious fact that its length is at most the number of Singles used in T&E).
The braid built that way will most of the time not be the shortest possible (and even very far from being so).
One can devise ways to shorten it (e.g. by deleting useless branches), but even so, nothing can guarantee that it will be the shortest possible - not even the shortest possible for this precise candidate.

Note that CSP-Rules doesn't have this problem, as it doesn't rely on any form of T&E, BFS or DFS: all works by pattern-matching. Braids of different lengths are different patterns and different patterns have different priorities, which explains why shorter whips always come before longer ones (unless one uses the additional features that somehow allow to change the default priorities).
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re: Fully supersymmetric chains

denis_berthier wrote:2) The sequel is done by recursion. If we have been able to replace the T&E procedure upto the nth assertion step, then we can replace it by a longer nrczt-braid upto the (n+1)th assertion step. Name n'r'c' the nth candidate asserted.

Isn't this "recursion" similar to BFS or DFS?
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Fully supersymmetric chains

yzfwsf wrote:
denis_berthier wrote:2) The sequel is done by recursion. If we have been able to replace the T&E procedure upto the nth assertion step, then we can replace it by a longer nrczt-braid upto the (n+1)th assertion step. Name n'r'c' the nth candidate asserted.

Isn't this "recursion" similar to BFS or DFS?

I'm talking of the proof of a theorem. What does BFS or DFS have to do with this?
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re: Fully supersymmetric chains

The clisp language is a book from heaven to me, I really can't understand it. But I see that in your sudorule, braids[n] are all extended from braids[n-1], which is a bit like recursion. Can you describe the relevant code in plain language or pseudocode?
yzfwsf

Posts: 671
Joined: 16 April 2019

### Re: Fully supersymmetric chains

yzfwsf wrote:The clisp language is a book from heaven to me, I really can't understand it. But I see that in your sudorule, braids[n] are all extended from braids[n-1], which is a bit like recursion. Can you describe the relevant code in plain language or pseudocode?

CLIPS allows automatic pattern-matching and forward logical inferencing (contrary to Prolog, which is based on backwards inferencing). The basic technology dates back to the 70s - though drastic speed improvements have been made since that time. Roughly speaking, it allows to use logical formulæ as programs.
:if you want to learn the basics of CLIPS, read sections 1-5 (minus sections 2.6 and 5.3.2-5.3.7) of the "Basic Programming Guide".

in [HLS], [CRT] or [PBCS], braids[n] are defined from partial-braids[n-1], which in turn are defined from partial-braids[n-2]. These are mathematical/logical definitions, not code.
The definition of partial-braids are indeed definitions by recursion, a standard technique in mathematics/FOL.
They are available in full logical detail [which you may consider as pseudo-code] in the above books.

CSP-Rules is the implementation of the above rules (and many other ones) in the CLIPS language. Basically, each logical rule appears in CLIPS as a CLIPS rule (or a small set of CLIPS rules), with minor syntactic changes.
I suggest you read one the the partial-whip rule files in directory CSP-Rules-Generic/CHAIN-RULES-SPEED/PARTIAL-WHIPS. As you're a programmer and my rules are coded with lots of comments, it should be easy for you to understand the general lines.

SudoRules is only the application of CSP-Rules to Sudoku.
denis_berthier
2010 Supporter

Posts: 3676
Joined: 19 June 2007
Location: Paris

### Re: Fully supersymmetric chains

Thanks for your advice. Strictly speaking, I am not a programmer, my profession is not a programmer, and I have never profited from writing programs. I am just a programming amateur. I started programming with vba provided by microsoft excel. I now use Freebasic programming language.
yzfwsf

Posts: 671
Joined: 16 April 2019

PreviousNext 