The New Sudoku Players' Forum

[denis_berthier]

Interesting, that your logical system, which mainly works with memory chains, is suffering from dementia, and can't remember, which numbers were given.

You're totally missing the point: it could.
The point is not about CSP-Rules but FOL: in a proof, you can't make a difference between the proven statement (r1c1=n1) and the axiom (r1c1=n1) .

[eleven]

In my world only the sudoku rules are axioms, not a given sudoku.

[denis_berthier]

In my world only the sudoku rules are axioms, not a given sudoku.

There are the general Sudoku axioms and there are the specific instance axioms.
When you solve a particular puzzle, the givens become axioms of this puzzle. (This was already explained in [HLS 2007].)

[eleven]

Yes, in your world. As you can see, your world is missing nice solution techniques.

[denis_berthier]

Yes, in your world. As you can see, your world is missing nice solution techniques.

Again, you're beside the point.
What "my world" allows, that yours doesn't, is to make a difference between a pure logic technique and extra-logical ones.

All this was already summarised in the first post here: http://forum.enjoysudoku.com/post287631.html#p287631. So, I don't see any point in continuing this discussion.
.

[denis_berthier]

Here's a nice GDP-7:

Code: Select all

    12  24  |  14
    13  .   |  12
    --------+----
    23  12  |  .

Exercise for the reader:
1) Read this post: http://forum.enjoysudoku.com/ur1-1-again-t37404-152.html
2) Find an extension of the above pattern that must be at the start of any resolution path where it appears.
.

[denis_berthier]

.
Answer:

Code: Select all

    12  124 |  124
    123 .   |  12
    --------+----
    123 12  |  .

As you can see, this covers the two ordinary UR1s mentioned in previous posts.

Consequence: in terms of resolution power, the "nice pattern" doesn't bring anything.

Challenge: find a GDP which is not a DP (in the sense of Sudopedia) and which is not an extension of DPs.
Prize: one piece of the Eiffel Tower.
.

[marek stefanik]

Answer:

Code: Select all

    12  124 |  124
    123 .   |  12
    --------+----
    123 12  |  .

The reason they're called GDPs is that this is not a DP. See this puzzle (b124):
.657.....9...83...8.7.5.4..5..94.86..7.6.........18....4..6.5.....3....1..3....2.

Marek

[denis_berthier]

.
It isn't a DP, as I said, BUT it contains 2 DPs.

Code: Select all

   +----------------------+----------------------+----------------------+
   ! 1234   6      5      ! 7      29     1249   ! 1239   1389   2389   !
   ! 9      12     124    ! 124    8      3      ! 1267   157    2567   !
   ! 8      123    7      ! 12     5      1269   ! 4      139    2369   !
   +----------------------+----------------------+----------------------+
   ! 5      123    12     ! 9      4      27     ! 8      6      237    !
   ! 1234   7      12489  ! 6      23     25     ! 1239   13459  23459  !
   ! 2346   239    2469   ! 25     1      8      ! 2379   34579  234579 !
   +----------------------+----------------------+----------------------+
   ! 127    4      1289   ! 128    6      1279   ! 5      3789   3789   !
   ! 267    2589   2689   ! 3      279    24579  ! 679    4789   1      !
   ! 167    1589   3      ! 1458   79     14579  ! 679    2      46789  !
   +----------------------+----------------------+----------------------+

