What methods do you use past forcing chains? (2nd try)

Advanced methods and approaches for solving Sudoku puzzles

Postby Wolfgang » Mon Feb 06, 2006 5:24 pm

Hi Tso,
Carcul wrote:For puzzle #6 we have...


Yet another way to solve it (sometimes its easier for me to solve it myself than to read the nice loop notation:) )
Code: Select all
+----------------+----------------+----------------+
| 123  9    138  | 4    12   7    | 15   6    58   |
| 7    128  4    | 12   6    5    | 139  38   29   |
| 6    12   5    | 8    9    3    | 17   47   24   |
+----------------+----------------+----------------+
| 8    3    2    | 9    7    1    | 6    45   45   |
| 9    4    6    | 5    3    8    | 2    1    7    |
| 15   157  17   | 6    4    2    | 8    9    3    |
+----------------+----------------+----------------+
| 1235 1578 137  | 13   125  9    | 4    3578 6    |
| 4    257  379  | 23   8    6    | 3579 357  1    |
| 135  6    1389 | 7    15   4    | 359  2    589  |
+----------------+----------------+----------------+


If r1c5=1:
1.r1c1=2,r3c2=1,r2c2=8,r1c9=8
2.(r3c2=1)r3c9=2,r2c9=9
3.(r1c5=1)r9c5=5
No candidate left for r9c9.

=>r2c4=1

Code: Select all
+----------------+----------------+----------------+
| 13   9    38   | 4    2    7    | 15   6    58   |
| 7    28   4    | 1    6    5    | 39   38   29   |
| 6    12   5    | 8    9    3    | 17   47   24   |
+----------------+----------------+----------------+
| 8    3    2    | 9    7    1    | 6    45   45   |
| 9    4    6    | 5    3    8    | 2    1    7    |
| 15   157  17   | 6    4    2    | 8    9    3    |
+----------------+----------------+----------------+
| 2    1578 17   | 3    15   9    | 4    78   6    |
| 4    57   39   | 2    8    6    | 3579 357  1    |
| 135  6    389  | 7    15   4    | 359  2    589  |
+----------------+----------------+----------------+


If r8c7=7:
1.r8c2=5,r8c8=3
2.r7c8=8,r2c8=3
=>r3c7=7
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby aeb » Mon Feb 06, 2006 5:48 pm

Carcul wrote:For puzzle #6 we have (without eliminating “1” from r2c2):
2. [r7c1]=2=[r1c1]-2-[r1c5]=2=[r2c4]{-2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4]-1-[r7c1|r7c3]}-2-[r2c9]-9-[r9c9]-8-[r9c3](-3-[r7c1])-3-[r7c3]-7-[r6c3]-1-[r6c1]-5-[r7c1], => r7c1<>1,3,5 => r7c1=2.

Yes, I started with (7,1)1 > (1,1)2 > (1,5)!2 > (2,4)2 > (7,4)1 > (7,1)!1 which is very similar, for the weaker conclusion r7c1<>1.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby tso » Mon Feb 06, 2006 8:00 pm

First, thanks everyone for your participation in this thread.
Second, do you *like* solving this type of puzzle? If so, do you like being presented with the challenge where it is given that a certain set of tactics has already been exhausted?


Jeff wrote:
Tso wrote:What methods do you use past forcing chains?

Hi Tso, 'Simple forcing chains', as defined in your post, are double implication forcing chains in which the chain nodes are single cells. Therefore, according to that definition and for the purposes of this thread, the following forcing chains/nets are not ‘simple forcing chains’:

Forcing chains that involve more than 2 implication streams
Forcing chains/nets that have nodes consisting of 2 or more cells
Forcing chains which have nodes that infer 2 or more nodes downstream

The method you are looking for are therefore include but not necessarily limited to the following:

  • Triple implication nice loops
  • Grouped nice loops
  • Multiple inference nice loops
  • Almost 'a-set-pattern' nice loops, eg. Almost uniqueness pattern nice loops
  • Family of almost locked set rules, eg, xz rules
  • POM
  • Fillet-O-fish
  • BUG and BUG-Lite
