Is this just a forcing chain or something else ?

Advanced methods and approaches for solving Sudoku puzzles

Is this just a forcing chain or something else ?

Postby Lunatic » Wed Jun 04, 2008 10:16 pm

Code: Select all
7...6.24.
8.4......
..9.34..8
..2....9.
...9.18..
98....4..
24.61.3..
1.....6.5
..3.8...4

+----------------------+----------------------+----------------------+
| 7      135    15     | 158    6      589    | 2      4      139    |
| 8      12356  4      | 1257   2579   257    | 1579   13567  1367   |
| 56     1256   9      | 1257   3      4      | 157    1567   8      |
+----------------------+----------------------+----------------------+
| 34     157    2      | 34578  457    35678  | 157    9      1367   |
| 34     57     567    | 9      2457   1      | 8      3567   2367   |
| 9      8      1567   | 2357   257    23567  | 4      13567  12367  |
+----------------------+----------------------+----------------------+
| 2      4     *578    | 6      1     *579    | 3      78     79     |
| 1     *79    *78     | 2347  *2479   237    | 6      278    5      |
| 56     5679   3      | 257    8      257    | 179    127    4      |
+----------------------+----------------------+----------------------+


5 @ r7 locked @ r7c36
9 @ r8 locked @ r8c25
9 @ b8 locked @ r7c6 r8c5
578 @ c3 ALS @ r78c3
789 @ r8 ALS @ r8c23

If r7c6=5 then 78 @ c3 locked @ r78c3
If r7c6=5 then r8c5=9 then 78 @ r8 locked @ r8c23
78 cannot be locked in two different sets in that same box
therefore r7c6<>5 therefore r7c3 must be 5

I tried both ALS and AIC to implement or a mixture of those two, but i can't figure it out, so it's probably a forcing chain, is it ?
Marc
~~~<><~~~<><~~~<><~~~<><~~~
The Lunatic is on the grass...
...under the sun everything is in tune,
but the sun is eclipsed by the moon...
User avatar
Lunatic
2015 Supporter
 
Posts: 20
Joined: 19 April 2008
Location: Ghent - Belgium

Re: Is this just a forcing chain or something else ?

Postby tarek » Wed Jun 04, 2008 11:01 pm

Lunatic wrote:If r7c6=5 then r8c5=9 then 78 @ r8 locked @ r8c23

Hi Lunatic & welcome to the Players' Forums,

Could you check the above statement with the PM grid you supplied ?

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

Postby Lunatic » Wed Jun 04, 2008 11:42 pm

Do you mean that i use the wrong syntax ?

Placing 5 @ r7c6 forces 9 @ r8c5,
so value 5 @ r7c6 extracts 5 from the ALS @ r78c3 there leaving 78 locked,
and value 9 @ r8c5 extracts 9 from the ALS @ r8c23 there leaving 78 locked too,
which is impossible.

There are other ways to discribe that r7c6 cannot be 5:

If we consider 5789 as ALS in the lower left box (b7) @ r7c3 r8c2 r8c3 then placing 5 @ r7c6 forces 9 @ r8c5, so value 5 @ r7c6 and value 9 @ r8c5 extracts 2 values from that locked sets, also impossible.

Or, if r7c6=5 then 78 will be locked in c3 @ r78c3, which forces 9 @ r8c2 leaving the middle lower box (b8) without placement for value 9.

Or, if r7c6=5 => r8c5=9 => r8c2=7 => r8c3=8 then r7c3 will be an empty cell.
Marc
~~~<><~~~<><~~~<><~~~<><~~~
The Lunatic is on the grass...
...under the sun everything is in tune,
but the sun is eclipsed by the moon...
User avatar
Lunatic
2015 Supporter
 
Posts: 20
Joined: 19 April 2008
Location: Ghent - Belgium

Postby ab » Thu Jun 05, 2008 12:02 am

here's a nice loops version of why r7c3=5
if r8c2=9 then r8c5<>9 so r2c5=9 so r2c7<>9 so r7c9=7 and r7c8=8 therefore r7c3<>7,8
Alternatively r8c2=7 so r8c3=8 therefore r7c3<>7,8
ab
 
Posts: 451
Joined: 06 September 2005

Postby daj95376 » Thu Jun 05, 2008 12:21 am

Lunatic: tarek was too subtle in trying to tell you that there isn't an 8 in r8c2, so you can't lock 78 into r8c23.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Thu Jun 05, 2008 2:42 am

