Is there a simple alternative for this template discovery?

Advanced methods and approaches for solving Sudoku puzzles

Re: Another puzzle

Postby Myth Jellies » Wed Feb 22, 2006 7:09 pm

Ruud wrote:This is the moment it requires the template check. It eliminates candidate 7 in R5C7. What alternatives can I use to eliminate this candidate?

Code: Select all
.---------------.---------------.---------------.
| 57   49  *457 | 2    69   34  | 8    1   *3467|
| 6    1248 14  | 7    5    348 | 9    24   34  |
| 278  2489 3   | 69   1    48  | 247  2467 5   |
:---------------+---------------+---------------:
| 3    48   2   | 69   789  5   | 1    678 #478 |
| 178  5   *147 | 3    2678 127 |-47-  9   *678 |
| 178  6    9   | 4    78   17  | 5    3    2   |
:---------------+---------------+---------------:
| 4    12   15  | 18   3    27  | 6    2578 9   |
| 9    3    8   | 5    247  6   | 247  247  1   |
| 125  7    6   | 18   24   9   | 3    458  48  |
'---------------'---------------'---------------'

A finned x-wing in r15c39, fin in r4c9, kills 7 in r5c7. It won't catch them all, but it does catch a lot of them:)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Re: Another puzzle

Postby Myth Jellies » Wed Feb 22, 2006 9:54 pm

Ruud wrote:This is the moment it requires the forcing chain:

Code: Select all
.------------.------------.------------.
| 57  9   457| 2   6   3  | 8   1   47 |
| 6   12  14 | 7   5   8  | 9   24  3  |
| 27  8   3  | 9   1   4  | 27  6   5  |
:------------+------------+------------:
| 3   4   2  | 6   9   5  | 1   78  78 |
| 178 5   17 | 3   278 127| 4   9   6  |
| 178 6   9  | 4   78  17 | 5   3   2  |
:------------+------------+------------:
| 4   12  15 | 18  3   27 | 6   578 9  |
| 9   3   8  | 5   47  6  | 27  247 1  |
| 125 7   6  | 18  24  9  | 3   458 48 |
'------------'------------'------------'


What simple alternative is available at this stage?


Not sure if you would call it simple, but multi-digit coloring is an alternative.

Let's color the 2's (A & a) and a few 4's (B & b)

Code: Select all
.--------------.--------------.--------------.
| 57   9    457| 2   6    3   | 8   1     47 |
| 6    12a  14 | 7   5    8   | 9   2A4   3  |
| 2A7  8    3  | 9   1    4   | 2a7 6     5  |
:--------------+--------------+--------------:
| 3    4    2  | 6   9    5   | 1   78    78 |
| 178  5    17 | 3   278  127 | 4   9     6  |
| 178  6    9  | 4   78   17  | 5   3     2  |
:--------------+--------------+--------------:
| 4    12A  15 | 18  3    2a7 | 6   578   9  |
| 9    3    8  | 5   4B7  6   | 2A7 2a4b7 1  |
| 12a5 7    6  | 18  2A4b 9   | 3   458   48 |
'--------------'--------------'--------------'


Note that the 4b color is trying to occupy cells that contain both the 2A color and its conjugate color 2a. Since either 2A or 2a must be true, we know that 4b must be false, eliminating the 4's from r8c8 and r9c5 and basically solving the puzzle.

(P.S. - If you think this looks a lot like a POM vulnerable pair reduction, you would also be correct:) . )
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby tarek » Thu Feb 23, 2006 12:32 am

hi Ruud,

You know what, it may be the first time I've seen you on this forum....

I'm not sure that this constitues a simpler alternative....

My solver puts ALS XY chains as simpler than ANY chains

