The New Sudoku Players' Forum

[Lunatic]

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 ?

[tarek]

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

[Lunatic]

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.

[ab]

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

[daj95376]

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.

[ronk]

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]

[udosuk]

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.


BTW there is a typo in ronk's loop:

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

[daj95376]

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]

[hobiwan]

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...

[Lunatic]

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).

[udosuk]

... 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.

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.

[Lunatic]

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...

[Lunatic]

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.

[ronk]

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.

[champagne]

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.