The New Sudoku Players' Forum

[denis_berthier]

Long whips SER 9.4, W31

This was originally intended to be mainly for DEFISE, but anyone can propose a solution.

Hi François,
Could you try
- your implementation of whips with the simplest-first strategy
- and your partial-optimiser of the number of steps
on this puzzle:

Code: Select all

+-------+-------+-------+
! . . . ! . . 1 ! . . 2 !
! . . . ! . 3 . ! . 4 . !
! . . 5 ! 2 . . ! 1 . . !
+-------+-------+-------+
! . . 3 ! 6 . . ! . 1 . !
! . 2 . ! . 7 . ! . . 8 !
! 9 . . ! . . 5 ! 7 . . !
+-------+-------+-------+
! . . 9 ! . . 7 ! . . . !
! . 8 . ! 9 . . ! . . 4 !
! 3 . . ! . 4 . ! . 8 . !
+-------+-------+-------+

.....1..2....3..4...52..1....36...1..2..7...89....57....9..7....8.9....43...4..8.
SER 9.4

Note: this is a morph of a puzzle found by Mauricio. As of now, it remains the largest known W rating for a puzzle solvable by whips.

[DEFISE]

Note: this is a morph of a puzzle found by Mauricio. As of now, it remains the largest known W rating for a puzzle solvable by whips.

Hi Denis,
I know this puzzle, it is on page 137 of your PCS book (Nov 2012). I had checked it in May (see my post of May 20) .
I find W = 29 because my whip [29] has 2 loops (in bold).
Here is my “Simplest First” resolution.

Hidden Text: Show

whip[11]: c8n9{r1 r5}- r4c9{n9 n5}- r2n5{c9 c4}- c4n7{r2 r1}- b2n4{r1c4 r3c6}- c6n9{r3 r4}- r5c6{n9 n3}- c4n3{r5 r7}- r7n8{c4 c5}- r3n8{c5 c1}- r4n8{c1 .} => -9r2c7
whip[11]: r8n1{c1 c5}- r9c4{n1 n5}- c2n5{r9 r4}- r4n7{c2 c1}- b4n8{r4c1 r6c3}- r6n1{c3 c4}- r6c5{n1 n2}- r4n2{c5 c7}- c7n4{r4 r5}- c3n4{r5 r1}- c4n4{r1 .} => -1r7c2
whip[12]: c9n1{r7 r9}- r9c4{n1 n5}- c2n5{r9 r4}- r4c9{n5 n9}- b5n9{r4c5 r5c6}- r2n9{c6 c2}- c2n1{r2 r6}- r5n1{c1 c4}- b5n3{r5c4 r6c4}- r6n4{c4 c3}- r5c1{n4 n6}- r5c3{n6 .} => -5r7c9
whip[12]: r9n9{c7 c9}- r4c9{n9 n5}- r2n5{c9 c4}- r9c4{n5 n1}- b5n1{r5c4 r6c5}- c2n1{r6 r2}- r2n9{c2 c6}- c5n9{r1 r4}- b5n2{r4c5 r4c6}- c6n8{r4 r3}- r1c5{n8 n6}- r3c5{n6 .} => -5r9c7
whip[14]: c7n8{r1 r2}- r2n5{c7 c4}- c4n7{r2 r1}- b2n4{r1c4 r3c6}- c6n8{r3 r4}- c4n8{r6 r7}- b8n3{r7c4 r8c6}- r5c6{n3 n9}- r4c5{n9 n2}- r6c5{n2 n1}- c4n1{r5 r9}- c2n1{r9 r2}- r2n9{c2 c9}- c8n9{r1 .} => -5r1c7
whip[14]: r7n4{c1 c2}- c2n5{r7 r4}- r4n7{c2 c1}- b4n8{r4c1 r6c3}- r6n4{c3 c4}- r4n4{c6 c7}- b6n2{r4c7 r6c8}- r6c5{n2 n1}- r5c4{n1 n3}- r5c6{n3 n9}- r4n9{c5 c9}- r2n9{c9 c2}- c2n1{r2 r9}- r8n1{c1 .} => -5r7c1
whip[17]: b2n4{r3c6 r1c4}- c4n7{r1 r2}- b2n5{r2c4 r1c5}- c5n9{r1 r4}- r4c9{n9 n5}- r2n5{c9 c7}- r5n5{c7 c1}- r8n5{c1 c8}- b9n7{r8c8 r9c9}- c9n9{r9 r2}- r1n9{c7 c2}- c2n3{r1 r3}- r3n4{c2 c1}- r3n8{c1 c5}- c6n8{r2 r4}- r4c1{n8 n7}- c2n7{r4 .} => -9r3c6
whip[17]: b4n8{r6c3 r4c1}- r4n7{c1 c2}- b4n5{r4c2 r5c1}- r5n1{c1 c4}- r9c4{n1 n5}- c2n5{r9 r7}- c5n5{r7 r1}- c8n5{r1 r8}- b9n7{r8c8 r9c9}- r9n1{c9 c2}- r2n1{c2 c1}- r2n2{c1 c3}- c3n8{r2 r1}- c3n4{r1 r5}- c7n4{r5 r4}- c7n5{r4 r2}- c7n8{r2 .} => -1r6c3

