non-repetitive xy-chain

Advanced methods and approaches for solving Sudoku puzzles

non-repetitive xy-chain

Postby Jeff » Fri Sep 02, 2005 11:19 am

Up till now, our description of xy-chain is of a repetitive type and would only allow us to eliminate one candidate from one cell as posted here.

However, if a non-repetitive xy-chain can be identified, it would allow us to possibly eliminate candidates from every unit where each edge of the chain lies. The name 'non-repetitive' implies that none of the consecutive edges on the chain have the same label.

Let me demonstrate via 2 examples:

Image
The chain is: starting from r1c2, [89]-[92]-[21]-[13]-[35]-[58]. Due to the existence of this non-repetitive xy-chain, 3 and 8 can be eliminated from r3c7 and r1c3 respectively.

Image
The chain is: starting from r1c7, [29]-[91]-[13]-[37]-[74]-[47]-[74]-[42]. Due to the existence of this non-repetitive xy-chain, 7, 24 and 7 can be eliminated from r4c1, r9c7 and r4c9 respectively.

These chains can be identified by pure inspection of bevalue cells as follows:

1) Choose one cell to start with and mark down the first candidate.
2) Propogate through the grid with cells that lie on the same unit.
3) Match the last candidate of the cell with the first candidate of the next cell.
4) Repeat the process until a cell (last cell) is found lying in the same unit with the starting cell.
5) If the last candidate of the last cell matches the first candidate of the starting cell, then congratulations, you have found a non-repetitive xy-chain.
Last edited by Jeff on Fri Sep 02, 2005 9:22 am, edited 2 times in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Sue De Coq » Fri Sep 02, 2005 12:20 pm

Jeff,

The following observation won't be of direct interest to you, because it doesn't explain how my solver found the chains in question. However, you might be able to work backwards from the presented chains in order to see how you might have spotted them in your world.

(First problem)

r2c3<>3 => r1c3=3 => r1c3<>7 => r1c9=7 => r1c9 <>9 => r3c9=9
r2c3<>3 => r2c4=3 => r3c4<>3 => r3c4=9 => r3c3<>9

Since this is a contradiction, we must have r2c3=3.

I solve the second problem differently to you but in that case I don't think my solution is an improvement.
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby Jeff » Fri Sep 02, 2005 1:41 pm

Sue De Coq

Thank you for your response. Again, you have demonstrated the powerful nature of forcing chains. In fact, there are quite a number of chains that can be identified from the examples. The first example can be solved by an xyz-chain which is just another form of forcing chain. The second example can be solved by a simple but long and curly xy-chain. Interestingly though, the xy-chain that I have demonstrated in the first example doesn't lead directly to a solution. I am just using it to demonstrate the concept of non-repetitive xy-chain, a chain which I consider as identifiable within human ability without any requirements of filtering or graphing.:D
Jeff
 
Posts: 708
Joined: 01 August 2005


Return to Advanced solving techniques