Nice loops for advanced level players - b/b plot

Advanced methods and approaches for solving Sudoku puzzles

Postby Jeff » Sat Dec 03, 2005 12:01 pm

rubylips wrote:Sorry for that slightly offbeat post. It's true - Firefox does display a frog instead of a puzzle. Here's an ASCII version for others out there who might be overrun with amphibian images at the moment:
Code: Select all
 . 3 . | . . . | . . .
 . 7 8 | 2 . 6 | 3 1 .
 6 9 . | . . . | . 5 2
-------+-------+------
 . 5 7 | 9 . 1 | 4 . .
 . 6 . | . . . | . 7 .
 . . 3 | 6 7 8 | 5 2 .
-------+-------+------
 3 8 . | 5 . . | . 4 7
 7 2 5 | 1 4 3 | 6 9 8
 . . . | . . . | . 3 5

Just to make sure everyone starts from the same point, here is the candidate grid:
Code: Select all
1245 3    124  | 478  1589 4579 | 789  68   469 
45   7    8    | 2    59   6    | 3    1    49   
6    9    14   | 3478 138  47   | 78   5    2   
---------------+----------------+---------------
28   5    7    | 9    23   1    | 4    68   36   
1289 6    129  | 34   235  245  | 89   7    139 
149  14   3    | 6    7    8    | 5    2    19 
---------------+----------------+---------------
3    8    169  | 5    269  29   | 12   4    7   
7    2    5    | 1    4    3    | 6    9    8   
149  14   1469 | 78   2689 279  | 12   3    5   
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Sat Dec 03, 2005 12:21 pm

Jeff,

You are right, the chain is not correctly written. Anyway, we dont need any chain to show that r1c7<>8. As I told you before, r1c7 = 8 implies that r5c3 cannot have any number, which is impossible. So, r1c7<>8.

BTW, I have already read your thread about triple implication chains. It is very nicely written. Congratulations.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Sat Dec 03, 2005 12:44 pm

Carcul wrote:BTW, I have already read your thread about triple implication chains. It is very nicely written. Congratulations.

Thanks:D . I am sure Max will love it. Personally, I found bennys almost locked set technique more direct and practical. I am still sharpening my almost locked set recognition ability to see whether it can be used to identify all outcomes implied by forcing chains.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sat Dec 03, 2005 12:58 pm

Carcul wrote:You are right, the chain is not correctly written. Anyway, we dont need any chain to show that r1c7<>8. As I told you before, r1c7 = 8 implies that r5c3 cannot have any number, which is impossible. So, r1c7<>8.

Carcul, the elimination is correct. Just a slight correction to the chain notation will fix it.

[r1c7]=9=[r5c7]-9-[r5c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r1c7] => r1c7<>8
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sat Dec 03, 2005 2:03 pm

Carcul wrote:I have solved the exercise you posted, but I did not found all the nice loops you said were necessary. I have used only about a few nice loops and one forcing net (in an empty cell contradiction argument). Could you list your chains?

Well done, Carcul. The empty cell contradiction argument is actually equivalent to a triple implication chain where the trivalue tripod is at r5c3. This explains why you only needed 6 double chains to complete the grid. I like your Chain 1, in particular, that fixed a 3 in r3c4.

I have two solutions, one involves 11 double chains, and one involves 8 double chains and one triple chain.

Either way, your solution uses less chains than mine.:D:D

I notice also that all your chains are discontinuous combination chains. In my solutions, apart from combination chains, there is a pure bilocation chain, few pure bivalue chains (xy-chains) and a continuous combination chain.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Sun Dec 04, 2005 4:23 pm

Thanks Jeff. But, like you said before, this is not a contest.:D
So, if you don’t mind, I insist and ask you again to list all double and triple chains in your two solutions.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

not very elegant

Postby bennys » Mon Dec 05, 2005 1:45 am

Code: Select all
 I have a solution (not very elegant)
+-------+-------+-------+
| . 3 . | . . . | . . . |
| . 7 8 | 2 . 6 | 3 1 . |
| 6 9 . | . . . | . 5 2 |
+-------+-------+-------+
| . 5 7 | 9 . 1 | 4 . . |
| . 6 . | . . . | . 7 . |
| . . 3 | 6 7 8 | 5 2 . |
+-------+-------+-------+
| 3 8 . | 5 . . | . 4 7 |
| 7 2 5 | 1 4 3 | 6 9 8 |
| . . . | . . . | . 3 5 |
+-------+-------+-------+