whip[29]: c7n8{r1 r2}- c1n8{r2 r4}- c6n8{r4 r3}- b2n4{r3c6 r1c4}- c4n7{r1 r2}- b2n5{r2c4 r1c5}- b3n5{r1c8 r2c9}- r4c9{n5 n9}- r4c5{n9 n2}- c5n9{r4 r3}- r2c6{n9 n6}- r9c6{n6 n2}- r4c6{n2 n4}- r4c7{n4 n5}- r4c2{n5 n7}- b4n5{r4c2 r5c1}- r8n5{c1 c8}- b9n7{r8c8 r9c9}- r9n9{c9 c7}- b3n9{r1c7 r1c8}- r1n7{c8 c1}- c3n7{r1 r8}- c3n2{r8 r2}- r2c1{n2 n1}- r8n1{c1 c5}- c5n6{r8 r7}- b9n6{r7c7 r8c7}- r1n6{c7 c2}- c1n6{r1 .} => -8r1c3

whip[6]: c3n8{r6 r2}- c1n8{r1 r4}- c6n8{r4 r3}- b2n4{r3c6 r1c4}- c3n4{r1 r5}- r6n4{c2 .} => -6r6c3
whip[7]: r1n4{c1 c4}- r6n4{c4 c3}- c3n8{r6 r2}- r2n2{c3 c1}- r2n1{c1 c2}- c2n9{r2 r1}- c2n3{r1 .} => -4r3c2
whip[6]: r3n4{c6 c1}- r3n8{c1 c5}- c6n8{r2 r4}- b4n8{r4c1 r6c3}- c3n4{r6 r5}- c6n4{r5 .} => -6r3c6
whip[10]: r4n8{c5 c1}- r3n8{c1 c6}- r3n4{c6 c1}- r7n4{c1 c2}- r1n4{c2 c4}- c4n7{r1 r2}- c4n8{r2 r7}- c4n5{r7 r9}- c2n5{r9 r4}- r4n7{c2 .} => -8r6c5
whip[6]: r6c5{n1 n2}- r4n2{c5 c7}- c7n4{r4 r5}- c4n4{r5 r1}- c3n4{r1 r6}- r6n8{c3 .} => -1r6c4
whip[2]: r6n1{c2 c5}- r8n1{c5 .} => -1r9c2
whip[6]: r4c9{n5 n9}- b5n9{r4c5 r5c6}- r2n9{c6 c2}- c2n1{r2 r6}- r6c5{n1 n2}- r4n2{c5 .} => -5r4c7
whip[6]: r7n8{c5 c4}- c4n1{r7 r5}- c4n3{r5 r6}- r6n8{c4 c3}- r6n4{c3 c2}- r6n1{c2 .} => -1r7c5
whip[6]: r4c9{n5 n9}- b5n9{r4c5 r5c6}- r2n9{c6 c2}- c2n1{r2 r6}- r5n1{c1 c4}- r9c4{n1 .} => -5r9c9
whip[7]: b5n9{r4c5 r5c6}- r2n9{c6 c2}- c2n1{r2 r6}- r5n1{c1 c4}- b5n3{r5c4 r6c4}- r6n4{c4 c3}- r6n8{c3 .} => -9r4c9
Single: 5r4c9
Single: 5r5c1
Hidden pair: 16-r5c3-r6c2 => -4r5c3 -4r6c2
Hidden pair: 48-r6c3-r6c4 => -3r6c4
Alignment: 3-r6-b6 => -3r5c7 -3r5c8
whip[2]: r5n1{c3 c4}- c5n1{r6 .} => -1r8c3
whip[3]: c4n7{r1 r2}- r2n5{c4 c7}- c7n8{r2 .} => -8r1c4
whip[4]: r6c4{n4 n8}- c3n8{r6 r2}- c6n8{r2 r3}- c6n4{r3 .} => -4r5c4
whip[2]: c3n4{r1 r6}- c4n4{r6 .} => -4r1c1
whip[2]: c3n4{r1 r6}- c4n4{r6 .} => -4r1c2
whip[4]: r7n4{c1 c2}- c2n5{r7 r9}- r9c4{n5 n1}- r8n1{c5 .} => -1r7c1
whip[3]: c1n1{r2 r8}- c5n1{r8 r6}- r5n1{c4 .} => -1r2c3
whip[4]: r6c2{n6 n1}- r5n1{c3 c4}- r9c4{n1 n5}- c2n5{r9 .} => -6r7c2
whip[4]: r6c9{n3 n6}- r5n6{c7 c3}- r5n1{c3 c4}- r7n1{c4 .} => -3r7c9
whip[4]: r9n5{c2 c4}- r2n5{c4 c7}- r8n5{c7 c8}- r8n7{c8 .} => -7r9c2
whip[3]: r2n2{c3 c1}- c1n1{r2 r8}- b7n7{r8c1 .} => -7r2c3
whip[3]: r8n1{c1 c5}- r9c4{n1 n5}- r9c2{n5 .} => -6r8c1
whip[4]: r6c2{n6 n1}- r5n1{c3 c4}- r9c4{n1 n5}- r9c2{n5 .} => -6r1c2
whip[4]: r2n1{c2 c1}- r8n1{c1 c5}- r9c4{n1 n5}- r9c2{n5 .} => -6r2c2
whip[4]: r6c2{n6 n1}- r5n1{c3 c4}- r9c4{n1 n5}- r9c2{n5 .} => -6r3c2
whip[4]: r5n1{c4 c3}- b4n6{r5c3 r6c2}- r9c2{n6 n5}- r9c4{n5 .} => -1r7c4
Single: 1r7c9
whip[5]: r4c2{n7 n4}- r6n4{c3 c4}- r1c4{n4 n5}- r9n5{c4 c2}- r7c2{n5 .} => -7r1c2
whip[5]: c3n4{r1 r6}- c3n8{r6 r2}- r2n2{c3 c1}- c1n1{r2 r8}- b7n7{r8c1 .} => -7r1c3
Alignment: 7-c3-b7 => -7r8c1
whip[3]: r6n2{c8 c5}- c5n1{r6 r8}- r8c1{n1 .} => -2r8c8
whip[4]: r8c1{n2 n1}- c5n1{r8 r6}- r5c4{n1 n3}- b8n3{r7c4 .} => -2r8c6
whip[5]: r5n3{c6 c4}- r5n1{c4 c3}- c2n1{r6 r2}- r2n9{c2 c9}- c8n9{r1 .} => -9r5c6
Alignment: 9-r5-b6 => -9r4c7
whip[3]: r6c4{n8 n4}- r5c6{n4 n3}- b8n3{r8c6 .} => -8r7c4
Single: 8r7c5
Hidden pair: 48-r3c1-r3c6 => -6r3c1 -7r3c1
Naked triplet: 135-r5c4-r7c4-r9c4 => -5r1c4 -5r2c4
Single: 5r2c7
Single: 5r1c5
Single: 5r8c8
Single: 7r8c3
Single: 7r9c9
Single: 9r9c7
Single: 9r5c8
Single: 9r1c2
Single: 3r3c2
Single: 7r3c8
Single: 8r1c7
Single: 3r1c8
Single: 3r6c9
Alignment: 6-r1-b1 => -6r2c1 -6r2c3
Hidden pair: 69-r2c6-r2c9 => -8r2c6
whip[2]: c3n8{r2 r6}- c4n8{r6 .} => -8r2c1
whip[2]: c8n6{r7 r6}- c2n6{r6 .} => -6r7c1

