The New Sudoku Players' Forum

by **mith** » Tue Mar 23, 2021 4:34 pm

Code: Select all: +-------+-------+-------+ | . . . | . . . | . . . | | . . 2 | 8 . . | . . 3 | | . 9 . | . 7 . | . 6 . | +-------+-------+-------+ | . 6 . | . 5 . | . 7 . | | . . 8 | 3 . . | . . 4 | | . . . | . . . | 2 . . | +-------+-------+-------+ | . 1 3 | 2 . . | . . 8 | | . 5 . | . 4 . | . 9 . | | 9 . . | . . 5 | . . . | +-------+-------+-------+ ...........28....3.9..7..6..6..5..7...83....4......2...132....8.5..4..9.9....5...

(Already on DST here, this one is for the EU folks...)

by **pjb** » Tue Mar 23, 2021 8:31 pm

2 MSLSs:

16 cell Truths: r3489 c3479
16 links: 5r3, 9r4, 67r8, 67r9, 14c3, 14c4, 1348c7, 12c9
17 eliminations: r3c1<>5, r1c3<>14, r6c3<>14, r16c4<>4, r1c7<>148, r2c7<>14, r5c7<>1, r7c7<>4, r1c9<>12, r6c9<>1,

25 cell Truths: r12567 c12567 +r1c8 r6c8
25 links: 238r1, 6r2, 26r5, 368r6, 6r7, 1457c1, 47c2, 19c5, 1479c6, 579c7
6 eliminations: r6c4<>6, r6c9<>6, r3c1<>14, r3c6<>14; lclste

Phil

by **Cenoman** » Tue Mar 23, 2021 11:29 pm

Solved with 9 fishes (8 SF, 1 JF) in each digit 1 to 9

Code: Select all: +---------------------------+--------------------------+-------------------------+ | 1345678 3478 14567 | 4569 12369 123469 | 145789 28 12579 | | 14567 47 2 | 8 169 1469 | 14579 145 3 | | 13458 9 145 | 45 7 1234 | 1458 6 125 | +---------------------------+--------------------------+-------------------------+ | 23 6 149 | 49 5 28 | 38 7 19 | | 1257 27 8 | 3 1269 12679 | 1569 15 4 | | 13457 347 14579 | 4679 1689 146789 | 2 38 1569 | +---------------------------+--------------------------+-------------------------+ | 467 1 3 | 2 69 679 | 4567 45 8 | | 28 5 67 | 167 4 38 | 1367 9 1267 | | 9 28 467 | 167 38 5 | 1467 23 167 | +---------------------------+--------------------------+-------------------------+

SF(2)r348\c169 => -2 r5c1, r15c6, r1c9
SF(3)r348\c167 => -3 r16c1, r1c6
SF(8)r348\c167 => -8 r1c1, r6c6, r1c7
SF(5)r257\c178 => -5 r136c1, r13c7
SF(9)r257\c567 => -9 r16c5, r16c6, r1c7; HT(238)r1c258, r348c1, r348c6

Code: Select all: +------------------------+-----------------------+-----------------------+ | 1467 38 14567 | 4569 23 146 | 147 28 1579 | | 14567 47 2 | 8 169 1469 | 14579 145 3 | | 38 9 145 | 45 7 23 | 148 6 125 | +------------------------+-----------------------+-----------------------+ | 23 6 149 | 49 5 28 | 38 7 19 | | 157 27 8 | 3 1269 1679 | 1569 15 4 | | 147 347 14579 | 4679 168 1467 | 2 38 1569 | +------------------------+-----------------------+-----------------------+ | 467 1 3 | 2 69 679 | 4567 45 8 | | 28 5 67 | 167 4 38 | 1367 9 1267 | | 9 28 467 | 167 38 5 | 1467 23 167 | +------------------------+-----------------------+-----------------------+

JF(1)r3489\c3479 => -1 r16c3, r125c7, r16c9
SF(4)r349\c347 => -4 r16c3, r16c4, r127c7; +7r1c7, NT(569)r1c349, r257c7, NP(59)b3p34