Together, I believe any grids can be solved and these can all be done without computer.:D


I agree your entire response except that there is no reason to be limited to double implication chains -- triple, quadruple, etc -- still fit my definition of simple forcing chains.

I agree with you last sentence -- my question isn't so much "if" puzzles like these can be solved but how actual humans tend to approach these -- especially in situations where they know in advance that there are no simple forcing chains left to move the puzzle forward.


castalia"][quote="Jeff wrote:... Perhaps you would care to try your hand at these:

http://home.comcast.net/~mshelor/files/impossible.db

... they are the 520 puzzles that stumped David Eppstein's solver.



I took a look at a dozen of them. They were all solvable by Nishio, many with no other advanced tactics. It seems like a database of Nishio practice.


maria45 wrote:Hello tso,

well, I'm not quite sure about the meaning of your restriction regarding "no memory". Without much effort, I could find a forcing chain in your first puzzle:

g9=5 or g1=5, k1=3, k3=6, k6=2, g6=1 > g9!=1

One could argue that there is a "memory" step involved in this, because you need both implications, k1=3 and k3=6 to get k6=2. Is this already ruled out in your restriction?

Anyhow, you asked, what human solvers would apply. Thats an example.

Greetings, Maria


On one hand, yes, this method *does* require memory and is therefore beyond simple forcing chains.

