The New Sudoku Players' Forum

[DEFISE]

Does this algorithm produce and compare several resolution paths?

No it's less elaborate than that. The principle is as follows:
1) Performing basic techniques
If solution => END.
2) Search for all potential targets, i.e all the candidates who give a contradiction, using singles only.
3) Sort these targets according to two criteria* so that the best targets are at the top of the list.
4) Selection of the first target T of the list which is also the target of a whip [n], n <= max-length parameter (if option = whip).
5) Deletion of T. Return to (1)

* Criterion 1 = number of candidates who would be removed by applying the basic techniques after removing the target. (must be as big as possible)
Criterion 2 = number of candidates of the smallest entity (CSP variable) containing the target (must be as small as possible).

[Cenoman]

Here is a more direct two-step resolution.

DEFISE's solution is nicer than mine. I have written it my own way, (two krakens with short embedded chains). Also written a reasonable solution with short chains;

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   58    |  7      9      6-5     |  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     |
 +-----------------------+------------------------+---------------------------+

Kraken row (2)r7c4589
(2)r7c4 - (2=5)r4c4
(2)r7c8 - (2=5)r6c8
(2-6)r7c9 = r7c5 - r5c5 = (6)r6c6
(2-8)r7c5 = [r7c3 *=* r7c4 - r1c4 = r1c1 - r3c2 = r6c2] - (8=5)r6c3
=> -5 r6c6

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      25     8      |  1679    179    1679    |
 |  1       2358   8-5   |  7      9      6      |  23      25     4       |
 +-----------------------+-----------------------+-------------------------+
 |  3       9      158   |  1258   2568   7      |  4       12     1256    |
 |  58      6      158   |  4      258    159    |  1279    3      12579   |
 |  4       7      2     |  159    356    1359   |  169     8      1569    |
 +-----------------------+-----------------------+-------------------------+

Kraken cell (1258)r7c4
(1)r7c4 - (1=25)r67c8
(2)r7c4 - (2=5)r4c4 - r5c5 = (5)r5c2
(5)r7c4 - r89c6 = r3c6 - r3c2 = (5)r456c2
(8)r7c4 - r7c3 = [Y-Wing (5=1)r7c3 - (1=2)r7c8 - (2=5)r6c8]
=> -5 r6c3; ste

As regards a "reasonable" solution, here is one in six simple steps :

Hidden Text: Show

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      2-5    4     |  3      256    8       |  1679-2  1579-2  15679-2  |
 |  1       2358   58    |  7      9      6-5     |  236     25      4        |
 +-----------------------+------------------------+---------------------------+
 |  3       9      158   |  125-8  2568   7       |  4       125     156-2    |
 |  58      6      158   |  4      28-5   159     |  1279    3       12579    |
 |  4       7      2     |  159    356    13569   |  169     8       1569     |
 +-----------------------+------------------------+---------------------------+

1. (2=56)r5c25 - (6=582)r6c368 => -2 r5c789

2. Kraken row (8)r7c345
(8)r7c3 - r8c13 = (8-2)r8c5 = (2)r8c79
(8)r7c4 - r1c4 = (8-2)r1c1 = (2)r1c9
(8-6)r7c5 = (6)r7c9
=> -2 r7c9

3. Kraken column (9)r129c4
(9-8)r1c4 = r1c1 - (8=5)r8c1
(9)r2c4 - (15)b2p49 = (5)r23c5
(9)r9c4 - (9=185)r8c136
=>-5r8c5

4. (8)r8c5 = r8c1 - r1c1 = r1c4 => -8 r7c4
5. (5)r6c3 = r78c3 - (5=82)r8c15 - r5c5 = (2)r5c2 => -5 r5c2; 3 placements & basics
6. (5)r6c3 = r78c3 - (5=82)r8c15 - r7c45 = r7c8 - (2=5)r6c8 => -5 r6c6; ste

[StrmCkr]

Code: Select all

