Multivalue X-Wing Strategy

Advanced methods and approaches for solving Sudoku puzzles

Multivalue X-Wing Strategy

Postby AndrewStuart » Sat Sep 16, 2006 7:26 pm

While not quite up in the stratosphere as some recent strategies posted here, I think this is useful for pencil and paper solvers and it does seem to fit into the pantheon, hense the name Multivalue X-Wing Strategy. It uses the exact formation of X-Wings solvers are familiar with so it's easy to spot but two different candiate numbers can be eliminated at the same time. Its possible to express this strategy in terms of nice loops, but I'll leave that to the reader.

Taking a look at the rectangular formation in the first diagram made from the yellow and brown cells. Connecting the two yellow cells is a conjugate pair of 6, the only two sixes in the row. In the other row connecting the two brown cells is a conjugate pair of 5. What connects the cells in the columns are the additional candidates, in this case 1 in column 1 and 9 in column 9. Note that there are additional 1's and 9's in these columns. These are the candidates we can eliminate and they are highighted in green cells.

Image

The logic goes as follows: 6 must occur in one of the two yellow cells and the 5 must occur in one of the brown cells. No doubt about that. But both 6 and 5 cannot occur in the same column. Lets pretend they do, say 6 and 5 in column 1. That would leave 9 as the only solution in two cells in column 9. Can't have that. So which ever way round 6 is 5 will be in the opposite corner. This forces the 1 and 9 to fill the remaining two corners. If 1 and 9 are guaranteed to be in either a yellow or a brown cell apiece then we can't have any more 1s and 9s in those columns. Hense the eliminations.

Image

The generalised X-Wing theory says that we can have a distorted X-Wing starting from 2 boxes and eliminating in 2 rows or 2 columns. The example above does just that. We have a strong link between the yellow cells (B7 and H7) using 5. And another string link between brown cells (A9 and J9) using 3. Since the top pair share a box and the bottom pair also share a box we don't need exact row alignment.

Using the arguement above we know that one 5 or 3 will occur in B7 or A9 focing the other cell in the top right box to be a 2. We don't know which yet, but of those two cells will be a 2 so all the others in the box can go.

Likewise, a 5 or a 3 will appear one of the cells int the bottom box, H7 or A9. That forces 4 to be the solution to that pair - we just don't know which way round yet. The 4 in H8 can go.
Last edited by AndrewStuart on Sat Sep 16, 2006 6:39 pm, edited 1 time in total.
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Postby ronk » Sat Sep 16, 2006 8:14 pm

In your examples, are you sure the conjugate relationships are required?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Sat Sep 16, 2006 10:22 pm

Essentially, in your first puzzle, any one of four Forcing Chains leads to the same eliminations in <1> and <9>. (Note: I think XY-Chains will suffice as well.)

I assume that you perform this operation before the UR Type (?) in <29> eliminates <9> in [r1c79]?

Because of the possible UR, one of [r1c7]=3 or [r1c9]=5|6 must be true.

Code: Select all
[r1c7]=3             => [r3c8]=9 => [r1c9]<>9
[r1c9]=5 => [r3c7]=3 => [r3c8]=9 => [r1c7]<>9
[r1c9]=6 =>          => [r2c9]=9 => [r1c7]<>9

In each case, the assignment eliminates <9> from one cell and the subsequent assignment(s) remove <9> from the other cell.
Last edited by daj95376 on Sat Sep 16, 2006 6:50 pm, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby AndrewStuart » Sat Sep 16, 2006 10:26 pm

Ronk, certainly yes, unless there is a completely different way to express the logic and make the deductions which is more expansive. An X-Wing needs two conjugate pairs in one dimension to reduce the other dimension to two conjugate pairs after eliminations. So does this. Its the old opposite corner thing - we just don't know which of the two opposite corners. I don't see how you could assert it if the pairs were not conjugate.

I'm trying to think of a snappy rule that expresses it all.
Last edited by AndrewStuart on Sat Sep 16, 2006 6:27 pm, edited 1 time in total.
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Re: Multivalue X-Wing Strategy

Postby gsf » Sat Sep 16, 2006 10:27 pm

would you please post the puzzle and/or pencilmark grid in snarfable [ code ] form?
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby AndrewStuart » Sat Sep 16, 2006 10:32 pm

