Supersymmetries and Hidden chains

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Fri Jul 27, 2007 8:10 pm

denis_berthier wrote:column C7 : hxy5-rn-chain on rn-cells R1N3*, R1N9, R4N9, R4N4 and R7N4* with columns C7, C3, C1, C3 and C1
==> C7 eliminated from the rn-candidates for R1N4
i.e. 4 eliminated from the candidates for R1C7
Code: Select all
.8.2.1...14.385.92.2.9.4.18.3.758261261493.8.8..612934.98137.2....8291.3312546879

rc-spc|  c1   c2    c3    | c4    c5    c6    | c7     c8    c9
------+-------------------+-------------------+-------------------
r1    | B5679 8    A35679 | 2     67    1     | 3567-4 45    567
r2    |  1    4     67    | 3     8     5     | 67     9     2
r3    |  567  2     3567  | 9     67    4     | 3567   1     8
------+-------------------+-------------------+-------------------
r4    |CE49   3    D49    | 7     5     8     | 2      6     1
r5    |  2    6     1     | 4     9     3     | 57     8     57
r6    |  8    57    57    | 6     1     2     | 9      3     4
------+-------------------+-------------------+-------------------
r7    | F456  9     8     | 1     3     7     |G456    2     56
r8    |  4567 57    4567  | 8     2     9     | 1      45    3
r9    |  3    1     2     | 5     4     6     | 8      7     9


rn-spc| n1    n2    n3    | n4    n5    n6    | n7    n8    n9
------+-------------------+-------------------+---------------
r1    | 6     4    a37    | 8-7   13789 13579 | 13579 2    b13
r2    | 1     9     4     | 2     6     37    | 37    5     8
r3    | 8     2     37    | 6     137   1357  | 1357  9     4
------+-------------------+-------------------+-------------------
r4    | 9     7     2     |d13    5     8     | 4     6    c13
r5    | 3     1     6     | 4     79    2     | 79    8     5
r6    | 5     6     8     | 9     23    4     | 23    1     7
------+-------------------+-------------------+-------------------
r7    | 4     8     5     |e17    179   179   | 6     3     2
r8    | 7     5     9     | 138   1238  13    | 123   4     6
r9    | 2     3     1     | 5     4     6     | 8     7     9

         a      b      c      d      e
r1n4-7-r1n3-3-r1n9-1-r4n9-3-r4n4-1-r7n4-7-r1n4, implies r1n4<>c7 i.e. r1c7<>4

It should be no surprise that bivalues in rn-space are bilocation values in standard rc-space. Using all the cells in the hxy5 chain, but in rc-space ...
Code: Select all
         A      B    C(E)     D    E(C)     F      G
r1c7=3=r1c4=9=r1c1-9-r4c1=9=r4c3=4=r4c1-4-r7c1=4=r7c7-4-r1c7, implies r1c7<>4

That r4c1 appears twice is a bit weird, but it's logically correct, and it means the deduction does not depend on the bivalues in r4c1 and r4c3.

Hmm, I wonder how many solvers would not find this (if r4c1 and r4c3 were not bivalues) because overlaps are not allowed.

[edit: formatted rn-pencilmarks]
Last edited by ronk on Sat Jul 28, 2007 6:45 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby re'born » Fri Jul 27, 2007 9:22 pm

denis_berthier wrote:
re'born wrote:
denis_berthier wrote:.8.2.1…
14.385.92
.2.9.4.18
.3.758261
261493.8.
8..612934
.98137.2.
…8291.3
312546879

In this puzzle, you've inadvertantly replaced "."'s with ellipses in row 1 and row 8. This makes it rather troublesome to copy into solvers.

re'born, thanks for signaling it. In my navigator, I don't see that. Have you corrected it in the above?


I didn't correct it. It has happened to me before, usually if my text editor has a built in auto-correct, since these usually turn 3 consecutive periods into ellipses. This explanation at least fits the facts (modulo me not knowing what text editor you used to originally write down the grid).
re'born
 
Posts: 551
Joined: 31 May 2007

Postby re'born » Fri Jul 27, 2007 9:46 pm

Inspired by ronk's analysis, I took a peek at the rn-space and found a very pretty almost xy-ring (would this translate in the rc-space to an halmost xy-ring?:) )