Code: Select all: +----------------------+----------------------+--------------------+ | 14 38 56 | 569 23 14 | 7 28 59 | | 14567 47 2 | 8 169 1469 | 59 14 3 | | 38 9 145 | 45 7 23 | 148 6 12 | +----------------------+----------------------+--------------------+ | 23 6 149 | 49 5 28 | 38 7 19 | | 157 27 8 | 3 1269 1679 | 569 15 4 | | 147 347 579 | 679 168 1467 | 2 38 569 | +----------------------+----------------------+--------------------+ | 467 1 3 | 2 69 679 | 56 45 8 | | 28 5 67 | 167 4 38 | 13 9 1267 | | 9 28 467 | 167 38 5 | 14 23 167 | +----------------------+----------------------+--------------------+

SF(6)r189\c349 => -6 r6c4, r6c9
SF(7)r257\c126 => -7 r6c1, r6c2, r6c6
ste
... and the unavoidable one-step solution:

Hidden Text: Show

Website · by **denis_berthier** » Wed Mar 24, 2021 5:32 am

.
1) Using only Subsets (22 of them):
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = SFin
*** Download from: https://github.com/denis-berthier/CSP-Rules-V2.1
***********************************************************************************************

Code: Select all: 1345678 3478 14567 14569 12369 123469 145789 12458 12579 14567 47 2 8 169 1469 14579 145 3 13458 9 145 145 7 1234 1458 6 125 1234 6 149 149 5 12489 1389 7 19 1257 27 8 3 1269 12679 1569 15 4 13457 347 14579 14679 1689 146789 2 1358 1569 467 1 3 2 69 679 4567 45 8 2678 5 67 167 4 13678 1367 9 1267 9 2478 467 167 1368 5 13467 1234 1267 233 candidates, 1607 csp-links and 1607 links. Density = 5.95%