+----------------------+----------------------------+------------------------+
| 79(28)   1       79  | 9(8)    4         39       | 5        6      379(2) |
| 579(8)   4       6   | 1589    3578      2        | 1789     179    1379   |
| 579(28)  5(8)    3   | 6       578       159      | 1789(2)  4      179(2) |
+----------------------+----------------------------+------------------------+
| 6        5(23)   79  | 25      1         4        | 279(3)   2579   8      |
| 79       5(2)    4   | 3       56(2)     8        | 12679    12579  125679 |
| 1        5(238)  58  | 7       9         56       | 6(23)    5(2)   4      |
+----------------------+----------------------------+------------------------+
| 3        9       158 | 15(28)  -5(28-6)  7        | 4        15(2)  156(2) |
| 5(8)     6       158 | 4       5(28)     159      | 1279     3      12579  |
| 4        7       2   | 159     -5(36)    -159(36) | 19-6     8      159-6  |
+----------------------+----------------------------+------------------------+


aals [32,166] 35 Candidates,
16 Truths = {2R67 3R49 8R1 2C125 3C27 8C12 2B3 268B8}
16 Links = {2r35 6r9 8r8 2c89 8c4 1n1 46n2 789n5 9n6 6n7 8b1}
8 Eliminations --> r9c6<>159, r9c79<>6, r79c5<>5, r7c5<>6,

Finned Franken Swordfish: 5 c36b1 r368 fr2c1 fr7c3 => r8c1<>5
singles + blr
W-Wing: 5/2 in r4c4,r6c8 connected by 2 in r7c48 => r4c8,r6c6<>5
singles to the end

{you can add the swordfish to the first move: but it makes it more messy}

[SpAce]

Hi StrmCkr,

16 Truths = {2R67 3R49 8R1 2C125 3C27 8C12 2B3 268B8}
16 Links = {2r35 6r9 8r8 2c89 8c4 1n1 46n2 789n5 9n6 6n7 8b1}
8 Eliminations --> r9c6<>159, r9c79<>6, r79c5<>5, r7c5<>6,

I don't understand how that's supposed to work. It has tons of overlapping truths, which makes manual rank calculations practically impossible anyway, but even discounting that I don't see any covers for 3r4c7 or 2r7c4.

[StrmCkr]

that's the issues with xsudo

its comprised of a 2/3/6/8 overlapping fish of monster size it collapsed the puzzle to all singles but used the whole grid was trying to reduce it to more function-able eliminations.

Capture.JPG (93.46 KiB) Viewed 636 times

as its not practical

[denis_berthier]

The principle is as follows:
1) Performing basic techniques
If solution => END.
2) Search for all potential targets, i.e all the candidates who give a contradiction, using singles only.
3) Sort these targets according to two criteria* so that the best targets are at the top of the list.
4) Selection of the first target T of the list which is also the target of a whip [n], n <= max-length parameter (if option = whip).
5) Deletion of T. Return to (1)
* Criterion 1 = number of candidates who would be removed by applying the basic techniques after removing the target. (must be as big as possible)
Criterion 2 = number of candidates of the smallest entity (CSP variable) containing the target (must be as small as possible).

It makes sense, but it supposes you are not counting a Subset as a step. So, why would you count a whip[3] or whip[4] as a step?

Could you try to apply your algorithm to my "slashes" puzzle here: http://forum.enjoysudoku.com/slashes-t38406.html. I'm curious to see if the number of steps in my solution can be significantly reduced.

[DEFISE]

Could you try to apply your algorithm to my "slashes" puzzle here: http://forum.enjoysudoku.com/slashes-t38406.html. I'm curious to see if the number of steps in my solution can be significantly reduced.

Yes, here is my optimized resolution of "slashes" with the option "whips" and parameter length_max = 11
=> 12 steps.

-K just to the right of a candidate indicates that this candidate is the only one possible in its cell.
-L ... in its line (row).
-C ... in its column.
-B ... in its block.

Hidden Text: Show