+----------------+----------------+----------------+
| 1245 3    124  |*478 *1589*4579 | 789  68   469  |
| 45   7    8    | 2    59   6    | 3    1    49   |
| 6    9    14   | 3478 138  47   | 78   5    2    |
+----------------+----------------+----------------+
| 28   5    7    | 9    23   1    | 4   *68  *36   |
| 1289 6    129  | 34   235  245  | 89   7    139  |
| 149  14   3    | 6    7    8    | 5    2    19   |
+----------------+----------------+----------------+
| 3    8    169  | 5    269  29   | 12   4    7    |
| 7    2    5    | 1    4    3    | 6    9    8    |
| 149  14   1469 | 78   2689 279  | 12   3    5    |
+----------------+----------------+----------------+

We will show that R5C7<>8 and that will solve the puzzle.
the problem cell is R5C6 lets call it x
A={R4C8,R4C9}
B={R1C4,R1C5,R1C6}  (notice that in B only R1C5 can be 1)

ok now
r5c7=8 will lock A and make R4C5=2 which eliminate 2 from x
also it will make R3C7=7 =>R3C6=4 which eliminate 4 from x and B
also it will force R1C7=9 and R1C9=8
which will lock B on 157 which will make R1C6=5(because r1c5 must be 1)
and that eliminate 5 from x.
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Jeff » Mon Dec 05, 2005 10:37 am

Carcul wrote:Thanks Jeff. But, like you said before, this is not a contest.:D
So, if you don’t mind, I insist and ask you again to list all double and triple chains in your two solutions.

Absolutely, I am just waiting for Max to publish his solution first in order to maintenance as much enjoyment for him as possible.
Jeff
 
Posts: 708
Joined: 01 August 2005

A shorter solution

Postby Carcul » Mon Dec 05, 2005 10:38 pm

I have noted that we can solve this puzzle using only nice loops (in the form of double and triple implication chains) through a simpler way - one double chain and two triple chains, which are the following:

Chain 1: [r3c4]=3=[r3c5]–3–[r4c5]–2–[r4c1]–8–[r4c8]–6–[r1c8]
-8–[r3c7]–7–[r3c6]–4–[r5c6]=4=[r5c4]=3=[r3c4] => r3c4 = 3.

Chain 2 (with a trivalue tripod at r5c3):
[r1c7]-8-[r3c7]-7-[r3c6]-4-[r3c3]-1-[r5c3]-9-[r5c7]=9=[r1c7]
[r1c7]=9=[r5c7]-9-[r5c3]-2-[r4c1]-8-[r4c8]-6-[r1c8]-8-[r1c7]
[r1c7]-8-[r3c7]-7-[r3c6]-4-[r3c3]-1-[r5c3]-2-[r4c1]-8-[r4c8]-6-[r1c8]-8-[r1c7]
This triple chain imply r1c7<>8.

Chain 3 (with a trivalue tripod at r1c6):
[r1c7]-9-[r5c7]-8-[r4c8]-6-[r4c9]-3-[r4c5]-2-[r5c6]-5-[r1c6]-4-[r3c6]-7-[r3c7]=7=[r1c7]
[r1c7]=7=[r3c7]-7-[r3c6]-4-[r1c6]-9-[r2c5]-5-[r2c1]-4-[r2c9]-9-[r1c7]
[r1c7]-9-[r5c7]-8-[r4c8]-6-[r4c9]-3-[r4c5]-2-[r5c6]-5-[r1c6]-9-[r2c5]-5-[r2c1]-4-[r2c9]-9-[r1c7]
This triple chain implies r1c7<>9, and that solve the puzzle.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Re: A shorter solution

Postby Jeff » Tue Dec 06, 2005 2:24 am

Carcul wrote:I have noted that we can solve this puzzle using only nice loops (in the form of double and triple implication chains) through a simpler way - one double chain and two triple chains, which are the following:

When nice and simple cross each other, that's elegance.:D Do you agree that with triple implication chain, we have reached the limit of the bilocation/blvalue plot technique?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Fri Dec 16, 2005 9:36 am

Jeff wrote:Absolutely, I am just waiting for Max to publish his solution first in order to maintenance as much enjoyment for him as possible.

I imagine Max is sleeping peacefully Z Z Z Z Z. I just have to keep my voice down. Here is my solution to the exercise with descriptions of trivial eliminations (include xy-wing) omitted:

Code: Select all
 *-----------*
 |...|...|...|
 |.78|2.6|31.|
 |69.|...|.52|
 |---+---+---|
 |..7|9.1|4..|
 |.6.|...|.7.|
 |..3|6.8|5..|
 |---+---+---|
 |38.|...|.47|
 |.25|1.3|69.|
 |...|...|...|
 *-----------*
 
 *-----------------------------------------------------------*
 | 1245  3     124   | 478   1589  4579  | 789   68    469   |
 | 45    7     8     | 2     59    6     | 3     1     49    |
 | 6     9     14    | 3478  138   47    | 78    5     2     |
 |-------------------+-------------------+-------------------|
 | 28    5     7     | 9     23    1     | 4     68    36    |
 | 1289  6     129   | 34    235   245   | 89    7     139   |
 | 149   14    3     | 6     7     8     | 5     2     19    |
 |-------------------+-------------------+-------------------|
 | 3     8     169   | 5     269   29    | 12    4     7     |
 | 7     2     5     | 1     4     3     | 6     9     8     |
 | 149   14    1469  | 78    2689  279   | 12    3     5     |
 *-----------------------------------------------------------*


1) combination chain: [r3c4]-7-[r3c6]-4-[r5c6]=4=[r5c4]=3=[r3c4] => r3c4<>7
2) combination chain: [r3c4]-8-[r3c7]-7-[r3c6]-4-[r5c6]=4=[r5c4]=3=[r3c4] => r3c4<>8
3) pure bivalue chain (xy-chain): [r7c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r5c7]-9-[r5c9]-1-[r6c2]-4-[r9c2]-1-[r7c3] => r7c3<>1
4) pure bivalue chain (xy-chain): [r9c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r5c7]-9-[r5c9]-1-[r6c2]-4-[r9c2]-1-[r9c3] => r9c3<>1
5) combination chain: [r1c3]-1-[r3c3]-4-[r3c6]-7-[r3c7]-8-[r1c8]=8=[r4c8]-8-[r4c1]-2-[r5c3]=2=[r1c3] => r1c3<>1

Code: Select all
 *-----------------------------------------------------------*
 | 1245  3     24    | 78    1589  4579  | 789   68    469   |
 | 45    7     8     | 2     59    6     | 3     1     49    |
 | 6     9     14    | 34    138   47    | 78    5     2     |
 |-------------------+-------------------+-------------------|
 | 28    5     7     | 9     23    1     | 4     68    36    |
 | 1289  6     129   | 34    235   245   | 89    7     139   |
 | 149   14    3     | 6     7     8     | 5     2     19    |
 |-------------------+-------------------+-------------------|
 | 3     8     69    | 5     269   29    | 1     4     7     |
 | 7     2     5     | 1     4     3     | 6     9     8     |
 | 149   14    469   | 78    689   79    | 2     3     5     |
 *-----------------------------------------------------------*


6) combination chain: [r3c5]-3-[r4c5]=3=[r4c9]=6=[r4c8]=8=[r1c8]-8-[r3c7]=8=[3c5] => r3c5<>3

Code: Select all
 *-----------------------------------------------------------*
 | 1245  3     24    | 78    1589  4579  | 789   68    469   |
 | 45    7     8     | 2     59    6     | 3     1     49    |
 | 6     9     14    | 3     18    47    | 78    5     2     |
 |-------------------+-------------------+-------------------|
 | 28    5     7     | 9     23    1     | 4     68    36    |
 | 1289  6     129   | 4     235   25    | 89    7     139   |
 | 149   14    3     | 6     7     8     | 5     2     19    |
 |-------------------+-------------------+-------------------|
 | 3     8     69    | 5     269   29    | 1     4     7     |
 | 7     2     5     | 1     4     3     | 6     9     8     |
 | 149   14    469   | 78    689   79    | 2     3     5     |
 *-----------------------------------------------------------*