hidden-pairs-in-a-block: b8{n3 n8}{r8c6 r9c5} ==> r9c5 ≠ 6, r9c5 ≠ 1, r8c6 ≠ 7, r8c6 ≠ 6, r8c6 ≠ 1
whip[1]: b8n1{r9c4 .} ==> r1c4 ≠ 1, r3c4 ≠ 1, r4c4 ≠ 1, r6c4 ≠ 1
hidden-pairs-in-a-block: b7{n2 n8}{r8c1 r9c2} ==> r9c2 ≠ 7, r9c2 ≠ 4, r8c1 ≠ 7, r8c1 ≠ 6
hidden-pairs-in-a-block: b6{n3 n8}{r4c7 r6c8} ==> r6c8 ≠ 5, r6c8 ≠ 1, r4c7 ≠ 9, r4c7 ≠ 1
naked-triplets-in-a-row: r4{c3 c4 c9}{n1 n4 n9} ==> r4c6 ≠ 9, r4c6 ≠ 4, r4c6 ≠ 1, r4c1 ≠ 4, r4c1 ≠ 1
naked-triplets-in-a-column: c8{r2 r5 r7}{n4 n1 n5} ==> r9c8 ≠ 4, r9c8 ≠ 1, r1c8 ≠ 5, r1c8 ≠ 4, r1c8 ≠ 1
naked-triplets-in-a-row: r9{c2 c5 c8}{n2 n8 n3} ==> r9c9 ≠ 2, r9c7 ≠ 3
swordfish-in-columns: n2{c2 c5 c8}{r9 r5 r1} ==> r5c6 ≠ 2, r5c1 ≠ 2, r1c9 ≠ 2, r1c6 ≠ 2
swordfish-in-columns: n9{c3 c4 c9}{r6 r4 r1} ==> r6c6 ≠ 9, r6c5 ≠ 9, r1c7 ≠ 9, r1c6 ≠ 9, r1c5 ≠ 9
swordfish-in-columns: n5{c3 c4 c9}{r6 r3 r1} ==> r6c1 ≠ 5, r3c7 ≠ 5, r3c1 ≠ 5, r1c7 ≠ 5, r1c1 ≠ 5
swordfish-in-columns: n3{c2 c5 c8}{r6 r1 r9} ==> r6c1 ≠ 3, r1c6 ≠ 3, r1c1 ≠ 3
hidden-pairs-in-a-block: b2{n2 n3}{r1c5 r3c6} ==> r3c6 ≠ 4, r3c6 ≠ 1, r1c5 ≠ 6, r1c5 ≠ 1
finned-x-wing-in-columns: n1{c8 c5}{r2 r5} ==> r5c6 ≠ 1
naked-triplets-in-a-column: c6{r3 r4 r8}{n3 n2 n8} ==> r6c6 ≠ 8
swordfish-in-rows: n8{r3 r4 r8}{c1 c7 c6} ==> r1c7 ≠ 8, r1c1 ≠ 8
hidden-pairs-in-a-block: b1{n3 n8}{r1c2 r3c1} ==> r3c1 ≠ 4, r3c1 ≠ 1, r1c2 ≠ 7, r1c2 ≠ 4
finned-x-wing-in-rows: n1{r4 r3}{c3 c9} ==> r1c9 ≠ 1
swordfish-in-rows: n4{r3 r4 r9}{c7 c4 c3} ==> r7c7 ≠ 4, r6c4 ≠ 4, r6c3 ≠ 4, r2c7 ≠ 4, r1c7 ≠ 4, r1c4 ≠ 4, r1c3 ≠ 4
jellyfish-in-columns: n1{c1 c6 c5 c8}{r5 r1 r6 r2} ==> r6c9 ≠ 1, r6c3 ≠ 1, r5c7 ≠ 1, r2c7 ≠ 1, r1c7 ≠ 1, r1c3 ≠ 1
naked-single ==> r1c7 = 7
naked-pairs-in-a-block: b3{r1c9 r2c7}{n5 n9} ==> r3c9 ≠ 5, r2c8 ≠ 5
hidden-pairs-in-a-row: r1{n1 n4}{c1 c6} ==> r1c6 ≠ 6, r1c1 ≠ 6
finned-x-wing-in-rows: n7{r7 r5}{c6 c1} ==> r6c1 ≠ 7
naked-pairs-in-a-column: c1{r1 r6}{n1 n4} ==> r7c1 ≠ 4, r5c1 ≠ 1, r2c1 ≠ 4, r2c1 ≠ 1
stte

2) 1-step solution?
There is no BRT- or W1- anti-backdoor, therefore no real 1-elimination solution.
In particular, Cenoman's elimination still requires several Subsets to be applied before the end:

Hidden Text: Show

Of course, it all depends on what you count as no-step. But if you count Subsets as no-step, then the first solution is 0-step.

3) 2-step solution?
As there is a solution in S4, it is natural to restrict the search for 2-step solutions to W4.
But in W4, there are only 5 W1-anti-backdoor-pairs:

Code: Select all: n4r9c2, n5r6c9 n4r9c2, n9r6c3 n4r9c2, n5r5c1 n4r9c2, n9r4c9 n1r5c8, n4r9c2

and none of them gives rise to a 2-step solution in W4.