Code: Select all
*--------------------------------------------------------*
| 57    49   *457  | 2     69    34   | 8     1    *3467 |
| 6     1248  14   | 7     5     348  | 9     24    34   |
| 278   2489  3    | 69    1     48   | 247   2467  5    |
|------------------+------------------+------------------|
| 3     48    2    | 69    789   5    | 1     678  %478  |
| 178   5    *147  | 3     2678  127  |-47    9    *678  |
| 178   6     9    | 4     78    17   | 5     3     2    |
|------------------+------------------+------------------|
| 4     12    15   | 18    3     27   | 6     2578  9    |
| 9     3     8    | 5     247   6    | 247   247   1    |
| 125   7     6    | 18    24    9    | 3     458   48   |
*--------------------------------------------------------*
Eliminating 7 From r5c7 (Finned XWing in Columns 39)
*--------------------------------------------------------*
| 57    9     457  | 2     6     3    | 8     1     47   |
| 6     12    14   | 7     5     8    | 9    *24    3    |
| 27    8     3    | 9     1     4    | 27    6     5    |
|------------------+------------------+------------------|
| 3     4     2    | 6     9     5    | 1     78    78   |
| 178   5     17   | 3     278   127  | 4     9     6    |
| 178   6     9    | 4     78    17   | 5     3     2    |
|------------------+------------------+------------------|
| 4     12    15   | 18    3     27   | 6    -2578  9    |
| 9     3     8    | 5     247   6    |*27   *247   1    |
| 125   7     6    | 18    24    9    | 3     458   48   |
*--------------------------------------------------------*
Eliminating 2 From r7c8 (7 & 4 & 2 in r8c8 form an XYZ wing with r8c7 & r2c8)
*-----------------------------------------------*
| 57   9    457 | 2    6    3   | 8    1    47  |
| 6    12   14  | 7    5    8   | 9    24   3   |
| 27   8    3   | 9    1    4   | 27   6    5   |
|---------------+---------------+---------------|
| 3    4    2   | 6    9    5   | 1    78   78  |
| 178  5    17  | 3    278  127 | 4    9    6   |
| 178  6    9   | 4    78   17  | 5    3    2   |
|---------------+---------------+---------------|
| 4    12   15  | 18   3    27  | 6    578  9   |
| 9    3    8   | 5    247  6   | 27   247  1   |
| 125  7    6   | 18   24   9   | 3    458  48  |
*-----------------------------------------------*
Eliminating 2 From r8c5 (Box 9 & Row 8 Box-Line interaction)
*-----------------------------------------------*
|^57   9   -457 | 2    6    3   | 8    1   %47  |
| 6    12   14  | 7    5    8   | 9    24   3   |
|^27   8    3   | 9    1    4   | 27   6    5   |
|---------------+---------------+---------------|
| 3    4    2   | 6    9    5   | 1    78   78  |
| 178  5    17  | 3    278  127 | 4    9    6   |
| 178  6    9   | 4    78   17  | 5    3    2   |
|---------------+---------------+---------------|
| 4    12   15  | 18   3    27  | 6    578  9   |
| 9    3    8   | 5    47   6   | 27   247  1   |
|^125  7    6   |*18   24   9   | 3    458 *48  |
*-----------------------------------------------*
Eliminating 7 from r1c3(ALS-XY  A=148 in r9c9,r9c4   B=1257 in r1c1,r3c1,r9c1   C=47 in r1c9   x=1 y=4 z=7)
*-----------------------------------------------*
| 57   9    45  | 2    6    3   | 8    1    47  |
| 6    12   14  | 7    5    8   | 9    24   3   |
| 27   8    3   | 9    1    4   | 27   6    5   |
|---------------+---------------+---------------|
| 3    4    2   | 6    9    5   | 1    78   78  |
| 18   5    7   | 3    28   12  | 4    9    6   |
| 18   6    9   | 4    78   17  | 5    3    2   |
|---------------+---------------+---------------|
| 4    12   15  | 18   3    27  | 6    578  9   |
| 9    3    8   | 5    47   6   | 27   247  1   |
| 125  7    6   | 18   24   9   | 3    458  48  |
*-----------------------------------------------*
Eliminating 1 From r9c1 (Box 4 & Column 1 Box-Line interaction)
*-----------------------------------------------*
| 57   9   ^45  | 2    6    3   | 8    1    47  |
| 6   ^12  ^14  | 7    5    8   | 9   *24   3   |
| 27   8    3   | 9    1    4   | 27   6    5   |
|---------------+---------------+---------------|
| 3    4    2   | 6    9    5   | 1    78   78  |
| 18   5    7   | 3    28   12  | 4    9    6   |
| 18   6    9   | 4    78   17  | 5    3    2   |
|---------------+---------------+---------------|
| 4    12  -15  | 8    3    27  | 6   %57   9   |
| 9    3    8   | 5    47   6   |%27  %247  1   |
| 25   7    6   | 1    24   9   | 3    458  48  |
*-----------------------------------------------*
Eliminating 5 from r7c3(ALS-XY  A=24 in r2c8   B=1245 in r1c3,r2c2,r2c3   C=2457 in r7c8,r8c7,r8c8   x=2 y=4 z=5)