On the other hand, this is *exactly* the response I'm looking for -- the methods that carbon based solvers are actually using on this type of puzzle. I often find similar deductions -- only when I'm forced to write them down do I feel I have to label them as one tactic or another.
(On the other, other hand -- this doesn't move the puzzle forward much.)


Carcul wrote:Hi Tso.

For puzzle #4 we have (and its not necessary to exclude previously "3" from r2c5):

[r3c4]=2=[r5c4]-2-[r5c8]-3-[r2c8]-2-[r2c2]-9-[r3c3]-3-[r3c4], => r3c4<>3;

[r1c4]-8-[r5c4]=8=[r5c6]-8-[r7c6]-5-[r9c6]-2-[r9c5](-3-[r2c5])-3-[r3c45]-9-[r2c5]-8-[r1c4], => r1c4<>8 and that solve the puzzle.

Regards, Carcul


That first nice loop is a simple forcing chain I missed:

r3c3=3 -> r3c4<>3
r3c3=9 -> r2c2=2 -> r2c8=3 -> r5c8=2 -> r5c4<>2 -> r3c4=2 -> r3c4<>3
Therefore, r3c4<>3

The second one is exactly what I'm looking for.

r2c5=8 -> r1c4<>8
r2c5=9 -> r3c4=2;
(r2c5=9 AND r3c4=2) -> r3c5=3 -> r9c5=2 -> r9c6=5 -> r7c6=8 -> r5c6<>8 -> r5c4=8 -> r1c4<>8
Therefore, r1c4<>8

By what method did you find these deduction -- that is, did you find the deduction and state it as a nice loop, or find the nice loop which showed you where there was a deduction?

Carcul wrote:Hi Tso.

For puzzle #5 we have (and is not necessary to eliminate “1” from r7c7):

1. [r4c9]=2=[r4c8]-2-[r7c8]-1-[r7c5]-8-[r2c5]-7-[r2c7]-1-[r1c9](-7-[r4c9|r5c9])-7-[r9c9](-8-[r4c9])-8-[r5c9]-3-[r4c9], => r4c9<>3,7,8.

2. [r6c456]-7-[r6c3]=7=[r4c3](-7-[r4c4])-7-[r4c89]-1-[r4c4]-8-[r5c4]-7-[r6c456] => r6c456<>7.

3. [r6c3]=7=[r4c3]-7-[r4c8]-1,2-[r7c9]=2=[r4c9]=1=[r1c9]-1-[r2c7]-7-[r6c7]=7=[r6c3], => r6c3=7.

4. [r2c7]=7=[r4c7]-7-[r4c8]-1,2-[r7c9]=2=[r4c9]=1=[r1c9]-1-[r2c7], => r2c7<>1 and that solve the puzzle.

Regards, Carcul


*These* are the kinds of fancy-pants deductions I'm looking for. Could you explain some of the notation -- specificaly, the use of paranthesis and the vertical bar? Maybe you could spell out the first loop for the layperson? Should I be able to look at nice loop #1 and be able to see that r4c0<>3,7,8? How? Could you spell out or point to the rule that allows the reader to make the deduction from the notation?

How are you finding these?


Terek seems to have found several simple forcing chains in both #4 and #6 that I missed.


aeb wrote:
tso wrote:After standard advanced stuff:

Code: Select all
+-------------------+-------------------+-------------------+
| 5     18    2     | 6     378   378   | 4     9     17    |
| 9     6     18    | 2     78    4     | 17    3     5     |
| 3     7     4     | 5     9     1     | 2     8     6     |
+-------------------+-------------------+-------------------+
| 4     5     378   | 178   6     9     | 1378  127   12378 |
| 1     9     6     | 78    2     378   | 5     4     378   |
| 2     38    378   | 147   3457  3578  | 1378  6     9     |
+-------------------+-------------------+-------------------+
| 7     4     5     | 9     18    6     | 38    12    1238  |
| 8     2     9     | 3     157   57    | 6     157   4     |
| 6     13    13    | 478   4578  2     | 9     57    78    |
+-------------------+-------------------+-------------------+

(9,5)8 > (2,5)7 > (2,7)1 > (1,9)7 > (9,9)8 > (9,5)!8 eliminates 8 at (9,5).


Another perfectly valid simple forcing chain in #6 I missed, though it doesn't advance the puzzle much.
Last edited by tso on Mon Feb 06, 2006 8:48 pm, edited 1 time in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Wolfgang » Mon Feb 06, 2006 9:06 pm

tso wrote:
castalia wrote:http://home.comcast.net/~mshelor/files/impossible.db

I took a look at a dozen of them. They were all solvable by Nishio, many with no other advanced tactics. It seems like a database of Nishio practice.

Mhm, i fed susser 2.0.4 with the first 20. 5 were solved with nishio, 3 with UR, 3 with forcing chains and 6 with tabling (in ascending order). Maybe someone could split the list into groups from medium to unlimited.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby aeb » Mon Feb 06, 2006 9:08 pm

tso wrote:
castalia wrote:http://home.comcast.net/~mshelor/files/impossible.db

I took a look at a dozen of them. They were all solvable by Nishio, many with no other advanced tactics. It seems like a database of Nishio practice.

Hmm. It seems that I do not need Nishio that often (only once for the first 25 puzzles). Let me show the start of the first one.

(1,1)2 > (8,1)3 > (8,7)8 > (4,7)3 > (9,7)1 > (7,9)!1 > (7,2)1 > (3,2)2 > (1,1)!2

(1,[23])2 > (3,2)1 > (2,1)!1 > (9,1)1 > (9,7)!1 > (4,7)1 > (4,8)3 > (7,8)!3 > (7,3)3 > (3,3)2 > (1,[23])!2

etc.
tso wrote:
aeb wrote:(9,5)8 > (2,5)7 > (2,7)1 > (1,9)7 > (9,9)8 > (9,5)!8 eliminates 8 at (9,5).

Another perfectly valid simple forcing chain in #6 I missed, though it doesn't advance the puzzle much.

Maybe it was #5. There was also a solution of #3, or at least the first step - can provide more on request. Concerning notation,
Carcul wrote:For puzzle #6 we have:
2. [r7c1]=2=[r1c1]-2-[r1c5]=2=[r2c4]{-2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4]-1-[r7c1|r7c3]}-2-[r2c9]-9-[r9c9]-8-[r9c3](-3-[r7c1])-3-[r7c3]-7-[r6c3]-1-[r6c1]-5-[r7c1], => r7c1<>1,3,5 => r7c1=2.