STTE

And my “Few Steps” resolution:

Hidden Text: Show

whip[29]: r7n4{c1 c2}- r1n4{c2 c4}- r6n4{c4 c3}- b4n8{r6c3 r4c1}- r4n7{c1 c2}- b4n5{r4c2 r5c1}- c2n5{r4 r9}- r9c4{n5 n1}- r5c4{n1 n3}- r5n1{c4 c3}- b4n6{r5c3 r6c2}- r6c9{n6 n3}- r6c4{n3 n8}- r7c4{n8 n5}- r2c4{n5 n7}- b2n5{r2c4 r1c5}- c8n5{r1 r8}- b9n7{r8c8 r9c9}- c9n1{r9 r7}- b7n1{r7c1 r8c1}- c1n7{r8 r1}- c8n7{r1 r3}- r3n3{c8 c2}- r1c2{n3 n9}- c8n9{r1 r5}- r5n6{c8 c7}- b9n6{r7c7 r7c8}- r1n6{c8 c3}- c1n6{r1 .} => -4r3c1

whip[20]: r3n4{c6 c2}- c2n3{r3 r1}- c2n9{r1 r2}- r2c6{n9 n6}- r3c5{n6 n9}- r1c5{n9 n5}- r2c4{n5 n7}- r2c9{n7 n5}- r4c9{n5 n9}- b5n9{r4c5 r5c6}- c6n4{r5 r4}- c7n4{r4 r5}- c1n4{r5 r7}- b4n4{r4c1 r6c3}- b4n8{r6c3 r4c1}- r4c5{n8 n2}- b6n2{r4c7 r6c8}- r7n2{c8 c7}- c7n3{r7 r8}- c6n3{r8 .} => -8r3c6