Code: Select all
rn-spc| n1    n2    n3    | n4    n5    n6    | n7    n8    n9
------+-------------------+-------------------+---------------
r1    | 6     4     37    | 78  13789  1579-3 |1579-3 2     13
r2    | 1     9     4     | 2     6     37b   | 37a   5     8
r3    | 8     2     37    | 6     137   157-3 | 157-3 9     4
r4    | 9     7     2     | 13    5     8     | 4     6     13
r5    | 3     1     6     | 4     79    2     | 79    8     5
r6    | 5     6     8     | 9     23    4     | 23e   1     7
r7    | 4     8     5     | 17    179   179   | 6     3     2
r8    | 7     5     9     | 38-1  238-1 13c   |12(3)d 4     6
r9    | 2     3     1     | 5     4     6     | 8     7     9


The almost xy-ring (labelled a-e above) eliminates from rn-space r13n67<>3, r8n45<>1, which in rc-space corresponds to
r13c3<>6,7 and r8c1<>4,5. This doesn't even come close to solving the puzzle, but it was the first xy-ring (or almost xy-ring) I've seen in rn-space.

Question: What sort of pattern makes these exclusions in rc-space?

[Edit: Changed xy-cycle to xy-ring (thanks ronk for pointing that out)]
[Edit2: Fixed my notation (thanks Denis, old habits will die hard)]
Last edited by re'born on Sat Jul 28, 2007 3:17 am, edited 1 time in total.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Sat Jul 28, 2007 3:48 am

re'born wrote:The almost xy-ring (labelled a-e above) eliminates from rn-space r13c67<>3, r8c45<>1

Of course, you mean: r13n67<>3, r8n45<>1

re'born wrote:Question: What sort of pattern makes these exclusions in rc-space?

The advantage of rn- and cn- spaces is that they make some complex patterns of rc-space appear as simple ones in rn-space.

Ronk's analysis of my example in a previous post is interesting: the simple hxy-chain on 5 rn-cells:
hxy5-rn-chain on rn-cells R1N3*, R1N9, R4N9, R4N4 and R7N4* with columns C7, C3, C1, C3 and C1
appears in rc-space as a discontinuous AIC on 7 cells (not counting the target R1C7)
r1c7=3=r1c4=9=r1c1-9-r4c1=9=r4c3=4=r4c1-4-r7c1=4=r7c7-4-r1c7

As you notice, "that r4c1 appears twice is a bit weird, but it's logically correct" and I think few people will find it because such internal loops are generally not looked for.

All hxy-chains are AICs (simply because a bivalue in rn- or cn- space corresponds to a bilocation in rc-space), but they often look much simpler (and are thus much simpler to find).
Notice that, conversely, not all AICs will appear as hxy-chains.

Nevertheless, for more complex chains in rn- or cn- space, there may be no known corresponding pattern in rc-space. This is in general the case for hxyt and hxyzt- chains.
In the case of your ring, I have no answer.

When I discovered rn- and cn- spaces, I initially did the same as you: I wondered what these patterns correspond to in "normal" space. Now, I know the answer is generally complex and I just take them as they are. Their have the same right to independent existence as any pattern in rc-space.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Sat Jul 28, 2007 10:58 am

denis_berthier wrote:r1c7=3=r1c4=9=r1c1-9-r4c1=9=r4c3=4=r4c1-4-r7c1=4=r7c7-4-r1c7

As you notice, "that r4c1 appears twice is a bit weird, but it's logically correct" and I think few people will find it because such internal loops are generally not looked for.

As stated earlier, that nice loop was forced to use all the cells of the hxy5 chain which means it was contrived. As there is no need to look for an "internal loop", it is not what someone would normally find. The bivalue/bilocation plot solver would most likely instead find ...

r1c7=3=r1c4=9=r1c1-9-r4c1-4-r7c1=4=r7c7-4-r1c7

... which, like the hxy5 chain, uses five cells.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby re'born » Sat Jul 28, 2007 5:11 pm

ronk wrote:
denis_berthier wrote:r1c7=3=r1c4=9=r1c1-9-r4c1=9=r4c3=4=r4c1-4-r7c1=4=r7c7-4-r1c7

As you notice, "that r4c1 appears twice is a bit weird, but it's logically correct" and I think few people will find it because such internal loops are generally not looked for.

