XYZ-wings

Advanced methods and approaches for solving Sudoku puzzles

XYZ-wings

Postby 999_Springs » Mon Mar 26, 2007 12:43 pm

How commonly are XYZ-wings found in puzzles? I have not needed a single one to solve any Su-Doku puzzles. I have only ever found one (in my solution to Vidar's Monster #4) but it did not eliminate anything.
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Binarius » Mon Mar 26, 2007 1:31 pm

999_Springs, you may be interested in this topic, in which Mike Barker has done some excellent work detailing the relative frequency of tons of techniques.

(And in answer to your question, I think it can safely be said that XYZ-Wings are significantly more interesting than they are common.)
Binarius
 
Posts: 4
Joined: 14 February 2007

Postby daj95376 » Mon Mar 26, 2007 4:25 pm

The hierarchy of your techniques has a big influence on how often any particular technique occurs. I encounter XYZ-Wings all the time with my solver.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby RW » Mon Mar 26, 2007 4:48 pm

In this list the XYZ-wing was right after singles, subsets, x-wing, swordfish and XY-wing in the hierarchy. It shows that the XYZ-wing appears more frequently in random puzzles than X-wing, swordfish, hidden triplet and naked/hidden quads. Wouldn't call it very rare based on that...

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

Postby Binarius » Tue Mar 27, 2007 5:03 am

Silly me, RW, you're absolutely right.

This begs a question, though, that I wonder whether anybody would be interested in shedding some light on: what are the distributions of the various techniques independent of any hierarchy as regards solving priority? For example, I would imagine that there are plenty of higher-order techniques lurking within your puzzle before you tear through it with singles and the like; I would also imagine, for example, that you wouldn't still find three times as many naked singles as you do hidden singles (or 60 times as many naked pairs as hidden pairs!) if you looked for the hidden ones first.

Of course, it goes without saying that any solution is a discrete, stepwise procedure, and that we must therefore decide which of however many techniques are applicable to use first at any particular junction. But would a puzzle solved by applying the hardest techniques first and then going in descending order of complexity yield any more insights into the depths of sudoku logic? Would a puzzle generated by starting hard and descending come out any differently than one generated by starting easy and ascending? Any ideas?
Binarius
 
Posts: 4
Joined: 14 February 2007

Postby StrmCkr » Tue Mar 27, 2007 6:22 am

every move can be written as a more complex step so simple moves can also be variing complexity.

starting with the hardest move doesn't nessisarily degenreate a puzzle quickly as that move may infact acutally be a variation of a similar move thats is acutally is as is easy as a plain hidden pairs.

but in some instances it can. ive seen countless variations of single swordfish breaking a puzzle into singles and skipping all the other moves.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 732
Joined: 05 September 2006

Postby daj95376 » Tue Mar 27, 2007 5:40 pm

I took a set of 240 puzzles that contained several XYZ-Wings in the solution and moved the XYZ-Wing routine to later in the hierarchy before resolving the puzzles.

As 999_Springs observed, many of the XYZ_Wing eliminations were completely unnecessary and absorbed into the background by Singles.

However, several puzzles needed more coloring eliminations, and several puzzles needed XY-Wings later in the solution.

Again, this was a very small sampling of puzzles and they were generated with the objective of producing finned/Sashimi/Franken/Mutant fish.

Still, I'd like to see 999_Springs solution to this puzzles without using an XYZ-Wing. The only other SS bottleneck is [r3c2]<>1 from a finned X-Wing.

Code: Select all
..2..439...3.....24....3...8.12.7.3..24...97..7.8.52.4...3....92.....5...357..4..
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby udosuk » Tue Mar 27, 2007 6:04 pm

daj95376 wrote:Still, I'd like to see 999_Springs solution to this puzzles without using an XYZ-Wing. The only other SS bottleneck is [r3c2]<>1 from a finned X-Wing.
Code: Select all
..2..439...3.....24....3...8.12.7.3..24...97..7.8.52.4...3....92.....5...357..4..

After singles, you arrive at this state:

 *-----------------------------------------------------------*
 | 17    18    2     | 5     178   4     | 3     9     6     |
 | 167   5     3     | 9     1678  168   | 18    4     2     |
 | 4     168   9     | 16    2     3     | 18    5     7     |
 |-------------------+-------------------+-------------------|
 | 8     9     1     | 2     4     7     | 6     3     5     |
 | 5     2     4     | 16    3     16    | 9     7     8     |
 | 3     7     6     | 8     9     5     | 2     1     4     |
 |-------------------+-------------------+-------------------|
 |-16    4     8     | 3     5    @126   | 7    @26    9     |
 | 2     16    7     | 4    #168   9     | 5    #68    3     |
 | 9     3     5     | 7    #68    268   | 4    #268   1     |
 *-----------------------------------------------------------*

The UR r89c58={68} will force one of r7c68 to contain a 6.
Therefore r7c1 cannot be 6, must be 1 and all naked singles from here.

I don't know what type of UR this is, and not sure if it's easier than your xyz-wing on r2c5?

:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Sped » Tue Mar 27, 2007 6:36 pm

daj95376 wrote:Still, I'd like to see 999_Springs solution to this puzzles without using an XYZ-Wing. The only other SS bottleneck is [r3c2]<>1 from a finned X-Wing.

Code: Select all
..2..439...3.....24....3...8.12.7.3..24...97..7.8.52.4...3....92.....5...357..4..

Simple Sudoku gets stuck here:

Code: Select all
 
 *-----------------------------------------------------------*
 | 17    18    2     | 5     178   4     | 3     9     6     |
 | 167   5     3     | 9     1678  168   | 18    4     2     |
 | 4     168^  9     | 16^   2     3     | 18    5     7     |
 |-------------------+-------------------+-------------------|
 | 8     9     1     | 2     4     7     | 6     3     5     |
 | 5     2     4     | 16^   3     16^   | 9     7     8     |
 | 3     7     6     | 8     9     5     | 2     1     4     |
 |-------------------+-------------------+-------------------|
 | 16^   4     8     | 3     5   (1)2    | 7     26    9     |
 | 2     16^   7     | 4     168   9     | 5     68    3     |
 | 9     3     5     | 7     68    268   | 4     268   1     |
 *-----------------------------------------------------------*


[r7c6]-1-[r5c6]-6-[r5c4]-1-[r3c4]-6-[r3c2]=6=[r8c2]-6-[r7c1]-1-[r7c6] , => r7c6<>1

reduces it to singles.

Edit: Added the following:

I'm afraid I don't understand Udosuk's UR, but looking at it, I came up with this:

Code: Select all
 
 *-----------------------------------------------------------*
 | 17    18    2     | 5     178   4     | 3     9     6     |
 | 167   5     3     | 9     1678  168   | 18    4     2     |
 | 4     168   9     | 16    2     3     | 18    5     7     |
 |-------------------+-------------------+-------------------|
 | 8     9     1     | 2     4     7     | 6     3     5     |
 | 5     2     4     | 16    3     16    | 9     7     8     |
 | 3     7     6     | 8     9     5     | 2     1     4     |
 |-------------------+-------------------+-------------------|
 | 16    4     8     | 3     5     12    | 7     26    9     |
 | 2     16    7     | 4     168*  9     | 5     68*   3     |
 | 9     3     5     | 7     68*  (2)68  | 4     268*  1     |
 *-----------------------------------------------------------*


In order to avoid the deadly pattern (68 in r8c58 and r9c58), either r8c5=1 or r9c8=2.

If r8c5=1, then r7c6=2 and r9c6 <>2.
If r9c8=2, then r9c6 <>2.

So r9c6<>2, and it's all singles.
Sped
 
Posts: 126
Joined: 26 March 2006

Postby daj95376 » Wed Mar 28, 2007 3:59 am

Well, I completely missed the Deadly Pattern. My solution is more involved because of it.

udosuk: Nice catch on the DP. However, I'm unaware of any UR that performs an elimination outside of the rows/columns/boxes containing the vertices of the DP. Still, nice reduction logic without using Colors!

Sped: By using Colors to get [r7c6]<>6, you were able to get udosuk's DP to produce an elimination that might qualify as a UR elimination. I don't know which 'Type'.

Congratulations all around!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby re'born » Wed Mar 28, 2007 10:05 am

daj95376 wrote:
Sped: By using Colors to get [r7c6]<>6, you were able to get udosuk's DP to produce an elimination that might qualify as a UR elimination. I don't know which 'Type'.


To me, this would be an AUR deduction.

Incidentally, there are a couple of other deductions one could make from this same AUR, one of which solves the puzzle, the other only slightly advances it:

1) This first is just a different version of Sped's technique
Code: Select all
 *-----------------------------------------------------------*
 | 17    18    2     | 5     178   4     | 3     9     6     |
 | 167   5     3     | 9     1678  168   | 18    4     2     |
 | 4     168   9     | 16    2     3     | 18    5     7     |
 |-------------------+-------------------+-------------------|
 | 8     9     1     | 2     4     7     | 6     3     5     |
 | 5     2     4     | 16    3     16    | 9     7     8     |
 | 3     7     6     | 8     9     5     | 2     1     4     |
 |-------------------+-------------------+-------------------|
 | 16    4     8     | 3     5     12    | 7     (2)6  9     |
 | 2     16    7     | 4     168*  9     | 5     68    3     |
 | 9     3     5     | 7     68*   268   | 4     268*  1     |
 *-----------------------------------------------------------*