clearly something that the eye won't catch straight away, except for the finned fish which I'm clearly a fan of:D

Tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Another puzzle

Postby ronk » Thu Feb 23, 2006 3:30 am

Myth Jellies wrote:Note that the 4b color is trying to occupy cells that contain both the 2A color and its conjugate color 2a. Since either 2A or 2a must be true, we know that 4b must be false, eliminating the 4's from r8c8 and r9c5

I wanted to actually see colors, so ...

Image

For 2s either Orange or Pink is true ... and for 4s either Blue or Green is true. Since both Orange (true) and Pink (true) exclude Green (true), Green must represent false. Therefore r8c8<>4 and r9c5<>4.

Programmatically speaking, I suspect this is easier to implement than grouped single-digit multi-coloring.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Another puzzle

Postby Jeff » Thu Feb 23, 2006 7:06 am

Myth Jellies wrote:............. but multi-digit coloring is an alternative.

Note that the 4b color is trying to occupy cells that contain both the 2A color and its conjugate color 2a. Since either 2A or 2a must be true, we know that 4b must be false, eliminating the 4's from r8c8 and r9c5 and basically solving the puzzle.

Hi MJ, I think you are aware that this "multi-digit coloring" has been known as "advanced colouring" or "super colouring" for some time. Nevertheless, I like your name "multi-digit colouring":D because it is more informative and not easy to be confused with "simple colouring" or "multiple colouring" that deals with a single digit.

As a matter of interest, I would like to point out that all deductions produced by multi-digit colouring are double implication chains and are equivalent to discontinuous simple nice loops, three of which as illustrated below.

Nice loop 1 (red): [r2c8]=2=[r2c2]-2-[r3c1]=2=[r9c1]-2-[r9c5]-4-[r8c5]=4=[r8c8]=2=[r2c8], implies r2c8=2
Nice loop 2 (black): [r8c8]-2-[r2c8]=2=[r2c2]-2-[r3c1]=2=[r9c1]-2-[r9c5]-4-[r8c5]=4=[r8c8], implies r8c8<>2
Nice loop 3 (blue): [r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1]=2=[r9c5]=4=[r8c5]-4-[r8c8], implies r8c8<>4

Image

Here are some of the nice loops that can also be identified from the grid:

[r9c5]-4-[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1]=2=[r9c5], implies r9c5<>4
[r9c5]=2=[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1]=2=[r9c5], implies r9c5=2
[r2c8]-4-[r2c2]-2-[r3c1]=2=[r9c1]-2-[r9c5]-4-[r8c5]=4=[r8c8]=2=[r2c8], implies r2c8<>4
[r9c1]-2-[r9c5]-4-[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1], implies r9c1<>2
[r3c1]=2=[[r9c1]-2-[r9c5]-4-[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1], implies r3c1=2

where:
'=x=' represents strong inference meaning if candidate 'x' in the preceding node is false, then candidate 'x' in the following node is true.
'-x-' represents weak inference meaning if candidate 'x' in the preceding node is true, then candidate 'x' in the following node is false.
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: Another puzzle

Postby ronk » Thu Feb 23, 2006 12:16 pm

Jeff wrote:Nice loop 1 (red): [r2c8]=2=[r2c2]-2-[r3c1]=2=[r9c1]-2-[r9c5]-4-[r8c5]=4=[r8c8]=2=[r2c8], implies r2c8=2
Nice loop 2 (black): [r8c8]-2-[r2c8]=2=[r2c2]-2-[r3c1]=2=[r9c1]-2-[r9c5]-4-[r8c5]=4=[r8c8], implies r8c8<>2
Nice loop 3 (blue): [r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1]=2=[r9c5]=4=[r8c5]-4-[r8c8], implies r8c8<>4

......................................

[r9c5]-4-[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1]=2=[r9c5], implies r9c5<>4
[r9c5]=2=[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1]=2=[r9c5], implies r9c5=2
[r2c8]-4-[r2c2]-2-[r3c1]=2=[r9c1]-2-[r9c5]-4-[r8c5]=4=[r8c8]=2=[r2c8], implies r2c8<>4
[r9c1]-2-[r9c5]-4-[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1]-2-[r9c1], implies r9c1<>2
[r3c1]=2=[[r9c1]-2-[r9c5]-4-[r8c5]=4=[[r8c8]-4-[r2c8]-2-[r2c2]=2=[r3c1], implies r3c1=2

And I suppose a deduction for r2c2 could be added to the list too. But I don't understand your point. Why not just make just one of the eliminations or placements (from your nice loops 1,2 or 3) and let naked singles and hidden singles take care of the rest?

And if one already has a picture, why write 10,000 words?

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Another puzzle

Postby Jeff » Thu Feb 23, 2006 12:51 pm

ronk wrote:And I suppose a deduction for r2c2 could be added to the list too. But I don't understand your point. Why not just make just one of the eliminations or placements (from your nice loops 1,2 or 3) and let naked singles and hidden singles take care of the rest?

And if one already has a picture, why write 10,000 words?

Hi Ronk, firstly thanks for the nice grid image. The demonstration is of academic interest to show that the underlying principle of multi-digit colouring and simple nice loop are equivalent, ie. they both involve the same nodes and produce the same deductions.

I realise that any one of the nice loops could be sufficient to solve the puzzle. As difference person looks at the grid could come up with a difference nice loop, my illustration and listing show some of the possibilities for easy reference.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Ruud » Thu Feb 23, 2006 3:39 pm

Myth Jellies wrote:A finned x-wing in r15c39, fin in r4c9, kills 7 in r5c7. It won't catch them all, but it does catch a lot of them.
I have now implemented Finned X-Wing in SudoCue.

Here are the results for the 3000 sudokus that required template checks:
- 64% contains 1 or more Finned X-Wings, many have 2, some have 3.
- 27% is completely solved without any template checks.
- LOTs of them can now be used as Daily Nightmare.:)

tarek wrote:You know what, it may be the first time I've seen you on this forum
Too busy on the other forum. I do read a lot here, especially in this "Advanced solving techniques" forum. Still, my "member since" does outdate yours...

All these "almost" techniques, interesting as they are, can only be used by a handful of players.

MJ, ronk, Jeff,

Thanks for explaining the multi-digit colouring and the nice loops. For now, I will focus on single digits to get rid of the template eliminations.

If have one more. This is the nightmare of last Tuesday. At this point, 3 candidates are eliminated by a template check:

Code: Select all
.------------------.------------------.------------------.
| 23    46    1    | 2789  2689  46789| 4689  3469  5    |
| 23    8     46   | 129   1269  5    | 469   1349  7    |
| 9     5     7    | 18    3     1468 | 2     146   1468 |
:------------------+------------------+------------------:
| 57    123   9    | 4     1568  1368 | 68    2567  268  |
| 6     124   248  | 1589  7     189  | 489   2459  3    |
| 57    34    48   | 3589  5689  2    | 1     45679 468  |
:------------------+------------------+------------------:
| 8     26    5    | 123   4     13   | 7     126   9    |
| 4     79    3    | 6     129   179  | 5     8     12   |
| 1     79    26   | 5789  589   789  | 3     246   246  |
'------------------'------------------'------------------'


There are 3 candidates for digit 6 in row 6. The first one is at R6C5. The other 2 would both force R3C6 to 6. R1C5, R2C5 and R4C6 are the shared peers for R6C5 and R3C6. Those can be eliminated.

I needed 3 candidates to prove the eliminations. Is there a more straightforward pattern that can be used? No fishing here.

TIA,

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby ravel » Thu Feb 23, 2006 5:01 pm

Hm, i cannot see a pattern, but in all 3 cases R4C6 occupies row 4 and the 6's in boxes 1 and 2 take the rows 1 and 2, what elimates all 6's from column 7.
The other way round: Each 6 in column 7 would eliminate the 6's in R1C5, R2C5 and R4C6 (triple forcing chain):
R1C7=6 -> R1C256<>6 -> R2C3=6 -> R2C5<>6 -> R3C6=6 -> R4C6<>6
R2C7=6 -> R2C35<>6 -> R1C2=6 -> R1C56<>6 -> R3C6=6 -> R4C6<>6
R4C7=6 -> R4C56<>6 -> R6C5=6 -> R12C5<>6
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Thu Feb 23, 2006 6:37 pm

Question:
This are the 6's from the above candidate list:
Code: Select all
.----------+-----------+-----------+
|    6     |     6   6 | 6   6     |
|        6 |     6     | 6         |
|          |         6 |     6   6 |
:----------+-----------+-----------|
|          |     6   6 | 6   6   6 |
| 6        |           |           |
|          |     6     |     6   6 |
:----------+-----------+-----------|
|    6     |           |     6     |
|          | 6         |           |
|        6 |           |     6   6 |
'----------+-----------+-----------+

If there would not be a 6 in R4C7, the conjugated pairs R1C2/R2C3 and R7C1/R7C2 would allow you eliminate the other 6's in rows 1 and 2. How is this called and how can it be written in a nice loop ?
Think you could write then something like
[R4C6]-6-[R4C7]-([pattern x R1C2/R2C3,R7C1/R7C2])=6=[R3C6=6]-6-[R4C6]
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Thu Feb 23, 2006 6:38 pm

Sorry, post deleted because I engaged my typing fingers before putting my brain in gear. (Hopefully that won't be lost on those who've never driven a stick shift.:D )

Ron
Last edited by ronk on Thu Feb 23, 2006 3:08 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Thu Feb 23, 2006 6:52 pm

I do not understand, Ron. The eliminations can be made, if either a or one of the A's must be 6, right? But what tells you that this is the case ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Thu Feb 23, 2006 7:02 pm

ravel wrote:I do not understand, Ron. The eliminations can be made, if either a or one of the A's must be 6, right? But what tells you that this is the case ?

Thanks, looking at it again I don't either. I think that's what my wife calls a "brain fart".:) I will try to figure out what I was thinking and most likely end up deleting that post.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby vidarino » Thu Feb 23, 2006 7:41 pm

ravel wrote:If there would not be a 6 in R4C7, the conjugated pairs R1C2/R2C3 and R7C1/R7C2 would allow you eliminate the other 6's in rows 1 and 2. How is this called and how can it be written in a nice loop ?


Hmm, probably not quite what you're asking, but; If there weren't a 6 in R4C7, the ones in R12C7 would be locked to that row, and the rest of the 6s in box 3 could be eliminated. Then there would only be a single 6 left in row 3, which would wipe out the rest of box 2.

Expressed as a Nice Loop, I guess this will do;

R1C2=6=R2C3-6-R2C7=6=R1C7-6-R1C2

A.k.a. continuous X-Cycle, which means you can eliminate the rest of the 6s along the weak edges.
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Thu Feb 23, 2006 8:04 pm

Ruud wrote:There are 3 candidates for digit 6 in row 6. The first one is at R6C5. The other 2 would both force R3C6 to 6. R1C5, R2C5 and R4C6 are the shared peers for R6C5 and R3C6. Those can be eliminated.

I don't see how you get the "other 2 would both force R3C6 to 6" without involving the ER in box 9. Would you please clarify?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques