The New Sudoku Players' Forum

[Mauriès Robert]

Hi all,
I offer you this puzzle without great difficulty, but for which one step is not enough, it seems to me.
Good sudoku.
Robert
.1....56..4...2.....36...4.6...14..8...3.8...1..79...4.9...74.....4...3..72....8.

puzzle: Show

solution: Show

[Cenoman]

Two steps (near missed Robert's challenge )

Code: Select all

 +-----------------------+------------------------+---------------------------+
 |  2789    1      79    |  89     4      39      |  5       6       2379     |
 |  5789    4      6     |  1589   3578   2       |  1789    179     1379     |
 |  25789   58     3     |  6      578    159     |  12789   4       1279     |
 +-----------------------+------------------------+---------------------------+
 |  6       235    79    |  25     1      4       |  2379    2579    8        |
 |  79      25     4     |  3      256    8       |  12679   12579   125679   |
 |  1       2358   8-5    |  7      9      56      |  236     25      4        |
 +-----------------------+------------------------+---------------------------+
 |  3       9      158   |  1258   2568   7       |  4       125     1256     |
 |  58      6      158   |  4      258    159     |  1279    3       12579    |
 |  4       7      2     |  159    356    13569   |  169     8       1569     |
 +-----------------------+------------------------+---------------------------+

1. Almost-almost Y-wing (as a net):

Code: Select all

[Y-Wing (5=1)r7c3 - (1=2)r7c8 - (2=5)r6c8] *
 ||
(5)r7c8 - r789c9 = (5)r5c9 - (5=26)r5c25 - (6=5)r6c6 *
 ||
 ||     (8=5)r6c3 - (2=5)r5c2 - (2)r5c5       (5)r3c6 - r3c2 = (5)r456c2 *
 ||    /                         ||            ||
(8)r7c3                         (236)b8p289 - (5)r9c6
       \                         ||            ||
        (8)r8c13 = (8)r8c5 - - -(2)r8c5       (5)r6c6 *
                                               ||
                                              (5)r8c6 - r8c1 = r78c3 *
-------------------
=> -5 r6c3; 7 placements & basics

Code: Select all

 +--------------------+--------------------+--------------------------+
 |  279    1     79   |  8     4     39    |  5       6       2379    |
 |  579    4     6    |  159   357   2     |  8       179     1379    |
 |  2579   8     3    |  6     57    159   |  1279    4       1279    |
 +--------------------+--------------------+--------------------------+
 |  6      235   79   | a25    1     4     |  2379    279-5   8       |
 |  79     25    4    |  3     256   8     |  12679   12579   12579   |
 |  1      235   8    |  7     9     6-5   |  236    d25      4       |
 +--------------------+--------------------+--------------------------+
 |  3      9     15   | b125   8     7     |  4      c125     6       |
 |  8      6     15   |  4     25    159   |  1279    3       12579   |
 |  4      7     2    |  159   36    36    |  19      8       159     |
 +--------------------+--------------------+--------------------------+

2. W-Wing (5=2)r4c4 - r7c4 = r7c8 - (2=5)r6c8 => -5 r6c6, r4c8; ste

[Mauriès Robert]

Hi Cenoman,
Your resolution based on the hidden Y-wing is quite "tortuous", but I admire your "vista" and your ability to find complex paths.
Here is a more direct two-step resolution. It is an adaptation of a resolution proposed by François C. (pseudo NSPF=DEFISE) in the Sudoku Assistant forum.

puzzle1: Show

P'(5r6c38, 8) : (-5r6c38)=> [2r6c8 and (8r6c3->8r3c2->8r1c4)->8r7c5->6r7c9]->2r7c4->5r4c4
Or as a diagram

Code: Select all

                              ->2r6c8-------------------------
                            /                                  \
P'(5r6c38, 8) : (-5r6c38)=> ->8r6c3->8r3c2->8r1c4->8r7c5->6r7c9->2r7c4->5r4c4
                                   \             /      \      /
                                     -----------          -----


=> -5r6c6 => r6c6=6.

puzzle2: Show

P'(8r8c1, 8) : (-8r8c1)=> 8r78c3->[[[5r6c3->5r5c5 and 2r6c8->1r7c8]->8r7c3]->25r47c4]->5r2c1
Or as a diagram

Code: Select all

                                           ->5r5c5----------------
                                         /             -----       \
                                        /            /       \      \
P'(8r8c1, 8) : (-8r8c1)=> 8r78c3->5r6c3->2r6c8->1r7c8->8r7c3->25r47c4->5r2c1
                                        \            /
                                          ----------



=> -5r8c1 => r8c1=8, stte.
In this resolution, the length of the two anti-tracks is 8. It is possible to solve in 5 steps with anti-tracks of length 5, which suggests that the level of the puzzle according to Denis Berthier's quotation is W=5. I hope that Denis will confirm. The TDP level is 2.
Cordialy
Robert

[denis_berthier]

It is possible to solve in 5 steps with anti-tracks of length 5, which suggests that the level of the puzzle according to Denis Berthier's quotation is W=5. I hope that Denis will confirm.

W=5 yes.
But it can't be a conclusion of the only existence of a solution with anti-tracks of lengths ≤ 5. W could be less.
Anti-tracks as you defined them are not necessarily minimal and they don't necessarily have any continuity property. In another thread, you said they are sets, so they are not even necessarily properly ordered to easily translate into a (non-minimal) braid.

[DEFISE]

...It is an adaptation of a resolution proposed by François C. (pseudo NSPF=DEVISE) ...

Hi Robert,
my pseudo is DEFISE as DEep FIrst SEarch

[Mauriès Robert]

...It is an adaptation of a resolution proposed by François C. (pseudo NSPF=DEVISE) ...

Hi Robert,
my pseudo is DEFISE as DEep FIrst SEarch

Excuse me Francois, I have corrected
A suggestion: to answer Denis, you should publish your resolution in 5 steps of length ≤5.
Friendly
Robert

[denis_berthier]

my pseudo is DEFISE as DEep FIrst SEarch

it's depth-first search

[denis_berthier]

Hi Denis,
Could you publish a resolution of Robert puzzle 2020-11-14 with whips and another one with braids. This would help DEFISE and me to better understand.
Thank you in advance

OK

1) Using only whips:

Code: Select all

(solve ".1....56..4...2.....36...4.6...14..8...3.8...1..79...4.9...74.....4...3..72....8.")
***********************************************************************************************
***  SudoRules 20.1.s based on CSP-Rules 2.1.s, config = W
***  Using CLIPS 6.32-r773
***********************************************************************************************
singles ==> r9c1 = 4, r5c3 = 4, r7c1 = 3, r8c2 = 6, r2c3 = 6, r1c5 = 4
178 candidates, 995 csp-links and 995 links. Density = 6.32%
whip[1]: c9n3{r2 .} ==> r2c7 ≠ 3
whip[2]: c3n7{r1 r4} - c3n9{r4 .} ==> r1c3 ≠ 8
whip[2]: b4n7{r4c3 r5c1} - b4n9{r5c1 .} ==> r4c3 ≠ 5
whip[2]: b4n7{r5c1 r4c3} - b4n9{r4c3 .} ==> r5c1 ≠ 2, r5c1 ≠ 5
whip[1]: b4n2{r6c2 .} ==> r3c2 ≠ 2
whip[2]: c4n2{r4 r7} - c8n2{r7 .} ==> r4c7 ≠ 2
whip[4]: r6c8{n2 n5} - r6c6{n5 n6} - r5c5{n6 n5} - r5c2{n5 .} ==> r5c9 ≠ 2, r5c8 ≠ 2, r5c7 ≠ 2
whip[5]: r7n6{c9 c5} - b8n2{r7c5 r8c5} - b8n8{r8c5 r7c4} - r1n8{c4 c1} - r1n2{c1 .} ==> r7c9 ≠ 2
whip[5]: r8c1{n8 n5} - r8c5{n5 n2} - b9n2{r8c9 r7c8} - r6c8{n2 n5} - r6c3{n5 .} ==> r8c3 ≠ 8
whip[2]: r8n8{c5 c1} - r1n8{c1 .} ==> r7c4 ≠ 8, r2c5 ≠ 8, r3c5 ≠ 8
whip[4]: r7n8{c5 c3} - r6c3{n8 n5} - c6n5{r6 r3} - c2n5{r3 .} ==> r7c5 ≠ 5
whip[5]: r7n8{c5 c3} - r6c3{n8 n5} - r5c2{n5 n2} - c5n2{r5 r8} - r8n8{c5 .} ==> r7c5 ≠ 6
hidden-single-in-a-row ==> r7c9 = 6
whip[2]: r9n6{c5 c6} - r9n3{c6 .} ==> r9c5 ≠ 5
whip[2]: r9n6{c6 c5} - r9n3{c5 .} ==> r9c6 ≠ 9, r9c6 ≠ 1, r9c6 ≠ 5
whip[3]: c2n5{r6 r3} - c1n5{r3 r8} - c6n5{r8 .} ==> r6c3 ≠ 5
singles ==> r6c3 = 8, r3c2 = 8, r8c1 = 8, r7c5 = 8, r1c4 = 8, r2c7 = 8[color=#40BF40][/color]
whip[3]: b7n5{r7c3 r8c3} - r8c5{n5 n2} - b9n2{r8c7 .} ==> r7c8 ≠ 5
whip[1]: b9n5{r9c9 .} ==> r5c9 ≠ 5
whip[3]: r9c7{n1 n9} - c4n9{r9 r2} - r2n1{c4 .} ==> r3c7 ≠ 1
whip[3]: r6c8{n5 n2} - r7n2{c8 c4} - r4c4{n2 .} ==> r6c6 ≠ 5
stte

Notice that I didn't try to manually discard potentially useless eliminations. It is likely that some could be eliminated.

2) Now, what do we get if we use braids:
errrr.... The EXACT same path.
The only difference is, it took SudoRules 3.34s using only whips but 54.35 s. using braids.

So, why do we get the same paths? For reasons that I've kept repeating over the years:

1) Whips are a (very) special type of braids (structurally much simpler and much easier to find, thanks to the continuity property)
2) BUT the resolution power of whips is almost the same as that of braids and I've observed on millions of puzzles that braids rarely appear when whips are active. This is what I call the whips miracle - and it applies to other logic puzzles than Sudoku.
3) Considering the above two points, I've hard coded in CSP-Rules that the activation of braids automatically implies the activation of whips (the latter having higher priority than braids of same length).


Note that there are rare cases where whips are not enough (see examples in PBCS). These cases appear mainly in the SER 9.2 to 9.3 range (and recently in a 9.5). But in such cases g-whips often provide faster and nicer results. That's why, in my hierarchy, g-whips come before braids of same length.

[Edit]: you wanted only whips/braids. I've therefore not activated Subsets, but they appear here as whips.

[DEFISE]

A suggestion: to answer Denis, you should publish your resolution in 5 steps of length ≤5.
Friendly

Yes, here is my resolution in which P(A,n) means the first n candidates of a track resulting from candidate A.

Singles: 4L1C5, 6L2C3, 4L9C1, 4L5C3, 3L7C1, 6L8C2
Alignment: 3-C9-B3 => -3L2C7
Hidden pair: 79-L1C3-L4C3 => -8L1C3 -5L4C3
Hidden pair: 79-L4C3-L5C1 => -2L5C1 -5L5C1
Alignment: 2-C1-B1 => -2L3C2

1) P(2L7C9,5) : 2L7C9, 2L1C1, 8L1C4, 6L7C5, 2L8C5 => impossibility in 8C5 => -2L7C9
2) P(8L8C3,5) : 8L8C3, 5L6C3, 2L6C8, 5L8C1, 2L8C5 => impossibility in 2L7 => -8L8C3
3) P(8L7C4,2) : 8L7C4, 8L1C1 => impossibility in 8L8 => -8L7C4
Alignment: 8-C4-B2 => -8L2C5 -8L3C5

4) P(6L7C5,5) : 6L7C5, 8L7C3, 5L6C3, 2L5C2, 8L8C5 => impossibility in 2C5 => -6L7C5
Single: 6L7C9
Hidden pair: 36-L9C5-L9C6 => -5L9C5 -1L9C6 -5L9C6 -9L9C6

5) P(5L6C6,5) : 5L6C6, 2L4C4, 8L6C3, 2L6C8, 2L7C5 => impossibility in 8L7 => -5L6C6
Singles to the end.
N.B : all of these tracks can easily be translated into braids of the same length.

[DEFISE]

Hi Denis,
Could you publish a resolution of Robert puzzle 2020-11-14 with whips and another one with braids. This would help DEFISE and me to better understand.
Thank you in advance

OK
1) Using only whips:
....
....
2) Now, what do we get if we use braids:
errrr.... The EXACT same path.
The only difference is, it took SudoRules 3.34s using only whips but 54.35 s. using braids.
So, why do we get the same paths? For reasons that I've kept repeating over the years:
....

I agree with you. I also get the same with braids with my “simplest first” program.
But the resolution I just gave is the result of another program which is looking for the minimum of steps for a given maximum track length.
It turns out that this second program gave 5 steps with the "braids" option and 6 steps with the "whips" option.
This does not mean that there is no resolution with 5 whips [<=5], or even less.
This second program does not guarantee optimum results because it's very difficult to minimize the number of steps.

[denis_berthier]

This second program does not guarantee optimum results because it's very difficult to minimize the number of steps.

Sure. And the question is, how does that scale up with the maximum necessary length?

[DEFISE]

Sure. And the question is, how does that scale up with the maximum necessary length?

I'm not sure what you meant.
You ask me how does the difficulty of optimizing the minimum number of steps increase with the W-rating (or B-rating).
That's right ?

[denis_berthier]

Sure. And the question is, how does that scale up with the maximum necessary length?

I'm not sure what you meant.
You ask me how does the difficulty of optimizing the minimum number of steps increase with the maximum length I set in my 2nd program. That's right ?

yes

[DEFISE]

Sure. And the question is, how does that scale up with the maximum necessary length?

I'm not sure what you meant.
You ask me how does the difficulty of optimizing the minimum number of steps increase with the maximum length I set in my 2nd program. That's right ?

yes

I had changed my previous post a bit while you were replying to me, but whatever my answer is the following:

1) My algorithm to minimize the number of steps is the same regardless of this maximum size. It is quite rustic and I don't have new ideas to improve it.
2) I have the same problem as in the "simplest first" program when the maximum size increase: combinatorial explosion and therefore memory saturation or astronomical run time. All this especially with the braids obviously, hence
in the interest of the whips, we agree on that.

[denis_berthier]

1) My algorithm to minimize the number of steps is the same regardless of this maximum size. It is quite rustic and I don't have new ideas to improve it.

Does this algorithm produce and compare several resolution paths?
If yes, does some parameter in it depend on the maximum length? As the number of possible resolution paths increases exponentially with maximal length (in the mean), checking only a constant number of resolution paths would make the "shortest" solution less and less likely to be really the shortest or close to it.