How to solve this one? Forcing Chains?

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

How to solve this one? Forcing Chains?

Postby bradles » Fri Feb 24, 2006 1:42 am

Hi All,

I am using simple sudoku to try and solve this puzzle. I have got to "No Hint available" and am wondering how this next step can be solved. What technique can be used to advance this puzzle to the next step?

Code: Select all
 *--------------------------------------------------*
 | 9    6    2    | 5    4    3    | 7    8    1    |
 | 3    8    4    | 2    17   17   | 9    5    6    |
 | 17   17   5    | 8    6    9    | 23   4    23   |
 |----------------+----------------+----------------|
 | 5    179  8    | 6    279  247  | 14   3    47   |
 | 47   79   3    | 1    8    5    | 6    29   247  |
 | 147  2    6    | 3    79   47   | 5    19   8    |
 |----------------+----------------+----------------|
 | 8    5    9    | 7    12   12   | 34   6    34   |
 | 2    3    1    | 4    5    6    | 8    7    9    |
 | 6    4    7    | 9    3    8    | 12   12   5    |
 *--------------------------------------------------*

Brad
bradles
 
Posts: 23
Joined: 21 February 2006

Postby tarek » Fri Feb 24, 2006 1:54 am

Possible next steps:

Code: Select all
*-----------------------------------------------*
| 9    6    2   | 5    4    3   | 7    8    1   |
| 3    8    4   | 2    17   17  | 9    5    6   |
| 17   17   5   | 8    6    9   | 23   4    23  |
|---------------+---------------+---------------|
| 5    179  8   | 6    279 -247 |^14   3    47  |
| 47   79   3   | 1    8    5   | 6    29   247 |
| 147  2    6   | 3   *79  *47  | 5   ^19   8   |
|---------------+---------------+---------------|
| 8    5    9   | 7    12   12  | 34   6    34  |
| 2    3    1   | 4    5    6   | 8    7    9   |
| 6    4    7   | 9    3    8   | 12   12   5   |
*-----------------------------------------------*
Eliminating 4 from r4c6(ALS-XZ A=479 in r6c5, r6c6 B=149 in r4c7, r6c8  x=9 z=4)
*-----------------------------------------------*
| 9    6    2   | 5    4    3   | 7    8    1   |
| 3    8    4   | 2    17   17  | 9    5    6   |
| 17   17   5   | 8    6    9   | 23   4    23  |
|---------------+---------------+---------------|
| 5    179  8   | 6    279  27  | 14   3    47  |
| 4    79   3   | 1    8    5   | 6    29   27  |
| 17   2    6   | 3    79   4   | 5    19   8   |
|---------------+---------------+---------------|
| 8    5    9   | 7    12   12  | 34   6    34  |
| 2    3    1   | 4    5    6   | 8    7    9   |
| 6    4    7   | 9    3    8   | 12   12   5   |
*-----------------------------------------------*
Eliminating 9 From r5c8 (1 & 7 in r6c1 form an XY wing with 9 in r6c8 & r5c2)


Tarek
User avatar
tarek
 
Posts: 2644
Joined: 05 January 2006

Postby bradles » Fri Feb 24, 2006 2:08 am

I lost you on the notation Tarek.
Eliminating 4 from r4c6(ALS-XZ A=479 in r6c5, r6c6 B=149 in r4c7, r6c8 x=9 z=4)

bradles
 
Posts: 23
Joined: 21 February 2006

Postby tarek » Fri Feb 24, 2006 2:15 am

Forgive me,

ALS -XZ stands for Almost Locked sets XZ rule, it is a generalisation of the XYZ wing technique, A & B are almost locked sets, x is the common sector candidate & z is the common candidate.

A search through the forums will guide you through examples of this rule....

Tarek
User avatar
tarek
 
Posts: 2644
Joined: 05 January 2006

Postby ronk » Fri Feb 24, 2006 2:50 am

tarek wrote:Eliminating 4 from r4c6(ALS-XZ A=479 in r6c5, r6c6 B=149 in r4c7, r6c8 x=9 z=4)

Hi tarek, I've noticed you've been recently posting solving steps using bennys' xz-rule.

There are three different patterns I'm aware of:
  1. x constrained to rows and z constrained to boxes,
  2. x constrained to boxes and z constrained to rows, and
  3. x constrained to rows and z constrained to columns.
Have you implemented all of these?

For each of the above, there are different size pairings for ALS1 and ALS2. Counting cells (rather than candidates) and including degenerative sets (naked pairs, xy-wing, etc.), I mean pairings like
  1. 1-1, 1-2, 1-3, 1-4, ... etc.
  2. 2-1, 2-2, 2-3, 2.4, ... etc.
  3. 3-1, 3-2, 3-3, ... etc.
  4. etc.
Where did you "draw the line" on these combinations?

Did you found an efficient algorithm for the above combinations that you would care to share? (I guess that should occur in a different thread, or even different topic or forum.)

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

Postby emm » Fri Feb 24, 2006 7:55 am

Hi Brad - here's another way

If r5c1=7 => r5c2=9 => r5c8=2
Code: Select all
*--------------------------------------------------*
 | 9    6    2    | 5    4    3    | 7    8    1    |
 | 3    8    4    | 2    17   17   | 9    5    6    |
 | 17   17   5    | 8    6    9    | 23   4    23   |
 |----------------+----------------+----------------|
 | 5    179  8    | 6    279  247  | 14   3    47   |
 | 47*  79*  3    | 1    8    5    | 6    29*  247  |
 | 147  2    6    | 3    79   47   | 5    19   8    |
 |----------------+----------------+----------------|
 | 8    5    9    | 7    12   12   | 34   6    34   |
 | 2    3    1    | 4    5    6    | 8    7    9    |
 | 6    4    7    | 9    3    8    | 12   12   5    |
 *--------------------------------------------------*

If r5c1=4 => XY wing marked * which eliminates 9 from r5c8 => r5c8=2

Code: Select all
*--------------------------------------------------*
 | 9    6    2    | 5    4    3    | 7    8    1    |
 | 3    8    4    | 2    17   17   | 9    5    6    |
 | 17   17   5    | 8    6    9    | 23   4    23   |
 |----------------+----------------+----------------|
 | 5    179  8    | 6    279  247  | 14   3    47   |
 | 4    79*  3    | 1    8    5    | 6    29   247  |
 | 17*  2    6    | 3    79   47   | 5    19*  8    |
 |----------------+----------------+----------------|
 | 8    5    9    | 7    12   12   | 34   6    34   |
 | 2    3    1    | 4    5    6    | 8    7    9    |
 | 6    4    7    | 9    3    8    | 12   12   5    |
 *--------------------------------------------------*


With 2 at r5c8 the puzzle is solved by singles
emm
 
Posts: 987
Joined: 02 July 2005

Postby Carcul » Fri Feb 24, 2006 10:15 am

Hi Brad.

Brad wrote:What technique can be used to advance this puzzle to the next step?


The following nice loop:

[r4c2]-1-[r3c2]-7-[r5c2]-9-[r5c8]-2-[r9c8]=2=[r9c7]=1=[r4c7]-1-[r4c2], => r4c2<>1 which solve the puzzle.

This same deduction could be made in a more complicated way, by making use of the Almost Almost Unique Pattern in cells r5c1/r6c1/r4c6/r6c6/r4c9/r5c9:

[r4c2](-1-[r3c2]-7-[r5c2]-9-[r5c8]-2-[r5c9])(-1-[r4c7])-1-[r6c1]=1|2=[r4c6]-2-[r7c6]-1-[r2c6]-7-[r6c6]-4-[r6c1]=4=[r5c1]-4-[r5c9]-7-[r4c9]

which implies that, if r4c2=1 then we would end up with two "4s" in row 4 (in r4c7 and r4c9). So, r4c2<>1.

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

Postby tarek » Fri Feb 24, 2006 10:19 am

ronk wrote:Hi tarek, I've noticed you've been recently posting solving steps using bennys' xz-rule.

True
ronk wrote:There are three different patterns I'm aware of:
  1. x constrained to rows and z constrained to boxes,
  2. x constrained to boxes and z constrained to rows, and
  3. x constrained to rows and z constrained to columns.
