Forcing Chain Problem

Post the puzzle or solving technique that's causing you trouble and someone will help

Forcing Chain Problem

Postby hobiwan » Fri Apr 25, 2008 7:25 am

I am still struggeling with the concept of Forcing chains. I picked a random example from SudoCue and got the following (which is actually a net and not a chain, but that's not the point here):
Code: Select all
.---------------------.---------------------.---------------------.
| 1256   12     1258  | 1368   7      1236  | 9      4      1236  |
| 126    7      1248  | 1368   9      12346 | 2368   136    5     |
| 3      1249   1489  | 168    124    5     | 268    7      126   |
:---------------------+---------------------+---------------------:
| 259    8      7     | 4      235    2369  | 1      3569   2369  |
| 4      6      3     | 159    8      129   | 257    59     279   |
| 1259   129    1259  | 3569   235    7     | 3456   8      3469  |
:---------------------+---------------------+---------------------:
| 8      12349  1246  | 7      1345   1349  | 456    1569   1469  |
| 7      1349   146   | 1359   1345   1349  | 456    2      8     |
| 19     5      149   | 2      6      8     | 347    139    13479 |
'---------------------'---------------------'---------------------'
Placing digit 1 in R8C2 eliminates all candidates for R8C7
R8C2=1 => R6C2<>1 => R6C2=9 => R4C1<>9 => R4C1=5 => R4C5<>5 => R4C5=3 => R8C5<>3 => R8C5=4 => R8C7<>4
R8C2=1 => R6C2<>1 => R6C2=9 => R4C1<>9 => R4C1=5 => R4C5<>5 => R4C5=3 => R8C5<>3 => R8C5=4 => R8C7<>4 => R8C7=5 => R5C7<>5 => R5C8=5 => R7C8<>5 => R7C7=5 => R8C7<>5
R8C2=1 => R8C2<>3 => R7C2=3 => R7C2<>2 => R7C3=2 => R7C3<>6 => R8C3=6 => R8C7<>6


I am stuck with the first chain:

R8C2=1 => R6C2<>1 => R6C2=9
I understand that because of R8C2=2 => R1C2<>1 => R1C2=2 => R6C2<>2

The next step (R4C1<>9) is clear too. But how do you get from R4C1<>9 to R4C1=5? For that you had to eliminate 2 from R4C1 and I can't see how.

Any ideas?
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby eleven » Fri Apr 25, 2008 8:44 am

I never installed this SudoCue program, because i dont like to be seen by the microsoft server:)

I agree, that something must be missing in the chains as you pointed out with "R6C2<>1 => R6C2=9", which cant be seen without cell r1c2.
For me it would need a long chain of singles (which depend on one another) to get to r4c1<>2 (after r4c6=2) - or a trick i cant see. But r8c7 is already empty then, so this does not make sense also.
So i dont think, that it is worth to study these chains.

And this puzzle is too hard for me to be fun:(
eleven
 
Posts: 1536
Joined: 10 February 2008

Postby daj95376 » Fri Apr 25, 2008 1:22 pm

The elimination is correct, but the chains appear to be rubbish. Or, at best, incomplete.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Sat Apr 26, 2008 3:11 pm

Thank's for your answers. Seems like I have to look elsewhere for test cases...

eleven wrote:I never installed this SudoCue program, because i dont like to be seen by the microsoft server:)


To "be seen" it's enough to have the .NET framework installed, which you probably have if you run one of the newer version of windows. Installing SudoCue itself won't change anything with that. And IMO SudoCue is one of the best GUI solvers/creators I have seen so far.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Draco » Sat Apr 26, 2008 11:35 pm

Hobiwan,

I have a brute-force forcing chain/net finder that works from all possible b/b locations; it operates by following the impact of singles (in parallel) as they ripple through the puzzle. Except for bugs I may not have found and fixed yet:) , it is relentless insofar as finding chains or nets originating from any b/b square that will eliminate even one value from a puzzle.

It finds nothing in the puzzle you posted.

