Is there a simple alternative for this template discovery?

Advanced methods and approaches for solving Sudoku puzzles

Is there a simple alternative for this template discovery?

Postby Ruud » Tue Feb 21, 2006 12:44 am

Hi,

I am looking for a simple alternative for a few eliminations made by the template (POM) checker in SudoCue.

Here is the situation:

Code: Select all
.------------------.------------------.------------------.
| 39    6     5    | 7     2348  34   | 249   248   1    |
| 2     89    348  | 68    13458 13456| 4569  458   7    |
| 1     7     48   | 9     2458  456  | 2456  3     458  |
:------------------+------------------+------------------:
| 8     4     9    | 5     7     2    | 3     1     6    |
| 7     1     6    | 3     49    8    | 245   245   459  |
| 35    25    23   | 1     6     49   | 8     7     49   |
:------------------+------------------+------------------:
| 59    3     128  | 248   19    7    | 45    6     458  |
| 6     59    18   | 48    139   139  | 7     458   2    |
| 4     28    7    | 268   58    56   | 1     9     3    |
'------------------'------------------'------------------'

At this point, multi-colouring does not reveal anything, but a template check for digit 8 reveals that R2C4 and R9C5 can be eliminated.

I can see how it works:

Column 2 has 2 candidates for digit 8: R2C2 and R9C2.
When R2C2 is true, candidates in box 2 are locked to column 5, eliminating R9C5.
When R9C2 is true, candidates in box 8 are locked to column 4, eliminating R2C4.

My question to the advanced solving techniques team:

What is the simplest single-digit technique that can make these same eliminations?

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Re: Is there a simple alternative for this template discover

Postby aeb » Tue Feb 21, 2006 2:01 am

Ruud wrote:Hi,

I am looking for a simple alternative for a few eliminations made by the template (POM) checker in SudoCue.

Here is the situation:

Code: Select all
.------------------.------------------.------------------.
| 39    6     5    | 7     2348  34   | 249   248   1    |
| 2     89    348  | 68    13458 13456| 4569  458   7    |
| 1     7     48   | 9     2458  456  | 2456  3     458  |
:------------------+------------------+------------------:
| 8     4     9    | 5     7     2    | 3     1     6    |
| 7     1     6    | 3     49    8    | 245   245   459  |
| 35    25    23   | 1     6     49   | 8     7     49   |
:------------------+------------------+------------------:
| 59    3     128  | 248   19    7    | 45    6     458  |
| 6     59    18   | 48    139   139  | 7     458   2    |
| 4     28    7    | 268   58    56   | 1     9     3    |
'------------------'------------------'------------------'

At this point, a template check for digit 8 reveals that R2C4 and R9C5 can be eliminated.

What is the simplest single-digit technique that can make these same eliminations?

Hmm. There are lots of possible arguments. A fairly simple one is the broken wing that eliminates (2,4)8: look at the pentagon (1,5)-(2,4)-(2,2)-(9,2)-(9,5) for the digit 8. Since five is odd there must be two successive vertices that are not 8, and a common neighbour of them that is. This yields (2,4)!8 and hence (2,4)6, and (9,5)5 follows by singles.
aeb
 
Posts: 83
Joined: 29 January 2006

Re: Is there a simple alternative for this template discover

Postby ronk » Tue Feb 21, 2006 2:52 am

Ruud wrote:What is the simplest single-digit technique that can make these same eliminations?

Grouped multi-coloring:
Code: Select all
 . . . | . 8 . | . 8 .
 . A 8 | B 8 . | . 8 .
 . . 8 | . 8 . | . . 8
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . 8 | b . . | . . 8
 . . 8 | b . . | . 8 .
 . a . | B B . | . . .


This is a grouped turbot fish where color B sees both conjugate colors A and a. Therefore B represents false.

The 8s in column 4 comprise a grouped strong link. i.e., if r2c4<>8 then r789c4=8. The 8s in box 8 also comprise a grouped strong link, i.e., if r9c45<>8 then r78c4=8.