4) [corrected:] 2-steps using nukes, i.e. Forcing-T&E
FORCING-T&E(BRT) applied to bivalue candidates n8r1c8 and n8r6c8 :
===> 0 values decided in both cases:
===> 51 candidates eliminated in both cases: n3r1c1 n8r1c1 n4r1c2 n7r1c2 n1r1c5 n6r1c5 n9r1c5 n2r1c6 n3r1c6 n8r1c7 n1r1c8 n4r1c8 n5r1c8 n2r1c9 n1r3c1 n4r3c1 n5r3c1 n1r3c6 n4r3c6 n1r3c9 n1r4c1 n2r4c1 n1r4c6 n4r4c6 n9r4c6 n1r4c7 n9r4c7 n2r5c1 n2r5c6 n3r6c1 n6r6c5 n9r6c5 n8r6c6 n1r6c8 n5r6c8 n6r8c1 n7r8c1 n1r8c6 n6r8c6 n7r8c6 n1r8c7 n6r8c7 n7r8c7 n4r9c2 n7r9c2 n1r9c5 n6r9c5 n3r9c7 n1r9c8 n4r9c8 n2r9c9
18 singles
FORCING-T&E(BRT) applied to bivalue candidates n1r4c9 and n9r4c9 :
===> 12 values decided in both cases: n4r7c8 n5r7c7 n5r3c4 n4r4c4 n6r5c7 n9r1c4 n6r8c9 n1r8c4 n7r2c2 n9r2c7 n4r6c2 n4r2c6
===> 76 candidates eliminated in both cases: n5r1c1 n6r1c1 n7r1c1 n1r1c3 n4r1c3 n7r1c3 n1r1c4 n4r1c4 n5r1c4 n6r1c4 n4r1c6 n9r1c6 n1r1c7 n5r1c7 n9r1c7 n1r1c9 n9r1c9 n1r2c1 n4r2c1 n7r2c1 n4r2c2 n9r2c5 n1r2c6 n6r2c6 n9r2c6 n1r2c7 n4r2c7 n5r2c7 n7r2c7 n4r2c8 n5r3c3 n1r3c4 n4r3c4 n5r3c7 n4r4c3 n1r4c4 n9r4c4 n1r5c1 n6r5c5 n1r5c6 n6r5c6 n1r5c7 n5r5c7 n9r5c7 n4r6c1 n5r6c1 n7r6c1 n7r6c2 n1r6c3 n4r6c3 n7r6c3 n1r6c4 n4r6c4 n9r6c4 n4r6c6 n7r6c6 n9r6c6 n1r6c9 n6r6c9 n4r7c1 n6r7c6 n4r7c7 n6r7c7 n7r7c7 n5r7c8 n6r8c3 n6r8c4 n7r8c4 n1r8c9 n7r8c9 n7r9c3 n1r9c4 n4r9c7 n6r9c7 n7r9c7 n6r9c9
stte

5) [added:] 1-step using super-nukes, i.e. Forcing[3]-T&E
FORCING[3]-T&E(W1) applied to trivalue candidates n5r1c9, n5r3c9 and n5r6c9 :
===> 4 values decided in the three cases: n4r7c8 n4r4c4 n5r7c7 n6r5c7
===> 116 candidates eliminated in the three cases: n3r1c1 n5r1c1 n6r1c1 n8r1c1 n4r1c2 n7r1c2 n1r1c3 n4r1c3 n7r1c3 n1r1c4 n4r1c4 n6r1c4 n1r1c5 n6r1c5 n9r1c5 n2r1c6 n3r1c6 n9r1c6 n1r1c7 n4r1c7 n5r1c7 n8r1c7 n9r1c7 n1r1c8 n4r1c8 n5r1c8 n1r1c9 n2r1c9 n1r2c1 n4r2c1 n7r2c1 n4r2c2 n9r2c5 n1r2c6 n9r2c6 n1r2c7 n5r2c7 n7r2c7 n4r2c8 n1r3c1 n4r3c1 n5r3c1 n5r3c3 n4r3c4 n1r3c6 n4r3c6 n1r3c7 n5r3c7 n1r3c9 n1r4c1 n4r4c1 n4r4c3 n1r4c4 n9r4c4 n1r4c6 n4r4c6 n9r4c6 n1r4c7 n9r4c7 n2r5c1 n6r5c5 n1r5c6 n2r5c6 n6r5c6 n1r5c7 n5r5c7 n9r5c7 n3r6c1 n5r6c1 n7r6c1 n7r6c2 n1r6c3 n4r6c3 n7r6c3 n1r6c4 n4r6c4 n9r6c4 n1r6c5 n9r6c5 n4r6c6 n7r6c6 n8r6c6 n9r6c6 n1r6c8 n5r6c8 n1r6c9 n6r6c9 n4r7c1 n6r7c6 n4r7c7 n6r7c7 n7r7c7 n5r7c8 n6r8c1 n7r8c1 n6r8c4 n1r8c6 n6r8c6 n7r8c6 n6r8c7 n7r8c7 n2r8c9 n7r8c9 n2r9c2 n7r9c2 n6r9c3 n7r9c3 n7r9c4 n6r9c5 n8r9c5 n3r9c7 n4r9c7 n6r9c7 n1r9c8 n4r9c8 n1r9c9
stte