Have you implemented all of these?

I wasn't aware that x & z must be in different sectors, basically the patterns encountered are described by:
x constrained to sector and z constrained to sector
Possibilities are then 3+2+1=6 & swapping x & z +3=9; I haven't checked if these do actually occur.... but my solver does search for these
ronk wrote:For each of the above, there are different size pairings for ALS1 and ALS2. Counting cells (rather than candidates) and including degenerative sets (naked pairs, xy-wing, etc.), I mean pairings like
  1. 1-1, 1-2, 1-3, 1-4, ... etc.
  2. 2-1, 2-2, 2-3, 2.4, ... etc.
  3. 3-1, 3-2, 3-3, ... etc.
  4. etc.
Where did you "draw the line" on these combinations?

Yes, at 6-6.... as there are many 6s, including 7s should provide some help in some puzzles.

ronk wrote:Did you found an efficient algorithm for the above combinations that you would care to share? (I guess that should occur in a different thread, or even different topic or forum.)

I didn't find an efficient way yet to do it, however this is the best of trying to do it:
I look for Set A=3 to 6
I look for Set B=2 to A
skip Bs that don't have 2 common candidates with A
Skip Bs that don't follow the XZ rule

I think the topic of efficiency merits a new thread, I'm not sure where though !!??

Tarek
User avatar
tarek
 
Posts: 2644
Joined: 05 January 2006

Postby bradles » Fri Feb 24, 2006 11:52 am

Carcul wrote:[r4c2]-1-[r3c2]-7-[r5c2]-9-[r5c8]-2-[r9c8]=2=[r9c7]=1=[r4c7]-1-[r4c2], => r4c2<>1 which solve the puzzle.

I think I should go and smash my head into a brick wall or something because this still doesn't make sense to me - no offense intended.

I don't understand the notation "-" and "=".
I get lost at [r9c7]=1=[r4c7]-1-[r4c2], => r4c2<>1

Brad
bradles
 
Posts: 23
Joined: 21 February 2006

Postby ravel » Fri Feb 24, 2006 12:44 pm

bradles wrote:I don't understand the notation "-" and "=".
I get lost at [r9c7]=1=[r4c7]-1-[r4c2], => r4c2<>1
Brad

Carcul, please correct me, if i am wrong:
I think, it says that if r9c8 is not 2 (must be 1),r9c7 is not 1, then r4c7 is 1 and r4c2 cannot be 1.
Alternatively it could say:
[r4c2]-1-[r3c2]-7-[r5c2]-9-[r5c8]-2-[r9c8]-1-[r9c7]-2-[r4c7]-1-[r4c2]
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ravel » Fri Feb 24, 2006 1:04 pm

Hm, no, r4c7=1 does not follow directly from r9c7=2, but from r9c7<>1 (conjugated pair), so better
[r4c2]-1-[r3c2]-7-[r5c2]-9-[r5c8]-2-[r9c8]-1-[r9c7]=1=[r4c7]-1-[r4c2]
ravel
 
Posts: 998
Joined: 21 February 2006

Postby emm » Fri Feb 24, 2006 7:18 pm

It's confusing because the (=) sign is used differently in different situations.

With chains where you indicate the progression by arrows => the trend seems to be to use (=) to mean 'if this is so' and (<>) to mean 'then that is not so'.

The loop above could be written as a chain
r4c2=1 => r3c2=7 => r5c2=9 => r5c8=2 => r9c8<>2 => r9c8=1 => r9c7<>1 => r4c7=1
This is a contradiction since r4c2 and r4c7 cannot both = 1

With loops the links are indicated by
(-) meaning a weak inference or "if candidate 'x' in the preceding node is true, then candidate 'x' in the following node is false" and
(=) meaning a strong inference or "if candidate 'x' in the preceding node is false, then candidate 'x' in the following node is true".

In other words it looks like an 'equals' sign but actually it's the opposite. Confused? Me too. For everything on chains and loops read this thead.
emm
 
Posts: 987
Joined: 02 July 2005


Return to Help with puzzles and solving techniques