whip[2]: r3n8{c1 c5}- c6n8{r2 .} => -8r4c1
Single: 8r6c3

whip[11]: c7n4{r5 r4}- b6n2{r4c7 r6c8}- r6c5{n2 n1}- r5n1{c4 c1}- r5c4{n1 n3}- r5c6{n3 n9}- r4n9{c5 c9}- r9n9{c9 c7}- r2n9{c7 c2}- r2n1{c2 c3}- r8n1{c3 .} => -4r5c3
Single: 4r1c3
Single: 4r3c6

whip[11]: c4n8{r1 r7}- b8n3{r7c4 r8c6}- r5c6{n3 n9}- b2n9{r2c6 r1c5}- r4c5{n9 n2}- r6c5{n2 n1}- c4n1{r5 r9}- c9n1{r9 r7}- c2n1{r7 r2}- c2n9{r2 r3}- c8n9{r3 .} => -8r3c5
Single: 8r3c1

whip[12]: r3c5{n6 n9}- r2c6{n9 n8}- c4n8{r1 r7}- b8n3{r7c4 r8c6}- r5c6{n3 n9}- r4c6{n9 n2}- r6c5{n2 n1}- c4n1{r5 r9}- c9n1{r9 r7}- c2n1{r7 r2}- c2n9{r2 r1}- c8n9{r1 .} => -6r1c5