It will not find chains that originate from non b/b squares or those that require more logic than following the outward flow of singles, so if that is what the SodoCue is doing, can't help you there. I think Sudoku Susser also handles forcing chains if you want another "opinion".

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Sat Apr 26, 2008 11:55 pm

hobiwan: Since you seem to be interested in forcing chains/nets, you might compare your results to the following.

Code: Select all
+-----------------------------------------------------------------------------+
|  1256    12      1258   |  1368    7       1236   |  9       4       1236   |
|  126     7       1248   |  1368    9       12346  |  2368    136     5      |
|  3       1249    1489   |  168     124     5      |  268     7       126    |
|-------------------------+-------------------------+-------------------------|
|  259     8       7      |  4       235     2369   |  1       3569    2369   |
|  4       6       3      |  159     8       129    |  257     59      279    |
|  1259    129     1259   |  3569    235     7      |  3456    8       3469   |
|-------------------------+-------------------------+-------------------------|
|  8       12349   1246   |  7       145-3  *1349*  |  456     1569    1469   |
|  7       349-1   146    |  1359    1345    1349   |  456     2       8      |
|  19      5       149    |  2       6       8      |  347     139     13479  |
+-----------------------------------------------------------------------------+

r7c5    <> 3 (4) Net -- Contradiction   on [r7c6]
r8c2    <> 1 (4) Net -- Contradiction   on [r7c6]


===== ===== ===== ===== =====

[Edit: withdrew chain. It was wrong in more ways than one. Sorry!!!]
Last edited by daj95376 on Wed Apr 30, 2008 12:55 am, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Draco » Sun Apr 27, 2008 3:00 am

Danny, if you meant that for my solver... can't do it with the current implementation. I zero in on bi-values only (either squares with two numbers or two links in a color chain). My solver gets no traction with the beast you posted.

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Postby daj95376 » Sun Apr 27, 2008 4:41 am

Draco wrote:Danny, if you meant that for my solver... can't do it with the current implementation.

Sorry Draco, my comment was aimed at hobiwan and his original PM.

FWIW, the pair 45 was a shortcut. My solver took the long way of using Naked/Hidden Singles. I still need to implement grouped and n-tuple eliminations.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Sun Apr 27, 2008 6:56 am

daj95376, thanks for the nice example. My solver does not find it yet, but it will:D
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Sun Apr 27, 2008 12:47 pm

daj95376 wrote:How about a chain as an alternate? In almost NL notation: (I had to break it into segments)

Code: Select all
[r2c7]-6-[r78c7]-45-[r6c7]-3- [r6c7]=4=[r6c9] [r6c9]=6=[r6c4]-6-[r3c4]=6=[r3c78]~6~[r2c7]

Nice chain with ALSs for 2 of the 3 strong inferences. Tersely:
Code: Select all
r2c7 -6- als:r678c7 -3- als:r6c12345 -6- r3c4 =6= r3c79 -6- r2c7  ==> r2c7<>6


With all the nitty-gritty details:
Code: Select all
 1256  12    1258  | 1368  7     1236  | 9     4     1236
 126   7     1248  | 1368  9     12346 | 238-6 136   5
 3     1249  1489  |C168   124   5     |C268   7    C126
-------------------+-------------------+------------------
 259   8     7     | 4     235   2369  | 1     3569  2369
 4     6     3     | 159   8     129   | 257   59    279
B1259 B129  B1259  |B3569 B235   7     |A3456  8     3469
-------------------+-------------------+------------------
 8     12349 1246  | 7     1345  1349  |A456   1569  1469
 7     1349  146   | 1359  1345  1349  |A456   2     8
 19    5     149   | 2     6     8     | 347   139   13479

                        A                                 B                      C
r2c7 -6- als:(r678c7 =6|45|3= r6c7) -3- als:(r6c12345 =3|1259|6= r6c4) -6- r3c4 =6= r3c79 -6- r2c7
  ==> r2c7<>6

daj95376, hobiwan, Draco -- When you're ready, I'd like to see you post some pseudo-code for your chain search algorithms on the Programmers' Forums.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby hobiwan » Sun Apr 27, 2008 5:13 pm