7) continuous combination chain: =[r9c4]=8=[r9c5]-8-[r3c5]=8=[r3c7]=7=[r3c6]-7-[r9c6]=7=[9c4]=
=> r1c5<>8 and r1c6<>7

Code: Select all
 *-----------------------------------------------------------*
 | 1245  3     24    | 78    159   459   | 789   68    469   |
 | 45    7     8     | 2     59    6     | 3     1     49    |
 | 6     9     14    | 3     18    47    | 78    5     2     |
 |-------------------+-------------------+-------------------|
 | 28    5     7     | 9     23    1     | 4     68    36    |
 | 1289  6     129   | 4     235   25    | 89    7     139   |
 | 149   14    3     | 6     7     8     | 5     2     19    |
 |-------------------+-------------------+-------------------|
 | 3     8     69    | 5     269   29    | 1     4     7     |
 | 7     2     5     | 1     4     3     | 6     9     8     |
 | 149   14    469   | 78    689   79    | 2     3     5     |
 *-----------------------------------------------------------*


Uniqueness rectangle: [r6c1][r6c2][r9c1][r9c2] => r5c1<>9

Code: Select all
 *-----------------------------------------------------------*
 | 1245  3     24    | 78    159   459   | 789   68    469   |
 | 45    7     8     | 2     59    6     | 3     1     49    |
 | 6     9     14    | 3     18    47    | 78    5     2     |
 |-------------------+-------------------+-------------------|
 | 28    5     7     | 9     23    1     | 4     68    36    |
 | 128   6     129   | 4     235   25    | 89    7     139   |
 | 149   14    3     | 6     7     8     | 5     2     19    |
 |-------------------+-------------------+-------------------|
 | 3     8     69    | 5     269   29    | 1     4     7     |
 | 7     2     5     | 1     4     3     | 6     9     8     |
 | 149   14    469   | 78    689   79    | 2     3     5     |
 *-----------------------------------------------------------*


8) pure bilocation chain: [r9c2]=1=[r9c1]=9=[r6c1]=4=[r6c2]=1=[r9c2] => r9c2=1

Code: Select all
 *-----------------------------------------------------------*
 | 1245  3     24    | 78    159   459   | 789   68    469   |
 | 45    7     8     | 2     59    6     | 3     1     49    |
 | 6     9     14    | 3     18    47    | 78    5     2     |
 |-------------------+-------------------+-------------------|
 | 28    5     7     | 9     23    1     | 4     68    36    |
 | 128   6     129   | 4     235   25    | 89    7     139   |
 | 19    4     3     | 6     7     8     | 5     2     19    |
 |-------------------+-------------------+-------------------|
 | 3     8     69    | 5     269   29    | 1     4     7     |
 | 7     2     5     | 1     4     3     | 6     9     8     |
 | 49    1     469   | 78    68    79    | 2     3     5     |
 *-----------------------------------------------------------*


9) pure bivalue chain (xy-chain): [r2c1]-4-[r2c9]-9-[r6c9]-1-[r6c1]-9-[r9c1]-4-[r2c1] => r2c1<>4

Code: Select all
 *--------------------------------------------------*
 | 14   3    2    | 78   15   45   | 789  68   69   |
 | 5    7    8    | 2    9    6    | 3    1    4    |
 | 6    9    14   | 3    18   47   | 78   5    2    |
 |----------------+----------------+----------------|
 | 28   5    7    | 9    23   1    | 4    68   36   |
 | 28   6    19   | 4    235  25   | 89   7    139  |
 | 19   4    3    | 6    7    8    | 5    2    19   |
 |----------------+----------------+----------------|
 | 3    8    69   | 5    26   29   | 1    4    7    |
 | 7    2    5    | 1    4    3    | 6    9    8    |
 | 49   1    469  | 78   68   79   | 2    3    5    |
 *--------------------------------------------------*


10) pure bilocation chain: [r1c5]=5=[r1c6]=4=[r1c1]=1=[r6c1]=9=[r5c3]=1=[r5c9]=3=[r5c5]=5=[r1c5] => r1c5=5