whip[13]: b2n6{r2c6 r3c5}- b2n9{r3c5 r1c5}- r1n8{c5 c7}- c4n8{r1 r7}- b8n3{r7c4 r8c6}- r5c6{n3 n9}- r4c6{n9 n2}- r6c5{n2 n1}- c4n1{r5 r9}- c9n1{r9 r7}- c2n1{r7 r2}- c2n9{r2 r3}- c8n9{r3 .} => -8r2c6
Single: 8r4c6
Alignment: 2-c6-b8 => -2r7c5 -2r8c5
Naked pair: 69-r2c6-r3c5 => -9r1c5

whip[8]: b5n1{r5c4 r6c5}- c5n2{r6 r4}- c5n9{r4 r3}- c6n9{r2 r5}- c8n9{r5 r1}- c2n9{r1 r2}- c2n1{r2 r7}- r8n1{c1 .} => -1r9c4
Single: 5r9c4
Single: 5r1c5
Single: 8r7c5

whip[8]: r6c5{n2 n1}- c4n1{r5 r7}- c9n1{r7 r9}- r9n9{c9 c7}- r4n9{c7 c9}- c5n9{r4 r3}- r2n9{c6 c2}- c2n1{r2 .} => -2r4c5

STTE

Not bad, isn't it ?

[yzfwsf]

The solution path of my solver is very complicated.

20201207204746.png (69.57 KiB) Viewed 818 times

[Cenoman]

Code: Select all

 +--------------------------+------------------------+--------------------------+
 |  67-48   34679   4678    |  4578   5689    1      |  35689   35679   2       |
 |  12678   67-1    12678   |  578    3       689    |  5689    4       5679    |
 |  4678    34679   5       |  2      689     4689   |  1       3679    3679    |
 +--------------------------+------------------------+--------------------------+
 |  4578    457     3       |  6      289     2489   |  2459    1       59      |
 |  1456    2       146     |  134    7       349    |  34569   3569    8       |
 |  9       146     1468    |  1348   128     5      |  7       236     36      |
 +--------------------------+------------------------+--------------------------+
 |  12456   1456    9       |  1358   12568   7      |  56-23   2356    1356    |
 |  12567   8       1267    |  9      1256    236    |  2356    567-23  4       |
 |  3       1567    1267    |  15     4       26     |  2569    8       567-19  |
 +--------------------------+------------------------+--------------------------+

The puzzle has a main diagonal symmetry of givens, with the following digit correspondance (19 23 48 55 66 77) => only 5, 6, 7 can be on the main diagonal in b19; 2 placements and basics.

Code: Select all

 +----------------------+-----------------------+-----------------------+
 |  67     39    48     |  4578   5689   1      |  3568   3569   2      |
 |  12     67    12     |  578    3      689*   |  568    4      569*   |
 |  48     39    5      |  2      689    4689   |  1      3679   3679   |
 +----------------------+-----------------------+-----------------------+
 |  4578   457   3      |  6      289*   2489*  |  245    1      59*    |
 |  1456   2     146    |  134*   7      34-9   |  3456   3569   8      |
 |  9      146*  1468   |  1348*  28-1   5      |  7      236    36     |
 +----------------------+-----------------------+-----------------------+
 |  2456   456   9      |  358    2568   7      |  56     23     1      |
 |  1256   8     1267   |  9      1256   236    |  23     567    4      |
 |  3      156*  1267   |  15*    4      26     |  9      8      567    |
 +----------------------+-----------------------+-----------------------+

Two symmetrical finned X-wings solve the puzzle now:
(1)r6c2 = r9c2 - r9c4 = r56c4 => -1 r6c5; -9 r5c6 by symmetry; ste

[DEFISE]

Wow fine Cenoman !

Apparently SE works without looking for symmetries, putting a score of 9.4

[denis_berthier]