which looks complicated because it really is three chains in one, namely two simple chains
(7,1)1 > (1,1)2 > (1,5)!2 > (2,4)2 > (7,4)1 > (7,1)!1
and
(7,1)5 > (1,1)2 > (1,5)!2 > (2,4)2 > (7,4)1 > (7,3)7 > (6,3)1 > (6,1)5 > (7,1)!5
and the more complicated
(7,1)3 > (1,1)2 > (1,5)!2 > (2,4)2 > {(2,9)9 > (9,9)!9 and (8,4)3 > (8,[78])5 > (9,9)!5} > (9,9)8 > (9,3)3 > (7,1)!3.
(Basically it is the Nishio "assume that r1c1 is 2, and write down all consequences until one reaches a contradiction".)
aeb
 
Posts: 83
Joined: 29 January 2006

Postby Carcul » Mon Feb 06, 2006 11:27 pm

Hi Tso.

For puzzle #3 here is a possible solution:

1. [r1c6]=4=[r9c6]-4-[r7c5]-5-[r7c1]-3-[r7c3]=3=[r2c3]-3-[r2c6](-8-[r1c6])-8-[r4c6]-5-[r1c6], => r1c6<>5,8.

2. [r3c7]=4=[r3c5]-4-[r1c6]-3-[r2c6]{-8-[r4c6](-5-[r4c7])=8=[r4c4]=2=[r6c4]-2-[r6c9]}-8-[r2c8]-2-[r4c8]-4-[r4c7](-9-[r3c7])-9-[r6c9]-5-[r5c7]-8-[r8c7]-3-[r3c7], => r3c7<>3,9.

3. [r4c8]=4=[r4c7]-4-[r3c7]=4=[r3c5]-4-[r1c6]-3-[r2c6]-8-[r2c8]-2-[r4c8], => r4c8<>2.

4. [r4c1]=3=[r4c2]-3-[r3c2]=3=[r3c9]-3-[r2c9]-9-[r6c9]=9=[r4c7]-9-[r4c1], => r4c1<>9.

5. [r5c1]=6=[r8c1]=9=[r1c1]=2=[r2c3]=3=[r7c3]-3-[r7c1]-5-[r5c1], r5c1<>5.

6. [r7c5]-5-[r7c1]=5=[r4c1]-5-[r4c6]=5=[r9c6]-5-[r7c5], => r7c5<>5.

7. [r4c7]=9=[r1c7]-9-[r2c9]-3-[r2c6]-8-[r4c6]-5-[r4c7], r4c7<>5.

8. Uniqueness: r9c5<>2.

9. [r8c7]=3=[r1c7]-3-[r3c9]=3=[r3c2]-3-[r4c2]-2-[r4c4]=2=[r6c4]=5=[r6c9]-5-[r5c7]-8-[r8c7], => r8c7<>8.

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

Postby Carcul » Mon Feb 06, 2006 11:56 pm

Tso wrote:By what method did you find these deduction -- that is, did you find the deduction and state it as a nice loop, or find the nice loop which showed you where there was a deduction?


The second method: I found the deductions by constructing the nice loops and arriving to the conclusions.

Tso wrote:Could you explain some of the notation -- specificaly, the use of paranthesis and the vertical bar? Maybe you could spell out the first loop for the layperson? Should I be able to look at nice loop #1 and be able to see that r4c0<>3,7,8? How? Could you spell out or point to the rule that allows the reader to make the deduction from the notation?