As stated earlier, that nice loop was forced to use all the cells of the hxy5 chain which means it was contrived. As there is no need to look for an "internal loop", it is not what someone would normally find. The bivalue/bilocation plot solver would most likely instead find ...

r1c7=3=r1c4=9=r1c1-9-r4c1-4-r7c1=4=r7c7-4-r1c7

... which, like the hxy5 chain, uses five cells.


I haven't checked it, but I think the above loop will correspond to an hxy-chain in cn-space. In my limited experience, I have seen that if an hxy-chain in rn-space (resp. cn-space) corresponds to a chain with internal loops in rc-space, then there is a corresponding chain in cn-space (resp. rn-space) that makes the same exclusions but doesn't have the internal loop.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby denis_berthier » Sun Jul 29, 2007 8:37 am

Raining cats and dogs outside ==> time (and weather) for more complex examples.

Consider the following (very hard) puzzle:
600700400
904060000
758000600
491000208
800009314
200841960
340007000
107980543
589000726

After a few elementary eliminations:
Code: Select all
row R4 interaction with block B5
                              ==> 6 eliminated from the candidates for R5C4
row R9 interaction with block B8
                              ==> 1 eliminated from the candidates for R7C5
                              ==> 1 eliminated from the candidates for R7C4
xy-wing on cells R5C3*, R7C3 and R7C5* with numbers 5, 6 and 2
                              ==> 5 eliminated from the candidates for R5C5
xy-wing on cells R5C4*, R5C3 and R7C3* with numbers 2, 5 and 6
                              ==> 2 eliminated from the candidates for R7C4

you need a succession of moderately complex chains of various types (xy, hxy, hxyt, hyyzt, c), illustrating how you can juggle with rc- and rn- spaces;
(for the definitions of xyt and xyzt, see the other thread;
c-chains are the simplest AICs
a * on a cell indicates that any target cell of the chain must be connected to it, in the space of this chain: rc, rn or cn);
these steps are a good way to get used with all these chains:

Code: Select all
hxy4-rn-chain on rn-cells R5N5*, R5N6, R8N6 and R4N6* with columns C4, C3, C2 and C6
                              ==> C4 eliminated from the rn-candidates for R4N5
                                  i.e. 5 eliminated from the candidates for R4C4
c4-chain row-bl-col on cells R8C6-R8C2-R7C3-R1C3
                              ==> 2 eliminated from the candidates for R1C6
xy5-chain on cells R5C5*, R5C2, R5C3, R6C3 and R1C3* with numbers 2, 7, 6, 5 and 3
                              ==> 2 eliminated from the candidates for R1C5
xyt5-chain on cells R7C5*, R7C4, R4C4, R4C5 and R5C5* with numbers 2, 5, 6, 3 and 7
                              ==> 2 eliminated from the candidates for R3C5
hxyzt5-rn-chain-type-3 on rn-cells R3N4*, R9N4, R9N1, R3N1* and R3N2* with columns C4, C6, C4, C5 and C9
                              ==> C4 eliminated from the rn-candidates for R3N3
                                  i.e. 3 eliminated from the candidates for R3C4
xy6-chain on cells R5C4*, R5C5, R5C2, R8C2, R8C6 and R7C4* with numbers 5, 2, 7, 6, 2 and 6
                              ==> 5 eliminated from the candidates for R2C4
xyzt7-chain-type-1 on cells R1C3*, R1C2*, R2C2, R6C2, R6C9, R1C9 and R3C8* with numbers 3, 2, 1, 3, 7, 5 and 9
                              ==> 3 eliminated from the candidates for R1C8

then comes a monster hxyt-rn-chain of length 10, which makes two decisive eliminations:
Code: Select all
hxyt10-rn-chain on rn-cells R2N7*, R6N7, R5N7, R5N2, R5N5, R5N6, R8N6, R8N2, R2N2 and R2N5* with columns C8, C9, C2, C5, C4, C3, C2, C6, C2 and C6
                              ==> C8 eliminated from the rn-candidates for R2N8
                                  i.e. 8 eliminated from the candidates for R2C8
                              ==> C8 eliminated from the rn-candidates for R2N3
                                  i.e. 3 eliminated from the candidates for R2C8

If you have reached this point, you'll easily find how to finsih.

Of course, such a exceptionally long chain is hard to find. But this is an extreme example. Usually, chains will be much shorter.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby daj95376 » Sun Jul 29, 2007 4:21 pm