[r7c8]-2-[r9c8]=2|1=[r8c5]-1-[r7c6]-2-[r7c8]

and therefore r7c8<>2, which solves the puzzle.

2) The strong link on 8 in row 8 along with the potential deadly pattern in r89c58 implies that r9c8<>8 (or, similarly, one can use the strong link on 8 in column 8 and the DP to get r8c5<>8) and so r8c8=8. However, this does not solve the puzzle. After SS gets stuck again, one can play the same game:

Code: Select all
 *--------------------------------------------------*
 | 17   18   2    | 5    178  4    | 3    9    6    |
 | 167  5    3    | 9    178  168  | 18   4    2    |
 | 4    168  9    | 16   2    3    | 18   5    7    |
 |----------------+----------------+----------------|
 | 8    9    1    | 2    4    7    | 6    3    5    |
 | 5    2    4    | 16   3    16   | 9    7    8    |
 | 3    7    6    | 8    9    5    | 2    1    4    |
 |----------------+----------------+----------------|
 | 16   4    8    | 3    5    12   | 7    26   9    |
 | 2    16   7    | 4    1(6) 9    | 5    8    3    |
 | 9    3    5    | 7    68   28   | 4    26   1    |
 *--------------------------------------------------*


The strong link on 6 in row 9 along with the potential DP in r89c58 implies r8c5<>6, which solves the puzzle.

