Exercise on xyz-wing and xy-chain

Advanced methods and approaches for solving Sudoku puzzles

Postby Max Beran » Wed Aug 24, 2005 6:06 pm

Tso - I love your edgy diagram and would like to have a clearer picture about it.

I happen to be the eponymous Max whose example Jeff used to initiate this thread. My own solution included a short xy-chain starting at r7c2 with a "2" and concluding with the "2" at r8c3 allowing the "2" to be eliminated from r7c7.

How does that fit into your scheme? I don't see a loop, nice or not, just a chain. Call me stupid but where does "proof" come into it? The chain of logical switching along the strung-together links is surely beyond argument or need of formality. I've stared long and hard at the red and blue lines and cannot see what distinguishes them. Is your scheme about xy-chains or is it some other structure? And is there any significance in the absence of a link between r7c3 and r8c3?

Is there any chance you could repeat the explanation using a simple cut-down example without the spaghetti of connections.

Thanking you in anticipation.
Max Beran
 
Posts: 57
Joined: 17 August 2005

Exercise on xyz-chain and xy-chain

Postby Bernard H » Fri Aug 26, 2005 3:56 pm

My attention has been brought to his posting, to see whether the 'Black Hole' technique and analysis can be used to solve this conundrum of a puzzle. I have not yet finished my examination but my first analysis can find no classic 'Black Hole' move.

The move involves the situation where you have eg. 17/27/127 on a line and row and related sequences/ terms with 7 as a possible in each of the cells. You cannot include both cells with the same terms eg 17/17 in opposition, but you can include one of those cells where it forms an integral part of the 'Chain', conjugation or sequence. The effect of the 'Black Hole' Technique is to place the common number in the cell at the main intersection So you are looking for a 'Footprint' of five related cells. In this puzzle that situation does not appear since many of the cells have three possibilities and there is no cell with four terms/candidates.

The underlying principle is to remove the number which is supposedly a candidate for all of the cells in the sequence and then to plot what are revealed 'singletons'. So I looked for this position with individual cells and found one weakness at r7c1.

If you examine the whole grid, you will find 2s at r1/2c9; (the only 2 on r9 and therefore strong), similarly r1c1 &r 2c2 are strong; r7c2 & r8c1 are strong only two on a col or row; and r7c7 & r8c7 are strong on c7. The effect of this is to perceive two 'Swordfish' which are interlocked or overlapping. This makes the 2 at r7c1 weak and excluding it produces a solution. Those are my first thoughts, but would want to look at other possibilities. Dare I say a bifurcation at r6c1/2 would be interesting since these two cells seem to me to be like an ammeter needle.

In one sense the twos in the on r7 &c1 are acting in a reverse way to the 'Black Hole' position but I need to look again

Heavens to Murgatroyd, Bernard, don't say such things; no bifurcations here

BH
Bernard H
 
Posts: 1
Joined: 26 August 2005

Postby tso » Fri Aug 26, 2005 4:19 pm

Max Beran wrote:... My own solution included a short xy-chain starting at r7c2 with a "2" and concluding with the "2" at r8c3 allowing the "2" to be eliminated from r7c7. How does that fit into your scheme?


It doesn't directly. I use BINARY GROUPS as one procedure to find a pair of forcing chains (xy-type chains). This procedure uses only exactly two candidates and therefore misses exclusions like the one you found. Only if it fails will I consider the cells with 3 or more candidates.

Max Beran wrote:... Call me stupid but where does "proof" come into it? The chain of logical switching along the strung-together links is surely beyond argument or need of formality.


I'm not using the word "proof" in any rigorous sense.

Max Beran wrote:I've stared long and hard at the red and blue lines and cannot see what distinguishes them. Is your scheme about xy-chains or is it some other structure?


The BLUE LINES are the BINARY GROUP. If you were to move from cell to cell, always following only blue lines, you would never find a contradiction in two consecutive cells. The entire binary group can exist in two internally consistant states. The RED LINES are NOT part of the binary group -- they are the only place where inconsistancies can be exploited. The group is the CONNECTIONS, not the cells themselves. By identifying the binary groups, even if there may be a complex network of lines, this procedure often makes the forcing chains obvious.

Here are some examples of simple binary groups:

a) [12][12] -- these two cells in the same row can exist in only two states: [1][2] or [2][1]
b) [12][23][34][14] -- these four cells in the same row can exist in only two states: [1][2][3][4] or[2][3][4][1]


Compare diagrams (c) and (d):
c)
Code: Select all
 12   .  23  |  .  34   .  | 14   .   .
  .   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .
-------------+-------------+-----------
 14   .   .  |  .  46   .  |  .   .  16
  .   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .
-------------+-------------+-----------
 24   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .


Simple Binary groups
r1c1357 -- [12][23][34][14]
r2c159 -- [14][46][16]
r147c1 -- [12][14][24]


d)
Code: Select all
 12   .  23  |  .  34   .  | 14   .   .
  .   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .
-------------+-------------+-----------
 16   .   .  |  .  46   .  |  .   .  14
  .   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .
-------------+-------------+-----------
 26   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .
  .   .   .  |  .   .   .  |  .   .   .


Simple Binary groups:
r1c1357 -- [12][23][34][14]
r2c159 -- [16][46][14]
r147c1 -- [12][16][26]

In both (c) and (d), BLUE lines are drawn between any two cells that are each in the same simple binary group. A RED line is drawn between r1c5 and r4c5 [34][46]. Although both cells are part of one of the three binary groups that overlap and form one larger binary group, this connection itself is NOT a part of the group, as these two cells *by themselves* are not in one simple binary group.

In (c) a pair of forcing chains -- exactly one of which crosses the red line -- will eliminate the 4:

r1c5=3 => r1c3=2 => r1c1=1 => r4c1=4 => r4c5=6
r1c5=4 => r4c5=6
Therefore, r4c5=6

In (d), the same loop is internally consistant -- it can exist without contradiction in either of two states. The RED line is removed and replaced with a BLUE line.

Once a loop is formed, you could apply David Eppstein's suggested labeling *only* to the lines in the loop to very quickly find if it will allow an elimination. This saves a lot of labeling. In (c), the lines would be labeled 44321 while (d) would be 64321. Also, Eppstein's method would require you to draw ALL connections, whereas using binary groups, you can safely assume many of them. For example, say you have these five cells in a row:

[12][45][23][15][34]

Using the Binary Groups procedure, I'll just draw a single line connecting these five cells in the order they appear -- even though no two consecutive cells actually share a candidate. If I were using Eppstein's method, I'd connect the 1st cell to the 3rd and 4th, the 2nd to the 4th and 5th, etc. Five edges, five labels -- confusing already. However, sometimes there are few or no simple binary groups and Eppstein's method is much simpler.

Once this procedure is exhausted, I would consider how the binary group interacts with the cells with 3 or more candidates.

Max Beran wrote:And is there any significance in the absence of a link between r7c3 and r8c3?


Oversight.

Max Beran wrote:Is there any chance you could repeat the explanation using a simple cut-down example without the spaghetti of

connections.



See these two posts on BINARY GROUPS:

Here and
here
tso
 
Posts: 798
Joined: 22 June 2005

Previous

Return to Advanced solving techniques