denis_berthier wrote:Raining cats and dogs outside ==> time (and weather) for more complex examples.

Consider the following (very hard) puzzle:
600700400
904060000
758000600
491000208
800009314
200841960
340007000
107980543
589000726

After a few elementary eliminations:

Set any one of 14 bi-value cells to the wrong value:

Code: Select all
[r1c3]=3,[r4c8]=5,[r5c2]=7,[r5c3]=6,[r5c4]=5,[r5c5]=2,[r6c2]=3,
[r6c3]=5,[r6c9]=7,[r7c3]=2,[r7c4]=6,[r7c5]=5,[r8c2]=6,[r8c6]=2

=> 16 Naked Singles, [r2c8]=h7, [r2c6]=h3 => [c6]=Invalid

After choosing a correct value in one of these cells, Singles complete the puzzle.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby denis_berthier » Sun Jul 29, 2007 4:35 pm

daj95376 wrote:600700400
904060000
758000600
491000208
800009314
200841960
340007000
107980543
589000726

Set any one of 14 bi-value cells to the wrong value:

Code: Select all
[r1c3]=3,[r4c8]=5,[r5c2]=7,[r5c3]=6,[r5c4]=5,[r5c5]=2,[r6c2]=3,
[r6c3]=5,[r6c9]=7,[r7c3]=2,[r7c4]=6,[r7c5]=5,[r8c2]=6,[r8c6]=2

=> 16 Naked Singles, [r2c8]=h7, [r2c6]=h3 => [c6]=Invalid

After choosing a correct value in one of these cells, Singles complete the puzzle.

Trial and Error is generally not accepted as a valid method.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby daj95376 » Sun Jul 29, 2007 4:54 pm

Yes, I can see where your solution is easier and more intuitive!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby re'born » Fri Aug 24, 2007 10:02 am

Here is a nice example I recently found of an hxy-ring:
Code: Select all
4 3 .|. 1 .|. . 9
. . 1|. . .|. . .
. . .|4 . .|7 3 1
-----+-----+-----
. 6 .|5 7 1|3 9 4
1 5 9|3 . 4|2 . 7
7 4 3|2 . .|1 5 .
-----+-----+-----
3 2 6|7 4 8|9 1 5
5 . .|. . .|8 . .
9 . .|. 5 2|. 7 3

After removing a couple of locked candidates, we get
Code: Select all
.------------------.------------------.------------------.
| 4     3     257  | 68    1     567  | 56    268   9    |
| 26    79    1    | 689   2369  35679| 456   2468  268  |
| 268   89    258  | 4     269   569  | 7     3     1    |
:------------------+------------------+------------------:
| 28    6     28   | 5     7     1    | 3     9     4    |
| 1     5     9    | 3     68    4    | 2     68    7    |
| 7     4     3    | 2     689   69   | 1     5     68   |
:------------------+------------------+------------------:
| 3     2     6    | 7     4     8    | 9     1     5    |
| 5     17    47   | 169   369   369  | 8     246   26   |
| 9     18    48   | 16    5     2    | 46    7     3    |
'------------------'------------------'------------------'

Switching to RN-space, we get
Code: Select all
    n1      n2      n3      n4      n5      n6      n7      n8      n9
-----------------------------------------------------------------------
r1| 5       38      2       1       367     4678    36      48      9
r2| 3       1589    56-     78*     67*     1456789-26*     489     2456-
r3| 9       135     8       4       36      156     7       123     256
r4| 6       13      7       9       4       2       5       13      8
r5| 1       7       4       6       2       58      9       58      3
r6| 7       4       3       2       8       569     1       59      56
r7| 8       2       1       5       9       3       4       6       7
r8| 24      89      56      38*     1       45689   23*     7       456
r9| 24      6       9       37      5       47      8       23      1

an xy-ring that implies r2n369<>6 and r2n6<>7. This translates in the original grid to r2c6<>369 and r2c7<>6. After some cleaning up, the puzzle is reduced to
Code: Select all
.---------------.---------------.---------------.
| 4    3    257 | 68   1    567 | 56   268  9   |
| 26   79   1   | 689  3    57  | 45   2468 268 |
| 68   89   58  | 4    2    569 | 7    3    1   |
:---------------+---------------+---------------:
| 28   6    28  | 5    7    1   | 3    9    4   |
| 1    5    9   | 3    68   4   | 2    68   7   |
| 7    4    3   | 2    689  69  | 1    5    68  |
:---------------+---------------+---------------:
| 3    2    6   | 7    4    8   | 9    1    5   |
| 5    17   47  | 169  69   3   | 8    246  26  |
| 9    18   48  | 16   5    2   | 46   7    3   |
'---------------'---------------'---------------'