Candidat unique : 1L1C8-L
Candidat unique : 5L9C8-K
1) P(7L4C5) = {7L4C5,1L9C5-C,6L3C5-C,6L4C8-C,2L4C4-L,..} => L6C5 vide => -7L4C5
Candidat unique: 7L6C5-C
2) P(6L4C4) = {6L4C4,6L5C7-B,5L5C4-K,5L2C6-B,..} => 6L2 vide => -6L4C4
3) P(2L1C4) = {2L1C4,9L4C4-K,4L8C4-K,8L7C4-K,2L7C5-K,2L4C8-L,6L3C8-C,4L3C6-K,4L1C2-C,5L1C1-L,7L7C1-K,..} => 7C8 vide => -2L1C4
4) P(5L1C1) = {5L1C1,2L1C5-L,3L1C2-L,4L3C2-C,6L3C6-K,6L4C8-C,2L4C4-L,9L4C2-L,7L7C2-C,..} => 5L7 vide => -5L1C1
5) P(6L2C4) = {6L2C4,5L5C4-K,5L1C2-L,4L3C2-C,2L3C6-K,9L6C6-K,8L6C2-K,9L4C2-B,9L9C3-L,8L7C1-B,..} => 5L7 vide => -6L2C4
Candidat unique: 6L5C4-C
Alignement: 5-C4-B2 => -5L2C6
6) P(8L1C1) = {8L1C1,2L1C5-L,3L1C2-L,4L3C2-C,6L3C6-K,6L4C8-C,2L4C4-L,9L4C2-L,7L7C2-C,5L7C1-L,..} => 2L7 vide => -8L1C1
7) P(2L7C1) = {2L7C1,3L1C1-K,2L1C5-L,1L4C5-K,7L4C1-K,..} => L8C1 vide => -2L7C1
Alignement: 2-L7-B8 => -2L8C4 -2L8C6
8) P(3L1C1) = {3L1C1,2L1C5-L,8L7C5-K,2L7C4-L,2L4C8-L,1L4C5-K,1L5C1-C,8L2C1-C,8L3C9-L,4L6C9-K,..} => L6C8 vide => -3L1C1
Candidat unique: 2L1C1-K
Candidat unique: 2L8C3-L
9) P(8L9C5) = {8L9C5,6L9C6-L,1L8C6-B,9L6C6-C,9L4C2-L,3L9C2-K,7L8C1-K,7L3C2-C,3L3C3-B,8L3C9-L,4L1C7-K,..} => 4C2 vide => -8L9C5
Alignement: 8-L9-B7 => -8L7C1 -8L7C2
Paire cachee: 28-L7C4-L7C5 => -4L7C4 -9L7C4
Alignement: 4-L7-B9 => -4L8C7 -4L8C9
10) P(5L5C3) = {5L5C3,1L5C6-K,1L4C1-L,1L9C5-C,3L9C9-K,3L8C1-L,3L4C2-B,7L5C1-B,8L5C9-K,8L2C1-C,8L3C5-L,..} => 6C5 vide => -5L5C3
Paire cachee: 15-L5C1-L5C6 => -3L5C1 -7L5C1 -8L5C1
Candidat unique: 8L2C1-C
11) P(7L2C3) = {7L2C3,5L6C3-C,9L9C3-C,9L7C7-L,4L7C8-L,4L6C9-L,8L6C2-L,..} => 8C3 vide => -7L2C3
Candidat unique: 5L2C3-K
Candidat unique: 5L1C4-L
Candidat unique: 8L7C4-C
Candidat unique: 2L7C5-K
Candidat unique: 1L4C5-K
Candidat unique: 5L5C6-K
Candidat unique: 1L5C1-K
Candidat unique: 6L9C5-K
Candidat unique: 5L6C2-L
Candidat unique: 5L7C1-L
Candidat unique: 8L9C2-C
Alignement: 7-L2-B3 => -7L3C8 -7L3C9
12) P(9L9C3) = {9L9C3,7L7C2-K,7L4C8-C,..} => 7C1 vide => -9L9C3

STTE

[DEFISE]

It makes sense, but it supposes you are not counting a Subset as a step.

Yes, I count only one candidate as a step, which is a target to be deleted.
(One step = 1) + 2) + 3) +4) + 5) in my algo).

So, why would you count a whip[3] or whip[4] as a step?

Excuse my poor English, I don't understand what you meant exactly.
You do think I really count whips as a step (which is false)
OR you suggest me to count whips as a step ?

[denis_berthier]

It makes sense, but it supposes you are not counting a Subset as a step.