ab wrote:here's a nice loops version of why r7c3=5
if r8c2=9 then r8c5<>9 so r2c5=9 so r2c7<>9 so r7c9=7 and r7c8=8 therefore r7c3<>7,8
Alternatively r8c2=7 so r8c3=8 therefore r7c3<>7,8

Without nice loop notation, IMO there is no "nice loop."

ALS:(r7c3 =5|7= r78c3) -7- r8c2 -9- r8c5 =9= r7c6 =5= r7c3 ==> r7c3=5

[edit: corrected typo noted by udosuk]
Last edited by ronk on Thu Jun 05, 2008 6:31 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Is this just a forcing chain or something else ?

Postby udosuk » Thu Jun 05, 2008 5:08 am

Lunatic wrote:
Code: Select all
+----------------------+----------------------+----------------------+
| 7      135    15     | 158    6      589    | 2      4      139    |
| 8      12356  4      | 1257   2579   257    | 1579   13567  1367   |
| 56     1256   9      | 1257   3      4      | 157    1567   8      |
+----------------------+----------------------+----------------------+
| 34     157    2      | 34578  457    35678  | 157    9      1367   |
| 34     57     567    | 9      2457   1      | 8      3567   2367   |
| 9      8      1567   | 2357   257    23567  | 4      13567  12367  |
+----------------------+----------------------+----------------------+
| 2      4     *578    | 6      1     -579    | 3      78     79     |
| 1     *79    *78     |#2347  #2479  #237    | 6      278    5      |
|-56    -5679   3      |#257    8     #257    | 179    127    4      |
+----------------------+----------------------+----------------------+

Here is an ALS-xz for you:

ALS A: r7c3+r8c23={5789}
ALS B: r8c456+r9c46={234579}
restricted common: x=9 (r8c25)
common: z=5 (r7c3+r9c46)

Hence r7c6+r9c12, seeing r7c3+r9c46, can't have 5.:idea:


BTW there is a typo in ronk's loop:
ALS:(r7c3 =5|7= r78c3) -7- r8c2 -9- r8c5 =9= r7c6 =5= r7c2 ==> r7c3=5

:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby daj95376 » Thu Jun 05, 2008 5:51 am

ab wrote:here's a nice loops version of why r7c3=5
if r8c2=9 then r8c5<>9 so r2c5=9 so r2c7<>9 so r9c7=9 so r7c9=7 and r7c8=8 therefore r7c3<>7,8
Alternatively r8c2=7 so r8c3=8 therefore r7c3<>7,8

I believe you omitted a step. Also, I thought a loop started and ended in the same cell. This looks more like a forcing network to me.

[Edit: changed chain to network]
Last edited by daj95376 on Thu Jun 05, 2008 8:44 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Thu Jun 05, 2008 10:02 am