where the short chain
[r8c4]-1-[r8c2]-7-[r2c2]-9-[r2c4]=9=[r8c4], =>r8c4<>1, solves the puzzle.

Edit: Alternatively, if one looks at CN-space from the start, there is an xy-chain
-2-[c2n7]-8-[c2n1]-9-[c4n1]-8-[c4n9]-2-, =>c2n9<>2 =>r2c2<>9, solving the puzzle.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby ronk » Fri Aug 24, 2007 3:22 pm

re'born wrote:Switching to RN-space, we get
Code: Select all
    n1      n2      n3      n4      n5      n6      n7      n8      n9
-----------------------------------------------------------------------
r1| 5       38      2       1       367     4678    36      48      9
r2| 3       1589    56-     78*     67*     1456789-26*     489     2456-
r3| 9       135     8       4       36      156     7       123     256
r4| 6       13      7       9       4       2       5       13      8
r5| 1       7       4       6       2       58      9       58      3
r6| 7       4       3       2       8       569     1       59      56
r7| 8       2       1       5       9       3       4       6       7
r8| 24      89      56      38*     1       45689   23*     7       456
r9| 24      6       9       37      5       47      8       23      1

an xy-ring that implies r2n369<>6 and r2n6<>7. This translates in the original grid to r2c6<>369 and r2c7<>6.

That hxy5 continuous loop uses the strong inferences of five bivalues. While the identical deduction in RC-space uses seven cells -- instead of five "hidden cells" -- it should be no surprise that it also uses five strong inferences.
Code: Select all
 4     3     257  | 68    1     567   | 56    268   9   
 26   *79    1    | 689   2369 *57-369|*45-6 *2468  268
 268   89    258  | 4     269   569   | 7     3     1   
------------------+-------------------+-----------------
 28    6     28   | 5     7     1     | 3     9     4   
 1     5     9    | 3     68    4     | 2     68    7   
 7     4     3    | 2     689   69    | 1     5     68 
------------------+-------------------+-----------------
 3     2     6    | 7     4     8     | 9     1     5   
 5    *17   *47   | 169   369   369   | 8    *246   26 
 9     18    48   | 16    5     2     | 46    7     3   

r2c2 =7= r2c6 =5= r2c7 =4= r2c8 -4- r8c8 =4= r8c3 =7= r8c2 -7- loop, implies r2c6<>369, r2c7<>6
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Automatic display of the rn- and cn- representations

Postby denis_berthier » Sat Aug 25, 2007 6:54 am

Several persons asked for a program that could display automatically the rn- and cn- representations. Ruud has announced in the UK forum that they are now integrated into his last release of Sudocue.
I hope this will help those of you who want to try them.

Beware, I never said they are a panacea. But they can make some puzzles easier to solve.
Remember that what you can do in these representations is simple: anything that you do in the other representations and that does not use the notion of a block, e.g.
- subsets (hidden subsets and fishy patterns will appear as mere naked subsets),
- xy-, xyt- and xyzt chains.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Automatic display of the rn- and cn- representations

Postby re'born » Sat Aug 25, 2007 9:37 am

denis_berthier wrote:Beware, I never said they are a panacea. But they can make some puzzles easier to solve.
Remember that what you can do in these representations is simple: anything that you do in the other representations and that does not use the notion of a block, e.g.
- subsets (hidden subsets and fishy patterns will appear as mere naked subsets),
- xy-, xyt- and xyzt chains.

If you're careful, even some techniques that use blocks can be used. For instance, sashimi and finned fish and even some of the uniqueness techniques can be spotted with corresponding moves in RN or CN space.
re'born
 
Posts: 551
Joined: 31 May 2007

Re: Automatic display of the rn- and cn- representations

Postby denis_berthier » Sat Aug 25, 2007 12:12 pm

re'born wrote:If you're careful, even some techniques that use blocks can be used.

If you are careful, yes. But not for first users.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Previous

Return to Advanced solving techniques