The paranthesis denote ramifications of the "main" implication stream, or, more exactly, multiple implications. The vertical bar separates two or more cells that are simultaneously implied by the previous link. You can make the deduction r4c9<>3,7,8 from the notation, by noting that from r4c9 "departs" a strong link with label "2", and to r4c9 "arrive" three weak links with labels "3", "7", and "8": so, according to the nice loop rules, 3,7, and 8 can be eliminated from r4c9. Here is my "spell out": if r4c9 is "2", then it cannot be 3,7,8; if r4c9 is not "2", then you will get r1c9=7, r9c9=8, and r5c9=3, and so r4c9 cannot be 3,7,8 in either case.

Tso wrote:How are you finding these?


Constructing the nice loops and allowing for multiple implications.

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

Postby ronk » Tue Feb 07, 2006 12:02 am

aeb wrote:Concerning notation,
Carcul wrote:For puzzle #6 we have:
2. [r7c1]=2=[r1c1]-2-[r1c5]=2=[r2c4]{-2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4]-1-[r7c1|r7c3]}-2-[r2c9]-9-[r9c9]-8-[r9c3](-3-[r7c1])-3-[r7c3]-7-[r6c3]-1-[r6c1]-5-[r7c1], => r7c1<>1,3,5 => r7c1=2.

which looks complicated because it really is three chains in one, namely two simple chains
(7,1)1 > (1,1)2 > (1,5)!2 > (2,4)2 > (7,4)1 > (7,1)!1
and
(7,1)5 > (1,1)2 > (1,5)!2 > (2,4)2 > (7,4)1 > (7,3)7 > (6,3)1 > (6,1)5 > (7,1)!5
and the more complicated ........................................

Unfortunately, your chains don't show how (7,3)!3.

(Basically it is the Nishio "assume that r1c1 is 2, and write down all consequences until one reaches a contradiction".)

I see no contradiction in the Carcul's original implication network, for which the implication streams can be diagrammed as follows:
Code: Select all
                               r2c4-2-r8c4-3-r7c4-1-[r7c3|r7c1]
                             ^                        v         v
                           ^                        v              v
                         ^                        v                   v
r7c1=2=r1c1-2-r1c5=2=r2c4-2-r2c9-9-r9c9-8-r9c3-3-r7c3-7-r6c3-1-r6c1-5-r7c1
                    v               ^       v                          ^
                  v                  ^       v                        ^
               r2c4-2-r8c4-3-r8c78-5-r9c9     v                      ^
                                               v > > > > > r9c3-3-r7c1

From the diagram, it is easy to see that digits 1 and 3 must be eliminated from r7c3 ... before one can deduce that it hold digit 7.

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

Re: What methods do you use past forcing chains? (2nd try)

Postby aeb » Tue Feb 07, 2006 12:34 am

tso wrote:Puzzle 2 - After easy tactics:
Code: Select all
+-------------------+-------------------+-------------------+
| 2389  5     1     | 2689  248   3469  | 3489  248   7     |
| 4     3678  23679 | 25789 258   379   | 389   28    1     |
| 23789 378   2379  | 2789  1     3479  | 5     6     3489  |
+-------------------+-------------------+-------------------+
| 257   4     27    | 3     6     8     | 29    1     59    |
| 35    36    8     | 1     9     2     | 7     45    456   |
| 1     9     26    | 4     7     5     | 268   3     68    |
+-------------------+-------------------+-------------------+
| 789   2     5     | 6789  3     1     | 468   478   468   |
| 3789  1     3479  | 56789 458   4679  | 368   578   2     |
| 6     378   347   | 2578  2458  47    | 1     9     358   |
+-------------------+-------------------+-------------------+

[/code]