by **DEFISE** » Wed Mar 24, 2021 12:06 pm

denis_berthier wrote:.
4) 1-step using nukes, i.e. Forcing-T&E
FORCING-T&E(BRT) applied to bivalue candidates n8r1c8 and n8r6c8 :
===> 0 values decided in both cases:
===> 51 candidates eliminated in both cases: n3r1c1 n8r1c1 n4r1c2 n7r1c2 n1r1c5 n6r1c5 n9r1c5 n2r1c6 n3r1c6 n8r1c7 n1r1c8 n4r1c8 n5r1c8 n2r1c9 n1r3c1 n4r3c1 n5r3c1 n1r3c6 n4r3c6 n1r3c9 n1r4c1 n2r4c1 n1r4c6 n4r4c6 n9r4c6 n1r4c7 n9r4c7 n2r5c1 n2r5c6 n3r6c1 n6r6c5 n9r6c5 n8r6c6 n1r6c8 n5r6c8 n6r8c1 n7r8c1 n1r8c6 n6r8c6 n7r8c6 n1r8c7 n6r8c7 n7r8c7 n4r9c2 n7r9c2 n1r9c5 n6r9c5 n3r9c7 n1r9c8 n4r9c8 n2r9c9
stte

Hi Denis,
I think there is something wrong in your path.
Either you made a mistake in the starting resolution state, or there is an error in your FORCING-T&E procedure.
(My initial resolution state is obtained after no basic tech. applied)

There is a general property that can be easily demonstrated:
Let’s the bivalue candidates {A,B} such that T&E(T,A) => error.
If B is not a T-backdoor then FORCING-T&E(T,A,B) cannot lead to the solution.
(T = resolution theory)

Website · by **denis_berthier** » Wed Mar 24, 2021 12:40 pm

DEFISE wrote:Hi Denis,
I think there is something wrong in your path.
Either you made a mistake in the starting resolution state, or there is an error in your FORCING-T&E procedure.
(My initial resolution state is obtained after no basic tech. applied)

Ah, right, thanks. There were so many singles after the first round of Forcing-T&E that I thought it was solved. The Forcing-T&E requires a second step. I'll correct, though, with two steps, it becomes irrelevant.
1-step requires Forcing{3}-T&E .

Website · by **denis_berthier** » Thu Mar 25, 2021 7:17 am

.
The main problem when looking for two-step solutions in a systematic way is to find the anti-backdoor-pairs. Direct computations generally lead to a very large number of them, as I have reported in other threads. I have therefore a smarter procedure.

I looked for a two-step solution for this puzzle, based on longer whips. I've already shown (with the same procedure as here) that there is none in W4 (the only one that would be acceptable, considering the rating of this puzzle), so I looked for one in W8.

First step: find the candidates that can be eliminated in W8 (any solution pair in W8 must contain one of them)

SudoRules commands: Show

Code: Select all: 67 candidates can be eliminated: (311 511 811 412 712 115 615 915 216 316 916 517 817 118 418 518 219 527 428 131 431 531 533 136 436 537 141 441 944 146 446 946 147 947 251 256 157 557 361 163 463 763 965 866 966 168 568 169 471 477 677 777 578 681 781 186 686 786 492 792 195 695 397 497 198 498 299)