[edit: colored r9c4 and added the following]

The observant will note the above "if ... then" statements color r9c4 as 'b' for column 4 and as 'B' for box 8, and consider the "bi-coloring" to invalidate the elimination r9c4<>8. But of the two interpretations, I see nothing wrong with choosing the one which maximizes the eliminations.

Following the chain clockwise, in implication stream terms we have:
either r9c45<>8,
or r9c45=8 -> r9c2<>8 -> r2c2=8 -> r2c4<>8 -> r789c4=8 -> r9c5<>8 implying only r9c5<>8

If we follow the chain counter-clockwise, for the 2nd implication stream we have:
r9c45=8 -> r78c4<>8 -> r2c4=8 -> r2c2<>8 -> r9c3=8 -> r9c45<>8 implying r9c4<>8 and r9c5<>8

Presented with the choice, I think it is perfectly valid to choose the latter which yields a 2nd elimination.

Ron
Last edited by ronk on Tue Feb 21, 2006 8:25 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Feb 21, 2006 4:46 am

Code: Select all
.------------------.------------------.------------------.
| 39    6     5    | 7     2348  34   | 249   248   1    |
| 2    *89    348  |*68    13458 13456| 4569  458   7    |
| 1     7     48   | 9     2458  456  | 2456  3     458  |
:------------------+------------------+------------------:
| 8     4     9    | 5     7     2    | 3     1     6    |
| 7     1     6    | 3     49    8    | 245   245   459  |
| 35    25    23   | 1     6     49   | 8     7     49   |
:------------------+------------------+------------------:
| 59    3     128  |#248   19    7    | 45    6     458  |
| 6     59    18   |#48    139   139  | 7     458   2    |
| 4    *28    7    |*268  -58-   56   | 1     9     3    |
'------------------'------------------'------------------'

Filet-O-Fish X-Wing in r29c24, fin in r78c4 kills 8 in r9c5. Locked candidates then kills 8 in r2c4.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Havard » Tue Feb 21, 2006 11:13 am

And I would like to add that my pet ER (empty rectangle) does it too:

Code: Select all
 
 . . . | X . X | . . .
 . 8 . | . + . | . . .
 . | . | X . X | . . .
---|---+-------+-------
 . | . | . . . | . . .
 . | . | . . . | . . .
 . | . | . . . | . . .
---|---+-------+-------
 . | . | . . . | . . .
 . | . | . . . | . . .
 . 8 . | . * . | . . .