Maybe this is the only one where no approach has been given yet.
First eliminate a lot of 7's, then show that (4,3)!2.
(7,4)7 > (7,8)!7 > (8,8)7 > (9,9)5 > (3,9)3 > (3,6)4 > (9,6)7 > (7,4)!7
(9,3)7 > (4,3)2 > (4,1)7 > (4,9)5 > (3,9)9 > (3,6)4 > (9,6)7 > (9,3)!7
(2,6)7 > (9,6)4 > (9,3)3 > (9,9)!3 > (3,9)3 > (3,6)4 > (9,6)7 > (2,6)!7
(3,6)7 > (3,9)4 > (9,9)3 > (9,3)4 > (9,6)7 > (3,6)!7
so that the 7 of box 2 is in column 4
(8,6)7 > (9,6)4 > (9,3)3 > (9,9)!3 > (3,9)3 > (3,6)4 > (9,6)7 > (8,6)!7,
and therefore (9,6)7 and (9,2)!7.
Now there is an X-wing eliminating 7's from ([23],3).
Now a Nishio-like net:
(4,3)2 > (4,7)9 > (4,9)5 > (5,8)4 > ([12],8)[28] > (2,7)[39]
But also (4,7)9 > (2,7)!9, hence (2,7)3
But also (4,3)2 > (6,3)6 >> (2,3)[39]
No value is left for (2,6).
Hence (4,3) is not 2.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby aeb » Tue Feb 07, 2006 12:43 am

ronk wrote:Unfortunately, your chains don't show how (7,3)!3.

Ha, you just deleted the line showing that.
Note that my three lines are exactly equivalent to what Carcul wrote down, it is precisely the same reasoning, just with a notation that is easier for me to read.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby ronk » Tue Feb 07, 2006 1:30 am

aeb wrote:
ronk wrote:Unfortunately, your chains don't show how (7,3)!3.

Ha, you just deleted the line showing that.

There is no (7,3) in the deleted line, so I don't see how that's possible. Perhaps you could enlighten me.

Note that my three lines are exactly equivalent to what Carcul wrote down, it is precisely the same reasoning, just with a notation that is easier for me to read.

They don't appear equivalent for the reason already given.

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

Postby aeb » Tue Feb 07, 2006 2:13 am

ronk wrote:Unfortunately, your chains don't show how (7,3)!3.

Ach, replied too quickly, thought you meant (7,1)!3. But see
(7,3)3 > (7,4)1 > (2,4)2 > (1,5)1 > (1,1)2 > (1,3)3 > (7,3)!3
aeb
 
Posts: 83
Joined: 29 January 2006

Re: What methods do you use past forcing chains? (2nd try)

Postby Jeff » Tue Feb 07, 2006 3:25 am

aeb wrote:Hmm. In my opinion POM is a technique for solving POM puzzles. One uses backtrack/recursion/trial-and-error to go from a given Sudoku puzzle to the start of the corresponding POM puzzle. Sometimes a difficult Sudoku puzzle is already solved by doing this backtrack that produces the possible number patterns, and no further POM work is required.

Hi Aeb, Your statement puzzles me as I have no idea what a 'POM puzzle' is. Further, even with my limited knowledge, I know POM doesn't use backtrack, recursion and trial-and-error.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Wolfgang » Tue Feb 07, 2006 10:15 am

aeb wrote:Hmm. It seems that I do not need Nishio that often (only once for the first 25 puzzles). Let me show the start of the first one.

(1,1)2 > (8,1)3 > (8,7)8 > (4,7)3 > (9,7)1 > (7,9)!1 > (7,2)1 > (3,2)2 > (1,1)!2

(1,[23])2 > (3,2)1 > (2,1)!1 > (9,1)1 > (9,7)!1 > (4,7)1 > (4,8)3 > (7,8)!3 > (7,3)3 > (3,3)2 > (1,[23])!2

etc.

There *is* no nishio and this does not give a number directly, so etc. what ?
Wolfgang
 
Posts: 208
Joined: 22 June 2005

puzzle #1

Postby maria45 » Tue Feb 07, 2006 10:43 am

Hello tso,

(On the other, other hand -- this doesn't move the puzzle forward much.)
Sure. Twas just a quick hack and proof of principle. Do you want a complete solution?
maria45
 
Posts: 54
Joined: 23 October 2005

PreviousNext

Return to Advanced solving techniques