Second step: find the W1-anti-backdoor-pairs, by testing in W1 only the pairs of candidates that contain one candidate in the previous list

SudoRules commands: Show

85 W1-ANTI-BACKDOOR-PAIRS FOUND: Show

As this is the most computation-intensive step, it is worth checking the gain:
There are 233 candidates and only 67 that can be eliminated in W8.
This makes a total of (233*232)/2 = 27,028 pairs to be checked in a naïve approach.
In this approach, it makes a total of 67*(233-67) = 11,122 pairs to be checked.
The proportion of pairs to check is 41%. It would be still lower for smaller k (for instance, it is 31% in W4).
This has to be combined with the gain is in each check: checking in W8 is much easier than checking for whips of any length.

A disadvantage of this approach is, if later, someone wants to check for more solutions in some Wk with k>8, he has to restart from zero. Had I tried first in W6 or W7 instead of W8, that's what I would have had to do.

Third step: look for 2-step solutions in W8

SudoRules commands: Show

The result is two 2-step solutions in W8 (which also shows that there is no smaller k with a two step solution in Wk):

Code: Select all: whip[7]: r5c8{n5 n1} - r4c9{n1 n9} - c3n9{r4 r6} - c4n9{r6 r1} - r2n9{c6 c7} - r2n5{c7 c1} - b4n5{r5c1 .} ==> r7c8 ≠ 5 naked-single ==> r7c8 = 4 hidden-single-in-a-block ==> r7c7 = 5 whip[8]: r3n3{c6 c1} - r3n8{c1 c7} - r4n8{c7 c6} - r4n2{c6 c1} - c2n2{r5 r9} - b7n4{r9c2 r9c3} - r4n4{c3 c4} - r3n4{c4 .} ==> r3c6 ≠ 2 Singles + one whip[1] to the end OR whip[8]: r7c8{n4 n5} - r5c8{n5 n1} - r4c9{n1 n9} - c3n9{r4 r6} - c4n9{r6 r1} - r2n9{c6 c7} - r2n5{c7 c1} - b4n5{r5c1 .} ==> r7c1 ≠ 4 whip[1]: r7n4{c8 .} ==> r9c7 ≠ 4, r9c8 ≠ 4 whip[8]: r3n3{c6 c1} - r3n8{c1 c7} - r4n8{c7 c6} - r4n2{c6 c1} - c2n2{r5 r9} - r9n4{c2 c3} - r3n4{c3 c4} - r4n4{c4 .} ==> r3c6 ≠ 2 Singles + one whip[1] to the end

by **DEFISE** » Thu Mar 25, 2021 10:34 am

denis_berthier wrote:.
The main problem when looking for two-step solutions in a systematic way is to find the anti-backdoor-pairs. Direct computations generally lead to a very large number of them, as I have reported in other threads. I have therefore a smarter procedure.

I looked for a two-step solution for this puzzle, based on longer whips. I've already shown (with the same procedure as here) that there is none in W4 (the only one that would be acceptable, considering the rating of this puzzle), so I looked for one in W8.

Hi Denis,
I recently made a new procedure which allows me to know if there is the possibility of doing 1 or 2 or 3 steps with T-braids.
1) It looks for all candidates A such that :
T&E(T,A) => error and T leads to the solution if A is deleted.
If no result => no one-step possible => 2) :

2) It looks for couples (A, B) such that:
- T&E(T,A) => error
- and T&E(T,B) => error (if A is deleted).
- and T leads to the solution if A and B are deleted.
If no result => no two-step possible => 3) :

3) It looks for triplets (A,B,C) such that …

N.B my old procedure “Few steps” remains unchanged. It does not do an exhaustive search and is independent of the new one. This is only where the max length of the whips (or braids) comes in.
For this puzzle, if I set the maximum length of the whips to 8 it gives me a solution with a whip[7] and a whip[8] as you. For max length = 7, I found 3-steps solutions but no 2-steps.