- marks strong links
x marks the ER (Empty Rectangle
+ marks the ERI (Empty Rectangle Intersection)
* marks the elimination


havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Ruud » Tue Feb 21, 2006 12:35 pm

Thanks for al the alternatives!

aeb wrote:Since five is odd there must be two successive vertices that are not 8, and a common neighbour of them that is. This yields (2,4)!8

This is a reasoning I cannot follow. What are the 2 vertices you isolated and what is the common neighbour. Please identify the cells involved in this process.

ronk wrote:Grouped multi-coloring

This is something I like, because it is the only technique that wipes out both candidates in a single move. Where can I read more about the rules behind these groups?

Myth Jellies wrote:Filet-O-Fish X-Wing in r29c24, fin in r78c4 kills 8 in r9c5.

Nice & easy. In terms of simplicity, this is a winner!
Code: Select all
.------------------.------------------.------------------.
| 39    6     5    | 7    #2348  34   | 249   248   1    |
| 2    *89    348  |-68-  *13458 13456| 4569  458   7    |
| 1     7     48   | 9    #2458  456  | 2456  3     458  |
:------------------+------------------+------------------:
| 8     4     9    | 5     7     2    | 3     1     6    |
| 7     1     6    | 3     49    8    | 245   245   459  |
| 35    25    23   | 1     6     49   | 8     7     49   |
:------------------+------------------+------------------:
| 59    3     128  | 248   19    7    | 45    6     458  |
| 6     59    18   | 48    139   139  | 7     458   2    |
| 4    *28    7    | 268  *58    56   | 1     9     3    |
'------------------'------------------'------------------'

The above is an alternative that kills R2C4 first, I think. Would it be possible to mark a candidate for elimination, use it in another formation to eliminate another candidate, before killing them both?

Havard wrote:And I would like to add that my pet ER (empty rectangle) does it too

I never heard of this technique. Can you point me towards an explanation?

Thanks again.

If there are other techniques that can do the trick, keep them coming!

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby ronk » Tue Feb 21, 2006 12:37 pm

Havard wrote:x marks the ER (Empty Rectangle
+ marks the ERI (Empty Rectangle Intersection)

What is the significance of the ERI? IOW please explain the connection between the ERI and the elimination.

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

Postby vidarino » Tue Feb 21, 2006 12:42 pm

Ruud wrote:
aeb wrote:Since five is odd there must be two successive vertices that are not 8, and a common neighbour of them that is. This yields (2,4)!8

This is a reasoning I cannot follow. What are the 2 vertices you isolated and what is the common neighbour. Please identify the cells involved in this process.


Since there can't be a 5-sided chain of only strong links, at least one of the candidates that make the weak links weak must be true. Here, all the "guadians" (the term used in the original Broken Wing explanation) can see a common cell, which therefore cannot be 8.

Havard wrote:And I would like to add that my pet ER (empty rectangle) does it too

I never heard of this technique. Can you point me towards an explanation?


It's only a simplified special case of grouped coloring.
More here. It borrows heavily from from the "Hinge pattern", as far as I can tell: http://www.sudoku.org.uk/discus/messages/29/414.html?1135572720

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ravel » Tue Feb 21, 2006 2:09 pm

This puzzle leads to another interesting advanced coloring problem:
Code: Select all
------------
...|.7.|.9.
6.7|49.|...
5..|..8|...
------------
...|..5|...
.8.|942|...
9..|.8.|12.
------------
..5|...|..7
...|..7|.53
7.2|..4|.8.
------------

3 3 3 | . . 3 | 3 . .
. . . | . . 3 | . 3 .
. 3 3 | 3 3 . | 3 3 .
---------------------
. . 3 | 3 3 . | . 3 .
3 . 3 | . . . | 3 3 .
. . 3 | . . 3 | . . .
---------------------
3 3 . | 3 3 . | . . .
. . . | . . . | . . 3
. 3 . | 3 . . | . . .

The 3's in R1C13,R4C8 and R5C13 can be eliminated.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Tue Feb 21, 2006 2:13 pm

Ruud wrote:Thanks for all the alternatives!
...................
ronk wrote:Grouped multi-coloring

Where can I read more about the rules behind these groups?

Three threads on this forum ...
Forcing chains: Terminology and Definition
Nice loops for intermediate level players - Grouped x-cycle
Simple Colouring and Grouping of Candidates

There's more to be done on this topic IMO. In particular, the treatment of overlapping groups has not been rigorously addressed.

Ruud wrote:This is something I like, because it is the only technique that wipes out both candidates in a single move.

I think full exploitation of that particular 'grouped turbot fish' would wipe out four candidates, because it is actually a chain of four strong links.
Code: Select all
 . . . | . 8 . | . 8 .
 . A 8 | A 8 . | . 8 .
 . . 8 | . 8 . | . . 8
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . 8 | a . . | . . 8
 . . 8 | a . . | . 8 .
 . a . | A A . | . . .

This viewpoint has two occurrences of color A in row 2, which is impossible. Therefore color A represents false. Note that color A also occurs twice in column 4. However, eliminations on that basis would not be valid AFAIK, an example of hazards created by the complexity of candidate grouping.

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

Postby Havard » Tue Feb 21, 2006 2:54 pm

Ruud wrote:
Havard wrote:And I would like to add that my pet ER (empty rectangle) does it too

I never heard of this technique. Can you point me towards an explanation?


ronk wrote:
Havard wrote:x marks the ER (Empty Rectangle
+ marks the ERI (Empty Rectangle Intersection)

What is the significance of the ERI? IOW please explain the connection between the ERI and the elimination.


I just wrote a topic on it.
http://forum.enjoysudoku.com/viewtopic.php?t=3251
Should answer all questions!:)
Havard
 
Posts: 378
Joined: 25 December 2005

Postby ravel » Tue Feb 21, 2006 3:16 pm

The ER is very good for my sample above, Havard:
Code: Select all
3 3 3 | . . 3 | 3 . .
. . . | . . 3 | . 3 .
. 3 3 | 3 3 . | 3 3 .
---------------------
. . 3 | 3 3 . | . 3 .
3 . 3 | . . . | 3 3 .
. . 3 | . . 3 | . . .
---------------------
3 3 . | 3 3 . | . . .
. . . | . . . | . . 3
. 3 . | 3 . . | . . .

---------------------

3 3 3 | . . 3 | 3 . .
. . . | . . a | . b .
. 3 3 | 3 3 . | 3 3 .
---------------------
. . 3 | 3 3 + | . * .
3 . 3 | X X . | 3 3 .
. . 3 | X X 3 | . . .
---------------------
3 3 . | 3 3 . | . . .
. . . | . . . | . . 3
. 3 . | 3 . . | . . .

Allows to eliminate 3 from R4C8. The others can be done with locked candidates.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Havard » Tue Feb 21, 2006 3:19 pm

ravel wrote:The ER is very good for my sample above, Havard:
Code: Select all
3 3 3 | . . 3 | 3 . .
. . . | . . 3 | . 3 .
. 3 3 | 3 3 . | 3 3 .
---------------------
. . 3 | 3 3 . | . 3 .
3 . 3 | . . . | 3 3 .
. . 3 | . . 3 | . . .
---------------------
3 3 . | 3 3 . | . . .
. . . | . . . | . . 3
. 3 . | 3 . . | . . .

---------------------

3 3 3 | . . 3 | 3 . .
. . . | . . a | . b .
. 3 3 | 3 3 . | 3 3 .
---------------------
. . 3 | 3 3 + | . * .
3 . 3 | x x . | 3 3 .
. . 3 | x x 3 | . . .
---------------------
3 3 . | 3 3 . | . . .
. . . | . . . | . . 3
. 3 . | 3 . . | . . .

Allows to eliminate 3 from R4C8. The others can be done with locked candidates.


cool! I am very happy to see someone finding a bit of use for it!:D
thanks!

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby ronk » Tue Feb 21, 2006 3:42 pm

ravel wrote:Allows to eliminate 3 from R4C8. The others can be done with locked candidates.

Very nice. So I guess that means when you wrote ...
The 3's in R1C13,R4C8 and R5C13 can be eliminated.

... you meant ... The 3's in R13C3,R4C8 and R5C13 can be eliminated. However, it is customary to only list the elimination directly made by a technique, namely r4c8<>3. When listing sequential eliminations, it is also customary to list them in order, i.e., r4c8, r5c13, and then r13c3.

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

Postby ravel » Tue Feb 21, 2006 4:13 pm

ronk wrote:... you meant ... The 3's in R13C3,R4C8 and R5C13 can be eliminated.

Yes, thank you
However, it is customary to only list the elimination directly made by a technique, namely r4c8<>3. When listing sequential eliminations, it is also customary to list them in order, i.e., r4c8, r5c13, and then r13c3.

It is also possible to eliminate 3 in R5C1 first (i did it to get the number 1 for this cell), but it is rather complicated. It follows that R4C8=3 and a contradiction then, how it is illustrated by the ER.
You also can start with R13C3, because it follows that R5C1=3 and then R4C8=3.
ravel
 
Posts: 998
Joined: 21 February 2006

Next

Return to Advanced solving techniques

cron