I know this puzzle, it is on page 137 of your PCS book (Nov 2012). I had checked it in May (see my post of May 20) .
I find W = 29 because my whip [29] has 2 loops (in bold).
Here is my “Simplest First” resolution.

The r1c3≠8 elimination seems to be a necessary point of passage. It's the same as done by the no-loop whip[31].
I had never checked that it didn't depend on the previous eliminations.

And my “Few Steps” resolution:
[...]
Not bad, isn't it ?

Yes, very good.

What are the relative computation times of the two solutions?

[denis_berthier]

The puzzle has a main diagonal symmetry of givens, with the following digit correspondance (19 23 48 55 66 77) => only 5, 6, 7 can be on the main diagonal in b19; 2 placements and basics.

It's great to have noticed this!

[denis_berthier]

The solution path of my solver is very complicated.

It looks much like SudokuExplainer. Do you have the same dynamic/forcing contradiction chains ?

[denis_berthier]

SE works without looking for symmetries, putting a score of 9.4

The 9.4 score is because of the long dynamic forcing chains in SE.
However, even without considering symmetries, it's much easier than it should be for W=31

[DEFISE]

What are the relative computation times of the two solutions?

With Java langage on a laptop (double i5 processor 2,3 Ghz):
“Simplest first” => 10s
“Few Steps” => < 5s, but I did 15 executions with a random variable which allows to change the order of tied (*) targets.
I obviously chose the shorter result.
(*) i.e targets which have the same criterion score.

[denis_berthier]

What are the relative computation times of the two solutions?

With Java langage on a laptop (double i5 processor 2,3 Ghz):
“Simplest first” => 10s
“Few Steps” => < 5s, but I did 15 executions with a random variable which allows to change the order of tied (*) targets.

For "few steps", do you mean the total time is 10 (to get the max 31) + 15*5 ?

[ghfick]

Andrew Stuart's solver [sudokuwiki.org] detects the symmetry of givens. He refers to this technique as 'Gurth's Theorem'.
May I suggest that YZF_Sudoku should have this technique added?

[DEFISE]

With Java langage on a laptop (double i5 processor 2,3 Ghz):
“Simplest first” => 10s
“Few Steps” => < 5s, but I did 15 executions with a random variable which allows to change the order of tied (*) targets.

For "few steps", do you mean the total time is 10 (to get the max 31) + 15*5 ?

Exact but for "few steps" it's an average: 1 or to 2 executions where much longer than the others (20s).
So in total about 1mn30.
I add that I consider few basic techniques: singles, pairs, naked triplets.

[Cenoman]

Wow fine Cenoman !

It's great to have noticed this!

Andrew Stuart's solver [sudokuwiki.org] detects the symmetry of givens. He refers to this technique as 'Gurth's Theorem'.
May I suggest that YZF_Sudoku should have this technique added?

Thank you Denis and François.
I didn't run Andrew's solver, but, of course, nobody has to trust me. There is no need of a solver to spot a patent symmetry as this one. In fact, Denis made me think of checking, by mentionning Mauricio's name. I was aware of his great interest in symmetric puzzles.

Andrew's solver detects this one, but if the puzzle is morphed a bit more (e.g; by circular swap of bands 1,2,3 to 2,3,1), it detects no longer the "symmetry", actually the automorphism, (nor would I have detected it manually). It doesn't detect the "stick symmetry" either (whether morphed or not).

What would be useful in a solver, would be detecting automorphic puzzles, for any automorphism.

[denis_berthier]

In fact, Denis made me think of checking, by mentionning Mauricio's name. I was aware of his great interest in symmetric puzzles.
Andrew's solver detects this one, but if the puzzle is morphed a bit more (e.g; by circular swap of bands 1,2,3 to 2,3,1), it detects no longer the "symmetry", actually the automorphism, (nor would I have detected it manually). It doesn't detect the "stick symmetry" either (whether morphed or not).

The fun of it is, I made a random morph so that it didn't look too similar fo Maurico's original puzzle. I had no idea I was making symmetry more visible.