ronk thanks! Although grouped links (including ALS) are definitely on my wish list it will take some time (I am happy if I manage to spend 2 or 3 hours a week with my solver these days).
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Sun Apr 27, 2008 6:28 pm

[edit: Deleted solution path for a puzzle that wasn't even discussed here.]
Last edited by ronk on Mon Apr 28, 2008 9:41 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Sun Apr 27, 2008 7:50 pm

ronk wrote:
daj95376 wrote:How about a chain as an alternate? In almost NL notation: (I had to break it into segments)

Code: Select all
[r2c7]-6-[r78c7]-45-[r6c7]-3- [r6c7]=4=[r6c9] [r6c9]=6=[r6c4]-6-[r3c4]=6=[r3c78]~6~[r2c7]

Nice chain with ALSs for 2 of the 3 strong inferences. Tersely:
Code: Select all
r2c7 -6- als:r678c7 -3- als:r6c12345 -6- r3c4 =6= r3c79 -6- r2c7  ==> r2c7<>6

daj95376, hobiwan, Draco -- When you're ready, I'd like to see you post some pseudo-code for your chain search algorithms on the Programmers' Forums.

Thanks ronk, but if my broken segments can only be expressed as an ALS-something, then I'll find a workaround.

As for my chain module, I'm still in development Phase I where I'm only working with Naked/Hidden Singles. I just managed to overcome a major hurdle in maintaining a consistent flow in the chain. As for my logic, I take an unorthodox approach where I follow a chain in search of a contradiction. Then, I try to convert the chain and contradiction to NL notation. I don't always succeed because I have trouble using NL notation to describe some sequences of steps -- like those listed above.

Here is a PM that I listed recently ... along with the (edited) output from my new solver as I stepped through the puzzle.

Code: Select all
 +-----------------------------------------------------------------------+
 |  2      3468   368    |  346    1      5      |  7      38     9      |
 |  14     13478  378    |  3479   38     34789  |  5      2      6      |
 |  5      3678   9      |  367    2      378    |  18     138    4      |
 |-----------------------+-----------------------+-----------------------|
 |  7      389    358    |  34     35     1      |  489    6      2      |
 |  6      45     2      |  8      9      47     |  3      457    1      |
 |  34     389    1      |  2357   6      247    |  89     5789   578    |
 |-----------------------+-----------------------+-----------------------|
 |  9      237    357    |  1      4      238    |  6      578    578    |
 |  13     2367   3567   |  239    358    2389   |  149    149    578    |
 |  8      15     4      |  59     7      6      |  2      19     3      |
 +-----------------------------------------------------------------------+

Code: Select all
  3r8c5  5r9c4         [b7]~1   (not necessary)

  3r8c4  2r6c4  5r9c4  [b7]~1

  3r1c4  4r4c4  7r5c6  [b2]~8
  3r2c4  4r4c4  7r5c6  [b2]~8
  3r3c4  4r4c4  7r5c6  [b2]~8

  SSTS

  6r1c3  3r4c3         [c4]~4

  SSTS

  3r3c2  6r3c4  7r6c4  [r6]~3

  SSTS

hobiwan: My apologies for side-tracking your thread!!!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Sun Apr 27, 2008 8:02 pm

daj95376 wrote:hobiwan: My apologies for side-tracking your thread!!!

No problem.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby ronk » Tue Apr 29, 2008 10:13 pm

daj95376 wrote:if my broken segments can only be expressed as an ALS-something, then I'll find a workaround.

As for my chain module, I'm still in development Phase I where I'm only working with Naked/Hidden Singles.

ALSs appearing simply means the singles are due to multiple inferences instead of a single inference ... as for the following:
daj95376 wrote:3r1c4 4r4c4 7r5c6 [b2]~8
3r2c4 4r4c4 7r5c6 [b2]~8
3r3c4 4r4c4 7r5c6 [b2]~8
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Help with puzzles and solving techniques