Yes, I count only one candidate as a step, which is a target to be deleted.
(One step = 1) + 2) + 3) +4) + 5) in my algo).

So, why would you count a whip[3] or whip[4] as a step?

Excuse my poor English, I don't understand what you meant exactly.
You do think I really count whips as a step (which is false)
OR you suggest me to count whips as a step ?

It's clear from your previous post: your count of steps is a count of tracks, i.e. you don't count a Single or a Subset as a step in the resolution path.
But most Subsets are special cases of whips[≤4]. So would you count a track[≤4] as a step in the resolution path?

[Mauriès Robert]

Hi Denis and François,
I read with interest your exchanges about the slashes puzzle. Certainly, François' 12-step resolution counts only the whips[n≥3], but if we count in Denis' resolution only the whips[n>4], we find 21, whereas in François' resolution we count only 10 for the same W. François' resolution is therefore better optimized, it seems to me.
Robert
PS: this discussion would be better placed in the thread dedicated to slashes.

[DEFISE]

So would you count a track[≤4] as a step in the resolution path?

Yes ! (there is a track[4] in step 2 and a track[3] in step 12)

To be clear :
There are TB (basic techniques) and tracks (<=> whips).
One step = one track + possible TB.
I consider as TB : singles, alignments, nude pairs, hidden pairs, nude triplets.
I have not activated the hidden triples nor the subsets of size >= 4.

I consider all tracks of size >= 2 (whip[>=2]) because some whip[2] do not correspond to a pair and because whip[1] are alignments.

[denis_berthier]

So would you count a track[≤4] as a step in the resolution path?

Yes ! (there is a track[4] in step 2 and a track[3] in step 12)
To be clear :
There are TB (basic techniques) and tracks (<=> whips).
One step = one track + possible TB.
I consider as TB : singles, alignments, nude pairs, hidden pairs, nude triplets.
I have not activated the hidden triples nor the subsets of size >= 4.
I consider all tracks of size >= 2 (whip[>=2]) because some whip[2] do not correspond to a pair and because whip[1] are alignments.

I don't deny that in some cases your algorithm may produce interesting paths. But your way of counting the steps sounds very arbitrary. There's no logical reason for not counting a Pair/Triplet/Quad as a step - especially considering that a Subset generally produces many more eliminations than a whip.


PS: remarks on your K/L/C/B notation: it's a good idea to have added the type of CSP-variable to the tracks, but the notation for it is awful.

PPS: Robert says a track is a set, you say the underlying braid/whip can easily be reconstructed for it - which can only be true if a track is a sequence. So, what is it for you?

[DEFISE]

I don't deny that in some cases your algorithm may produce interesting paths. But your way of counting the steps sounds very arbitrary. There's no logical reason for not counting a Pair/Triplet/Quad as a step - especially considering that a Subset generally produces many more eliminations than a whip.

It’s true that TB produce more eliminations than whips, but they remain more banal and much easier to find, so I don’t count them.

PS: remarks on your K/L/C/B notation: it's a good idea to have added the type of CSP-variable to the tracks, but the notation for it is awful.

It's in a desire for compactness.

PPS: Robert says a track is a set, you say the underlying braid/whip can easily be reconstructed for it - which can only be true if a track is a sequence. So, what is it for you?

I know Robert says a track is a set of candidates but I think a track doesn't just contain candidates, in general.
What do you call sequence ?

[denis_berthier]

It’s true that TB produce more eliminations than whips, but they remain more banal and much easier to find, so I don’t count them.

So,here is the solution of a typical puzzle from mith:

Code: Select all

btte

PS: remarks on your K/L/C/B notation: it's a good idea to have added the type of CSP-variable to the tracks, but the notation for it is awful.

It's in a desire for compactness.

At the cost of readability.

What do you call sequence ?

Here, let's say a fully ordered set of candidates: C1, C2, C3...
Not any set without any order, as Robert says.

[Mauriès Robert]

Hi Denis

What do you call sequence ?

Here, let's say a fully ordered set of candidates: C1, C2, C3...
Not any set without any order, as Robert says.

Do you consider the following representation of this anti-track to be a sequence?
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
                                   \             /      \      /
                                     -----------          -----


Robert