Website · by **denis_berthier** » Thu Mar 25, 2021 3:55 pm

Hi François,
There are many possibilities for looking systematically for n-step solutions.

As I understand what you describe for fixed n, there are 3 steps:
a) look for solutions with n steps of T&E(T) and obtain a set of M sequences of n candidates each (cand1, cand2, ... candn)
b) using the T-braids vs T&E(T) theorem, you know that this implies M solutions with n-steps of braids of unknown length
c) filter these M solutions and keep only those that can be realised with T-braids of length <= k or better with T-whips of length <= k.

As you increase n, the smallest k with an n-step solution will obviously decrease.
(Note: in any realistic interpretation of what a step is, T can only be BRT or W1, so that the T-braids are merely braids or g-braids. Otherwise, you'll find unwanted Subsets in the resolution path.)

What I described in my previous posts works the opposite way.
1) First find the normal simplest-first solution and its W rating, say k;
2) Decide on some reasonable value (k2) for the maximum length of chains above which you are not interested by a solution with any number of steps; IMO, this shouldn't be much more than k+2;
3) find the 1-step solutions in Wk2, first looking for the T-anti-backdoors (an easy task)
4) if none, find the 2-step solutions in Wk2, as described in my previous post;
5) if none, ...

The problem with both approaches is the exponential growth (with n) of the number of cases to consider (if we want to find the shortest chains, we have to consider all the cases). How far (wrt n) have you tried to go?

Anyway, what most of the examples I've considered show is, any additional constraint on the number of steps leads to using absurdly complex chains, relative to the real complexity of the puzzle.

by **DEFISE** » Fri Mar 26, 2021 9:08 am

denis_berthier wrote:Hi François,
There are many possibilities for looking systematically for n-step solutions.
As I understand what you describe for fixed n, there are 3 steps:
a) look for solutions with n steps of T&E(T) and obtain a set of M sequences of n candidates each (cand1, cand2, ... candn)
b) using the T-braids vs T&E(T) theorem, you know that this implies M solutions with n-steps of braids of unknown length
c) filter these M solutions and keep only those that can be realised with T-braids of length <= k or better with T-whips of length <= k.

Hi Denis,
YES for a) and b) but NO for c) : the goal of my new procedure is not to find systematically n-step solutions with n whips[<=p] or braids[<=m]. It's goal is to be able to say that such n-steps are certainly impossible if a simple criterion is verified. For n=2 this criterion is:
There are no couples of candidates (A,B) such that:
T&E(T,A) => error
and T&E(T,B) => error (if A is deleted).
and T leads to the solution if A and B are deleted.

denis_berthier wrote:What I described in my previous posts works the opposite way.
1) First find the normal simplest-first solution and its W rating, say k;
2) Decide on some reasonable value (k2) for the maximum length of chains above which you are not interested by a solution with any number of steps; IMO, this shouldn't be much more than k+2;
3) find the 1-step solutions in Wk2, first looking for the T-anti-backdoors (an easy task)
4) if none, find the 2-step solutions in Wk2, as described in my previous post;
5) if none, ...

I understood well.

denis_berthier wrote:The problem with both approaches is the exponential growth (with n) of the number of cases to consider (if we want to find the shortest chains, we have to consider all the cases). How far (wrt n) have you tried to go?

Surely, even without looking for the shortest chains ! I do the test of the criterion described above only for n <= 3. Execution time is about 1s for n = 2 and 1mn for n = 3. Beyond that it must be much too long.

Website · by **denis_berthier** » Fri Mar 26, 2021 9:50 am

DEFISE wrote:the goal of my new procedure is not to find systematically n-step solutions with n whips[<=p] or braids[<=m]. It's goal is to be able to say that such n-steps are certainly impossible if a simple criterion is verified.

I see. A quick T&E pre-test before looking for n-step solutions if the test fails. Good idea.

The New Sudoku Players' Forum

Tatooine Daylight Savings

Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings

Re: Tatooine Daylight Savings