Alternatively, one could play the AUR game again:

Code: Select all
 *--------------------------------------------------*
 | 17*  18   2    | 5    178* 4    | 3    9    6    |
 | 167* 5    3    | 9    178* 168  | 18   4    2    |
 | 4    168  9    | 16   2    3    | 18   5    7    |
 |----------------+----------------+----------------|
 | 8    9    1    | 2    4    7    | 6    3    5    |
 | 5    2    4    | 16   3    16   | 9    7    8    |
 | 3    7    6    | 8    9    5    | 2    1    4    |
 |----------------+----------------+----------------|
 | 16   4    8    | 3    5    12   | 7    26   9    |
 | 2    16   7    | 4    16   9    | 5    8    3    |
 | 9    3    5    | 7    6(8) 28   | 4    26   1    |
 *--------------------------------------------------*


[r9c5]-8-[r12c5]=8|6=[r2c1]-6-[r7c1]-1-[r7c6]-2-[r9c6]-8-[r9c5]

and so r9c5<>8. This solves the puzzle.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Mike Barker » Wed Mar 28, 2007 6:54 pm

There are a number of UR's which crack the puzzle, but this is somewhat off topic.
Code: Select all
UR+2rd (6,8): r89c58 => r9c8<>6,r9c8<>8,r8c5<>8
+--------------+----------------+--------------+
|  17   18  2  |  5   178    4  |  3     9  6  |
| 167    5  3  |  9  1678  168  | 18     4  2  |
|   4  168  9  | 16     2    3  | 18     5  7  |
+--------------+----------------+--------------+
|   8    9  1  |  2     4    7  |  6     3  5  |
|   5    2  4  | 16     3   16  |  9     7  8  |
|   3    7  6  |  8     9    5  |  2     1  4  |
+--------------+----------------+--------------+
|  16    4  8  |  3     5   12  |  7    26  9  |
|   2   16  7  |  4  16-8*   9  |  5    68* 3  |
|   9    3  5  |  7    68* 268  |  4  2-68* 1  |
+--------------+----------------+--------------+

UR+2kd (6,8): r89c58, r9c6 => r8c5<>6,r8c5<>8,r9c8<>8
+--------------+----------------+--------------+
|  17   18  2  |  5   178    4  |  3     9  6  |
| 167    5  3  |  9  1678  168  | 18     4  2  |
|   4  168  9  | 16     2    3  | 18     5  7  |
+--------------+----------------+--------------+
|   8    9  1  |  2     4    7  |  6     3  5  |
|   5    2  4  | 16     3   16  |  9     7  8  |
|   3    7  6  |  8     9    5  |  2     1  4  |
+--------------+----------------+--------------+
|  16    4  8  |  3     5   12  |  7    26  9  |
|   2   16@ 7  |  4  1-68*   9  |  5    68* 3  |
|   9    3  5  |  7    68* 268  |  4  26-8* 1  |
+--------------+----------------+--------------+

Here are a couple examples from the zoo of XYZ-wings which do a nice job of cracking the puzzles. They are not necessary and if you are looking for longer XY-chains and rings then you may want to take that approach instead.
Code: Select all
..4....87..38.2..6.6...5....5..9.1.....3.........1.8.2..5....6....1267....1...9.. #13.1
...8..6...1.9..82...56..3...52.....38....4.1.....5.2..2.....1....64.....5...27..4 #13.2
Mike Barker
 
Posts: 458
Joined: 22 January 2006


Return to Advanced solving techniques