DP4-2-1s-OR2-relation for digits: 12
   in cells (marked #): (r4c3 r4c2 r2c3 r2c2)
   with 2 guardians (in cells marked @) : n3r4c2 n4r2c3

DP4-2-1s-OR3-relation for digits: 12
   in cells (marked #): (r7c6 r7c4 r3c6 r3c4)
   with 3 guardians (in cells marked @) : n9r7c6 n8r7c4 n6r3c6 

DP4-2-1s-OR3-relation for digits: 12
   in cells (marked #): (r7c6 r7c4 r3c6 r3c4)
   with 5 guardians (in cells marked @) : n7r7c6 n9r7c6 n8r7c4 n6r3c6 n9r3c6

And from these 2 DPs, you get anything (and likely more) than you could obtain with the GDP.
.

[nazaz]

Code: Select all

    12  124 |  124
    123 .   |  12
    --------+----
    123 12  |  .

All you've illustrated here is that those seven cells must contain at least the indicated candidates immediately after placement of the givens. They could easily contain even more candidates as well. The extra candidates are the price you pay for trying to make a DP-like elimination too early in the solving path: they contribute to OR relations that are awkward to work with.

For example, consider this situation:

Code: Select all

.  .   .   |  .
.  12  24  |  149
.  13  .   |  12
-----------+----
.  23  12  |  .

The GDP-7 asserts 9@r2c4 directly. However if we had tried to deal with that 9 at the start of the solving path then we'd have been faced with the following or worse:

Code: Select all

.  .   .   |  .
.  12  124 |  1249
.  123 .   |  12
-----------+-----
.  123 12  |  .

In this case, the DP to which 9@r2c4 is attached does not assert it directly. Instead, it asserts 9@r2c4 OR 4@r2c4 OR 3@r3c2, which is a strictly weaker deduction.

The best things come to those who wait. If I have the choice, I'd rather use the later GDP-7 than the earlier pair of DPs-plus-extras.

[denis_berthier]

.
Yes, I can believe you. I'm sure you prefer thousands of combinations of DPs to a few elementary minimal ones.
.

[nazaz]

From a while back, when discussing the GDP-5 example:

Would be nice to see a real world example.

I'll caveat this by reminding readers that usefulness for real-world solvers is not my priority. Also, I'm less sure than I'd like to be that my mods to PGExplainer have done the right thing.

That said, this might be what you're looking for:

Code: Select all

 7    2    8  |  5    9    1  |  6   34   34   
 4    9    5  |  7    3    6  |  8    1=   2=
 6    1    3= |  8    2    4= |  5=  79   79   
--------------+---------------+-------------
39    8   79  | 34    6    2  | 47    5    1 
 5   37    1  | 49    8   39  | 47    2=   6=
 2    4=   6  |  1    7=   5= | 39   39    8=
--------------+---------------+-------------
39    6   47  |  2=   1    8= | 39   47    5 
 8    5=   2  | 39*   4    7* |  1=   6   39* 
 1=  37  479  |  6=   5   39* |  2    8   47*

The "=" cells are the givens. The pencilmarks are the state after a few moves (not sure which moves; maybe later I can get PGExplainer to write out a log). The "*" cells in the last two rows are those implicated in the GDP-5, which asserts the guardian 4@r9c9 directly.

[marek stefanik]

I'm sure you prefer thousands of combinations of DPs to a few elementary minimal ones.

More complex DPs can sometimes significantly simplify certain eliminations.
Consider this puzzle:
.657.....9...83...8.7.564..5...4.86..7............1.9..4....5.....37...1..3....2.
Suppose you manage to eliminate 1r2c3, 2r2c4, 2r3c2, and 1r4c2.

This is the RS after subsets:

Code: Select all

,------------------,-------------------,---------------,
| 134   6     5    | 7     129   249   | 23   18   289 |
| 9    *12   *24   |*14    8     3     | 67   57   56  |
| 8    *13    7    |*2+9   5     6     | 4    13   29  |
:------------------+-------------------+---------------:
| 5    *23+9  1    | 2–9   4     7     | 8    6    23  |
| 236   7     269  | 68    2369  289   | 1    45   45  |
| 2346  28    2468 | 5     236   1     | 23   9    7   |
:------------------+-------------------+---------------:
| 1267  4     2689 | 168   1269  289   | 5    378  368 |
| 26    2589  2689 | 3     7     24589 | 69   48   1   |
| 167   1589  3    | 1468  169   4589  | 679  2    468 |
'------------------'-------------------'---------------'

All guardians of the GDP see 9r4c4, so it can be eliminated.

Using only the minimal DPs, this elimination is not obvious. Even if you set 9r4c4, this is the state after subsets:

Code: Select all

,---------------,------------------,---------------,
| 34    6   5   | 7     19    49   | 23   18   28  |
| 9     12  24  | 14    8     3    | 67   57   56  |
| 8     13  7   | 2     5     6    | 4    13   9   |
:---------------+------------------+---------------:
| 5     23  1   | 9     4     7    | 8    6    23  |
| 236   7   9   | 68    236   28   | 1    45   45  |
| 2346  8   246 | 5     236   1    | 23   9    7   |
:---------------+------------------+---------------:
| 17    4   268 | 168   1269  289  | 5    378  368 |
| 26    59  268 | 3     7     2458 | 69   48   1   |
| 17    59  3   | 1468  16    458  | 679  2    468 |
'---------------'------------------'---------------'

I think you still need an OR2-whip[2], or whatever you'd call it, to reach a contradiction.

If a bivalue GDP can make the difference between OR2-whip[1] (or whatever) and T&E(2), it is probably worth it.
And I can't even imagine what one would have to do in order to prove this pattern deadly with just minimal DPs:

Code: Select all

13  | .  123 . | 123
123 | .  .   . | 12
123 | .  23  . | .

TLDR: Using a single compound DP can lead to a way more elegant solution path than using thousands of elementary minimal ones.

Marek

[nazaz]

TLDR: Using a single compound DP can lead to a way more elegant solution path than using thousands of elementary minimal ones.

True! And a very nice example, thank you.

Of course, there's a tradeoff to be had here. Do you restrict yourself to a satisfyingly-short catalogue Sudopedia-style DPs and add branching logic to fit the problem at hand, or do you use a larger catalogue of GDPs to enact elegant eliminations in a slightly magical way? Either would be a reasonable position to take, and now that we've heard both sides I don't think it would be profitable to argue the "beauty" question any further.

Moving on ... here's a recap of where we've got to with GDPs and their depletions:

• They appear to include everything that people recognise as "deadly", e.g. Sudopedia's narrow formally-defined DPs, UR1.1, MUGs and dobrichev's 7-cell patterns.
• There's a lot of them ... which perhaps you love, perhaps you hate. A matter of personal taste.
• The "new" GDPs are not all just theoretical. Examples can be found within natural-looking solution paths.
• Some GDPs fall into easily-described families, like the UR-related GDP5+ "zoo" described earlier.

A lot more could probably be said about the internal connecting logic that holds a GDP's constituent UAs together.

[denis_berthier]

More complex DPs can sometimes significantly simplify certain eliminations.
Consider this puzzle:
.657.....9...83...8.7.564..5...4.86..7............1.9..4....5.....37...1..3....2.

Suppose you manage to eliminate 1r2c3, 2r2c4, 2r3c2, and 1r4c2.

I've a much better idea: suppose the puzzle is solved.

As for a solution, there's a simple one based on 2 UR1s:
(Note that accepting uniqueness for this puzzle doesn't lead to much simplification: only -1 in max-length of chains.)

Code: Select all

Resolution state after Singles:
   +----------------------+----------------------+----------------------+
   ! 1234   6      5      ! 7      129    249    ! 1239   138    2389   !
   ! 9      12     124    ! 124    8      3      ! 1267   157    2567   !
   ! 8      123    7      ! 129    5      6      ! 4      13     239    !
   +----------------------+----------------------+----------------------+
   ! 5      1239   129    ! 29     4      7      ! 8      6      23     !
   ! 12346  7      124689 ! 25689  2369   2589   ! 123    1345   2345   !
   ! 2346   238    2468   ! 2568   236    1      ! 237    9      23457  !
   +----------------------+----------------------+----------------------+
   ! 1267   4      12689  ! 12689  1269   289    ! 5      378    36789  !
   ! 26     2589   2689   ! 3      7      24589  ! 69     48     1      !
   ! 167    1589   3      ! 145689 169    4589   ! 679    2      46789  !
   +----------------------+----------------------+----------------------+
199 candidates, 1189 csp-links and 1189 links. Density = 6.04%

Code: Select all

DP4-2-1s-OR4-relation for digits: 12
   in cells (marked #): (r4c3 r4c2 r2c3 r2c2)
   with 4 guardians (in cells marked @) : n9r4c3 n3r4c2 n9r4c2 n4r2c3 
   +----------------------+----------------------+----------------------+
   ! 1234   6      5      ! 7      129    249    ! 1239   138    2389   !
   ! 9      12#    124#@  ! 124    8      3      ! 1267   157    2567   !
   ! 8      123    7      ! 129    5      6      ! 4      13     239    !
   +----------------------+----------------------+----------------------+
   ! 5      1239#@ 129#@  ! 29     4      7      ! 8      6      23     !
   ! 12346  7      124689 ! 25689  2369   2589   ! 123    1345   2345   !
   ! 2346   238    2468   ! 2568   236    1      ! 237    9      23457  !
   +----------------------+----------------------+----------------------+
   ! 1267   4      12689  ! 12689  1269   289    ! 5      378    36789  !
   ! 26     2589   2689   ! 3      7      24589  ! 69     48     1      !
   ! 167    1589   3      ! 145689 169    4589   ! 679    2      46789  !
   +----------------------+----------------------+----------------------+


DP4-2-1-OR3-relation for digits: 12
   in cells (marked #): (r3c4 r3c2 r2c4 r2c2)
   with 3 guardians (in cells marked @) : n9r3c4 n3r3c2 n4r2c4 
   +----------------------+----------------------+----------------------+
   ! 1234   6      5      ! 7      129    249    ! 1239   138    2389   !
   ! 9      12#    124    ! 124#@  8      3      ! 1267   157    2567   !
   ! 8      123#@  7      ! 129#@  5      6      ! 4      13     239    !
   +----------------------+----------------------+----------------------+
   ! 5      1239   129    ! 29     4      7      ! 8      6      23     !
   ! 12346  7      124689 ! 25689  2369   2589   ! 123    1345   2345   !
   ! 2346   238    2468   ! 2568   236    1      ! 237    9      23457  !
   +----------------------+----------------------+----------------------+
   ! 1267   4      12689  ! 12689  1269   289    ! 5      378    36789  !
   ! 26     2589   2689   ! 3      7      24589  ! 69     48     1      !
   ! 167    1589   3      ! 145689 169    4589   ! 679    2      46789  !
   +----------------------+----------------------+----------------------+

whip[1]: r4n1{c3 .} ==> r5c3≠1, r5c1≠1
finned-x-wing-in-rows: n3{r4 r3}{c2 c9} ==> r1c9≠3
naked-triplets-in-a-row: r2{c2 c3 c4}{n2 n1 n4} ==> r2c9≠2, r2c8≠1, r2c7≠2, r2c7≠1
naked-triplets-in-a-column: c7{r2 r8 r9}{n7 n6 n9} ==> r6c7≠7, r1c7≠9
singles ==> r6c9=7, r6c4=5
whip[1]: r6n8{c3 .} ==> r5c3≠8
whip[1]: r6n4{c3 .} ==> r5c1≠4, r5c3≠4
whip[1]: c7n9{r9 .} ==> r7c9≠9, r9c9≠9
naked-pairs-in-a-block: b6{r4c9 r6c7}{n2 n3} ==> r5c9≠3, r5c9≠2, r5c8≠3, r5c7≠3, r5c7≠2
naked-single ==> r5c7=1
finned-x-wing-in-columns: n3{c7 c1}{r1 r6} ==> r6c2≠3
swordfish-in-rows: n3{r3 r4 r7}{c8 c2 c9} ==> r1c8≠3
biv-chain[3]: r4c9{n3 n2} - r4c4{n2 n9} - r3n9{c4 c9} ==> r3c9≠3
biv-chain[3]: r6c7{n2 n3} - r1n3{c7 c1} - c1n4{r1 r6} ==> r6c1≠2
z-chain[3]: r9n7{c1 c7} - c7n9{r9 r8} - r8n6{c7 .} ==> r9c1≠6
DP4-2-1-OR3-whip[3]: r3c9{n2 n9} - OR3{{n9r3c4 n3r3c2 | n4r2c4}} - r2n2{c4 .} ==> r3c2≠2
naked-pairs-in-a-row: r3{c2 c8}{n1 n3} ==> r3c4≠1
naked-pairs-in-a-column: c4{r3 r4}{n2 n9} ==> r9c4≠9, r7c4≠9, r7c4≠2, r5c4≠9, r5c4≠2, r2c4≠2
whip[1]: r2n2{c3 .} ==> r1c1≠2
biv-chain[3]: r6c2{n8 n2} - b1n2{r2c2 r2c3} - c3n4{r2 r6} ==> r6c3≠8
hidden-single-in-a-block ==> r6c2=8
DP4-2-1s-OR4-whip[3]: b1n2{r2c2 r2c3} - OR4{{n4r2c3 n3r4c2 n9r4c2 | n9r4c3}} - r4n1{c3 .} ==> r4c2≠2
biv-chain[4]: r1n3{c1 c7} - c8n3{r3 r7} - b9n7{r7c8 r9c7} - r9c1{n7 n1} ==> r1c1≠1
whip[1]: c1n1{r9 .} ==> r7c3≠1, r9c2≠1
hidden-pairs-in-a-block: b7{n1 n7}{r7c1 r9c1} ==> r7c1≠6, r7c1≠2
biv-chain[3]: b8n5{r8c6 r9c6} - r9c2{n5 n9} - c7n9{r9 r8} ==> r8c6≠9
biv-chain[3]: r1n1{c5 c8} - r3c8{n1 n3} - r1c7{n3 n2} ==> r1c5≠2
z-chain[3]: b7n8{r8c3 r7c3} - b7n6{r7c3 r8c1} - r8c7{n6 .} ==> r8c3≠9
DP4-2-1-OR3-whip[3]: r2n1{c3 c4} - OR3{{n4r2c4 n3r3c2 | n9r3c4}} - r1c5{n9 .} ==> r3c2≠1
stte