Sorry, that was an annoying thing not to do.
Code: Select all
400000080005000700200040001700408003040500000900702008800010007002000600030000004
4 . .|. . .|. 8 .
. . 5|. . .|7 . .
2 . .|. 4 .|. . 1
-----+-----+-----
7 . .|4 . 8|. . 3
. 4 .|5 . .|. . .
9 . .|7 . 2|. . 8
-----+-----+-----
8 . .|. 1 .|. . 7
. . 2|. . .|6 . .
. 3 .|. . .|. . 4


058040160400000008003000900040309000300000005000401080004000700200000006095070810

. 5 8|. 4 .|1 6 .
4 . .|. . .|. . 8
. . 3|. . .|9 . .
-----+-----+-----
. 4 .|3 . 9|. . .
3 . .|. . .|. . 5
. . .|4 . 1|. 8 .
-----+-----+-----
. . 4|. . .|7 . .
2 . .|. . .|. . 6
. 9 5|. 7 .|8 1 .


Actually the first one takes a good bit of monkeying around to get to that stage. I chose it for its nice rectangular spaced formation. Most MXWs are not of this type. This is the solved state before the MXW

Code: Select all
4......8...5...74.2...4...1726498153348561.7.9517324688.4.1...7..2..46...3....8.4
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Postby daj95376 » Sat Sep 16, 2006 10:49 pm

AndrewStuart wrote:Actually the first one takes a good bit of monkeying around to get to that stage. I chose it for its nice rectangular spaced formation. Most MXWs are not of this type. This is the solved state before the MXW

Code: Select all
4......8...5...74.2...4...1726498153348561.7.9517324688.4.1...7..2..46...3....8.4

Actually, there are many interesting eliminations that you've performed that don't show up in the pencilmarks for the above grid.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby AndrewStuart » Sat Sep 16, 2006 11:29 pm

Hi daj95376, interesting points about the double XY-chain. I check URs after non-UR strats. Funny how they are going out of style. And, yes the first one was interesting as a puzzle. To get to the MXW I required:
Code: Select all
X-WING (Col->Row) 5 taken off A6, based on CG67
X-WING (Col->Row) 5 taken off J6, based on CG67
X-WING (Col->Row) 5 taken off A7, based on CG67
XYZ-WING 9 taken off C7 - using C8 A7 E7
ALS/ALS: [C8] and [H1|H8|H9], 3 is restricted common, other common candidate 9 can be removed from G8
ALS/ALS: [C8] and [H1|H8|H9], 3 is restricted common, other common cand 9 can be removed from J8
ALS/ALS: [B1|H1] and [B9|E9|H9], 5 is restricted common, other common cand 6 can be removed from B2
ALS/ALS: [B1|H1] and [B9|E9|H9], 5 is restricted common, other common cand 6 can be removed from B4
ALS/ALS: [B1|H1] and [B9|E9|H9], 5 is restricted common, other common cand 6 can be removed from B6
ALS/ALS: [B1|H1] and [B9|E9|H9], 6 is restricted common, other common cand 5 can be removed from H5
ALS/ALS: [C3|C4|C6|C7|C8] and [H1|H2|H4|H8|H9], 8 is restricted common, other common cand 7 can be removed from C2
APE: Col Pair A2 / B2 reduced from 1/6/7/9->1/7/9 and 1/8/9->1/8/9
- PAIR combination 6/9 found in G2
- PAIR combination 6/1 found in B1
- TRIPLE combinations 6/8/9 C2 + 6/9 G2
- TRIPLE combinations 3/7/9 A3 + 3/7/9 C3
AIC Rule 2, on 6 (Alternating Inference Chain, length 6):
1[A4]=1[A2]-1[B1]=6[B1]-6[B9]=6[A9]-
- Chain ends A4 cannot be 6 and A9 cannot be 1
SINGLES CHAIN (Type 1): Removing 6 from G6
AIC Rule 2, on 2 (Alternating Inference Chain, length 8):
1[A4]=1[A2]-7[A2]=7[H2]-7[H5]=8[H5]-8[B5]=2[B5]-
- Chain ends A4 cannot be 2 and B5 cannot be 1
AIC Rule 2, on 2 (Alternating Inference Chain, length 8):
5[A5]=5[A9]-5[H9]=9[H9]-9[E9]=9[E7]-2[E7]=2[A7]-
- Chain ends A5 cannot be 2 and A7 cannot be 5
INTERSECTION REMOVAL PAIR: Between Row=1 and Box=3: 2 taken off B9