The grid can be solved using basic rules from here.
Alternatively, Chains 8, 9 and 10 can be replaced by one triple implication chain as follows:

Triple combination chain with bivalue tripod at r1c6:
[r4c5]=3=[r4c9]=6=[r4c8]=8=[r5c7]=9=[r1c7]=7=[r3c7]-7-[r3c6]-4-[r1c6]-5-[r5c6]-2-[r4c5]
[r4c5]=3=[r4c9]=6=[r4c8]=8=[r5c7]=9=[r1c7]-9-[r1c6]-5-[r5c6]-2-[r4c5]
All imply r4c5<>2
Last edited by Jeff on Wed Mar 08, 2006 3:26 pm, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Wed Jan 18, 2006 12:02 pm

Carcul rated this grid as 'easy' in exercise 1 of this post.
Code: Select all
 *-----------*
 |...|...|...|
 |.9.|8.5|.4.|
 |..6|.7.|8..|
 |---+---+---|
 |.5.|...|.3.|
 |..1|.8.|6..|
 |.4.|...|.2.|
 |---+---+---|
 |..2|.6.|7..|
 |.6.|1.9|.5.|
 |...|...|...|
 *-----------*

 *--------------------------------------------------------------------*
 | 1      8      45     | 2      349    6      | 359    7      39     |
 | 7      9      3      | 8      1      5      | 2      4      6      |
 | 45     2      6      | 349    7      34     | 8      1      359    |
 |----------------------+----------------------+----------------------|
 | 2      5      89     | 6      49     17     | 14     3      78     |
 | 3      7      1      | 45     8      2      | 6      9      45     |
 | 6      4      89     | 39     359    17     | 15     2      78     |
 |----------------------+----------------------+----------------------|
 | 459    13     2      | 345    6      34     | 7      8      1349   |
 | 8      6      7      | 1      234    9      | 34     5      234    |
 | 49     13     45     | 7      2345   8      | 349    6      12349  |
 *--------------------------------------------------------------------*

I personally found this grid quite interesting because it can be reduced to many bivalue cells via basic rules, yet not one xy-chain can be found. An xyz wing is possible if it is not counted as one of the basic rules; but it doesn't help either. Another interesting point is that having completed a bilocation/bivalue plot, I could identify one nice loop to give one deduction. Normally, for a difficult grid, you struggle to identify a few nice loops, but it still doesn't solve the puzzle. In this case, you struggle to identify one nice loop, and it's what it takes to solve the puzzle. I consider this grid as 'hard' since this nice loop takes quite some effort to be found. The nice loop is a pure bilocation chain highlighted in red in the b/b plot below:

Pure bilocation chain:
[r9c3]=5=[r9c5]=2=[r9c9]=1=[r7c9]=9=[r7c1]=5=[r9c3] => r9c3=5

Image
Last edited by Jeff on Wed Jan 18, 2006 9:14 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Wed Jan 18, 2006 12:49 pm

Hi Jeff.

I rated that puzzle "easy" because I didn't take very long (I didn't "struggle") to find two discontinuous loops that solved the puzzle (which, interestingly, are not present in your bilocation/bivalue plot). But I think that rating a puzzle is a very personal question.

BTW, have someone managed to complete exercise #5?

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Jeff » Wed Jan 18, 2006 1:13 pm

Carcul wrote:.........find two discontinuous loops that solved the puzzle (which, interestingly, are not present in your bilocation/bivalue plot).

Hi Carcul, You are so gifted.:D Could you list the 2 nice loops you used to solve this puzzle for our readers please?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Carcul » Wed Jan 18, 2006 1:24 pm

Jeff wrote:Hi Carcul, You are so gifted.


I don't think so. Don't forget that you have used only one loop, while I used the following two:

[r3c4]=9=[r1c5]-9-[r1c7]=9=[r9c7]-9-[r9c1]-4-[r9c3]-5-[r9c5]=5=[r6c5]=3=[r6c4]=9=[r3c4], => r3c4=9.

[r7c4]=5=[r9c5]-5-[r9c3]-4-[r1c3]-5-[r3c1]-4-[r3c6]-3-[r7c6]-4-[r7c4], => r7c4<>4 => r7c4=5 which solve the puzzle.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

PreviousNext

Return to Advanced solving techniques

cron