I tried to reproduce the chain using only singles (because that's all I can do for now) but I had to use multiple chains to get a result, e.g.:

Forcing Chain Contradiction in r7c3 => r7c6<>5
r7c6=5 r7c3<>5
r7c6=5 r8c5=9 r8c2=7 r7c3<>7
r7c6=5 r8c5=9 r8c2=7 r8c3=8 r7c3<>8

To do it in one step with singles I needed a net:

Forcing Net Contradiction in r7c9 => r7c3=5
r7c3<>5 r7c6=5 r8c5=9 r8c2=7 (r7c3<>7) r8c3=8 r7c3=5

Looks like I am not done with chains and nets yet...
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Lunatic » Thu Jun 05, 2008 12:02 pm

daj95376 wrote:Lunatic: tarek was too subtle in trying to tell you that there isn't an 8 in r8c2, so you can't lock 78 into r8c23.


I knew that, in fact it solves that ALS, but i was thinking from a programmers view (for my own solver). Value 5 @ r7c6 forces 9 @ r8c5, both claiming the not-common values of both ALS's who share the same house AND share at least one cell. I'm interested in the pattern, if any, and i'm not keen on forcing chains (yet).
Marc
~~~<><~~~<><~~~<><~~~<><~~~
The Lunatic is on the grass...
...under the sun everything is in tune,
but the sun is eclipsed by the moon...
User avatar
Lunatic
2015 Supporter
 
Posts: 20
Joined: 19 April 2008
Location: Ghent - Belgium

Postby udosuk » Thu Jun 05, 2008 1:37 pm

Lunatic wrote:... i was thinking from a programmers view (for my own solver).

In that case I think your solver need to be taught better to recognise that ALS-xz I shown above. I think generally if you can find a forcing chain like that, there must be an accompanying ALS-xz move which might include a few more cells.:idea:

Note whenever you find a strong link within a group, you can probably get an almost locked set by taking the whole group excluding one of the end cells of that strong link.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Lunatic » Thu Jun 05, 2008 3:33 pm

udosuk wrote:In that case I think your solver need to be taught better to recognise that ALS-xz I shown above.


Well, my solver doesn't yet handle ALS's, nor AIC, nor Forcing Chains. I found that 'contradiction' by hand. I was looking at different solving techniques to take my solver to the next level, trying to spot ALS, AIC, POM, BUG, by hand on some sudokus my solver can't handle, but to little or no avail. IMHO, forcing chains smells a bit like trial and error, and i'm trying to avoid that (knowing that i will have to deal with forcing chains sooner or later). Anyway, thanks for the ALS-xz, it's not easy to spot this manually, one has to have a lot of experience.

Here it is once again, in full color...
Image
Marc
~~~<><~~~<><~~~<><~~~<><~~~
The Lunatic is on the grass...
...under the sun everything is in tune,
but the sun is eclipsed by the moon...
User avatar
Lunatic
2015 Supporter
 
Posts: 20
Joined: 19 April 2008
Location: Ghent - Belgium

Postby Lunatic » Wed Jun 11, 2008 6:14 pm

Ok, I decided to take my solver to the next level, implementing a lookup routine for ALS-xz.

At first I was thinking to collect all possible ALSs on the grid, and then to handle all possible pairs of ALSs looking for possible common restricted candidates, and if found one then looking for a non restricted common candidate that could lead to eliminations. Sounds good in theory, but i think i will end up with a huge amount of ALSs to collect and compare, mostly leading to nothing and wasting time. So, i need a different approach. I searched the "programming sudoku" forum but to no avail.

Thinking it over, i came to the conclusion to look for possible restricted common candidates first, and then lookup if i could place them in ALSs, and if so, look for a non-restricted common candidate that leads to eliminations. How about this ? If anyone knows a better approach, please let me know...

Just a few quick thoughts...
- Could it be that any naked subset in its whole is not useful as part of an ALS ?
- I think that mixing parts of two naked subsets together for making a single ALS is not very useful either. Which would mean that any useable ALS is a subset from a naked subset (or from the whole set if no subsets are present)

Can anyone confirm this ?

I asked the same questions at the programmers forum, but didn't got much replies...

Tnx,
Marc.
Marc
~~~<><~~~<><~~~<><~~~<><~~~
The Lunatic is on the grass...
...under the sun everything is in tune,
but the sun is eclipsed by the moon...
User avatar
Lunatic
2015 Supporter
 
Posts: 20
Joined: 19 April 2008
Location: Ghent - Belgium

Postby ronk » Wed Jun 11, 2008 7:10 pm

Lunatic wrote:Just a few quick thoughts...
- Could it be that any naked subset in its whole is not useful as part of an ALS ?
- I think that mixing parts of two naked subsets together for making a single ALS is not very useful either. Which would mean that any useable ALS is a subset from a naked subset (or from the whole set if no subsets are present)

Can anyone confirm this ?

I am not aware of proofs, but I believe both statements are correct.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Wed Jun 11, 2008 7:22 pm

Lunatic wrote:Ok, I decided to take my solver to the next level, implementing a lookup routine for ALS-xz.

At first I was thinking to collect all possible ALSs on the grid, and then to handle all possible pairs of ALSs looking for possible common restricted candidates, and if found one then looking for a non restricted common candidate that could lead to eliminations. Sounds good in theory, but i think i will end up with a huge amount of ALSs to collect and compare, mostly leading to nothing and wasting time. So, i need a different approach. I searched the "programming sudoku" forum but to no avail.

Thinking it over, i came to the conclusion to look for possible restricted common candidates first, and then lookup if i could place them in ALSs, and if so, look for a non-restricted common candidate that leads to eliminations. How about this ? If anyone knows a better approach, please let me know...

.


I worked at the beginning on ALS pairs. I quickly gave up. Instead, I used AHS/AC, working as almost cells. It's much easier to handle, you have not to consider couples of ALS (n2 dimension) and you get the same result.

I am doing it in a tagging context reducing the overall dimension, but the same technic can be applied without tagging.
champagne
2017 Supporter
 
Posts: 7465
Joined: 02 August 2007
Location: France Brittany


Return to Advanced solving techniques