Note the double 5 cell ALS. First for me today.
I'll try and do the text/pencil mark output so popular here next example
Last edited by AndrewStuart on Sat Sep 16, 2006 7:34 pm, edited 1 time in total.
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Postby Mike Barker » Sat Sep 16, 2006 11:31 pm

I think Ron and Daj may have important points. The question is: are the eliminations possible because of the strong links or are they possible because of the bivalue cells which form 4-cell XY ring in both cases? In the first case:
Code: Select all
r2c1-6-r2c9-9-r8c9-5-r8c1-1-r2c1

and in the second
Code: Select all
r2c7-2-r1c9-3-r9c9-4-r8c7-5-r2c7

These account for the eliminations. Can the strong links also account for them? As a quick test consider if 2 had not been placed in r3c1, say r3c1=26 in the first example. It is then possible for r2c1 to contain 2. This doesn't impact the strong links, but breaks up the XY ring. Now what happens if r2c9=6 and r8c9=5? r9c1=1, r2c1=2, r9c1=5, and r3c1=6. The implication is that the r9c1 elimination of "1" is no longer assured even though the strong links remain. I'd conclude that it is the XY-ring, not the strong links which make the elimination possible.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby AndrewStuart » Sun Sep 17, 2006 12:01 am

Hi Mike, I think I know what you are implying. Let me try an AIC rule on the first example.
Code: Select all
1[r2c1]=6[r2c1]-6[r2c9]=9[r2c9]-9[r8c9]=5[r8c9]-5[r8c1]=1[r8c1]-1[r2c1]

and round and round. This says if there is no 1 at r2c1 it must be a 6 which imples there is no 6 at r2c9....etc...etc...until 1 is impled at r8c1 which implies there is no 1 at r2c1. As I understand AIC candidates can be eliminated outside the loop but within the unit of the links with weak inference. There is a weak link between r8c1 and r2c1 on 1 so other 1s in the column can be removed. There is a weak link between r2c9 and r8c9 on 9 so 9s in that column can be removed.

Now, having got that far in my arguement and ready to refute you I see that I have a weak link between the 6s r2c1 and r2c9 and the 5s between r8c9 and r8c1, not a strong one, so perhaps there could be other 6s in row 2 and 5s in row 9 and it would still work. Interesting. I'll think on it over night. Very late now.
AndrewStuart
 
Posts: 21
Joined: 28 December 2005

Postby RW » Sun Sep 17, 2006 1:37 pm

AndrewStuart wrote:so perhaps there could be other 6s in row 2 and 5s in row 9 and it would still work. Interesting.

Indeed there could, seems like a standard XY-ring to me. Here's a very good example of one with no strong links (posted by Ocean in the Effortless-thread):
Code: Select all
 *-----------*
 |...|...|...|
 |..1|.2.|3..|
 |.3.|1.4|.5.|
 |---+---+---|
 |..6|...|2..|
 |.4.|...|.7.|
 |..8|...|9..|
 |---+---+---|
 |.1.|3.7|.4.|
 |..2|.9.|8..|
 |...|...|...|
 *-----------*

I don't think I need to point out exactly in which cells the XY-ring is...:)

I was thinking that perhaps the MXW could be useful if the cells wheren't bivalue cells, but instead part of some ALS:
Code: Select all
X      Y
*   a  #
aX-----aY
*      #
*      #
*   b  #
bX-----bY
*      #
*      #

practical example:
23      45
*    1  #
123-----145
*       #
*       #
*    6  #
623-----645
*       #
*       #

eliminate 23 from all '*'-cells and 45 from all '#'-cells

but it seems this would also work just as well without the strong links...

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby re'born » Tue Sep 19, 2006 10:10 am

Here is a naive argument which maybe someone can help me debunk:

Use subset counting.

In the first example, the 4 cells r2c19, r8c19 hold the four candidates 1,5,6,9 with max multiplicities 1,1,1,1, respectively. Therefore, any entry which would reduce the max multiplicity of any of those candidates to 0 must be incorrect. Hence, r9c1 != 1 and r15c9 != 9.

It seems that nowhere in this argument are the strong links used.

The same idea works with the second example.

What do you think?
re'born
 
Posts: 551
Joined: 31 May 2007


Return to Advanced solving techniques