xyt-chains

Advanced methods and approaches for solving Sudoku puzzles

Postby denis_berthier » Sat Jul 28, 2007 8:17 am

Until now, you got only the simplest pedagogical examples of xyt-chains.
Now fasten your seat belts for a jump into hyperspace.
(Try to solve it before looking at the solution).

(xyzt-chains are an extension of xyt-chains, where the target value is allowed as an optional additional candidate in any cell that is linked to the target cell.)

100060800
008003001
000020005
060007000
034800000
002900703
000400098
000000000
609070000


CLIPS> (solve-nth-grid-from-text-file Sudogen0 3949)
***** SudoRules version 12 *****
number 8 : hidden-single-in-row R3 ==> R3C6 = 8
number 8 : hidden-single-in-block B8 ==> R8C5 = 8
number 8 : hidden-single-in-block B7 ==> R9C2 = 8
number 9 : hidden-single-in-block B8 ==> R8C6 = 9
number 9 : hidden-single-in-block B2 ==> R2C5 = 9
number 4 : hidden-single-in-block B2 ==> R1C6 = 4
number 1 : hidden-single-in-block B2 ==> R3C4 = 1
number 7 : hidden-single-in-row R5 ==> R5C1 = 7
number 9 : hidden-single-in-block B4 ==> R4C1 = 9
number 8 : hidden-single-in-block B4 ==> R6C1 = 8
number 8 : hidden-single-in-block B6 ==> R4C8 = 8
number 6 : hidden-single-in-column C3 ==> R3C3 = 6
number 6 : hidden-single-in-column C4 ==> R8C4 = 6
number 6 : hidden-single-in-row R7 ==> R7C7 = 6
number 6 : hidden-single-in-block B3 ==> R2C8 = 6
number 6 : hidden-single-in-block B6 ==> R5C9 = 6
number 6 : hidden-single-in-block B5 ==> R6C6 = 6
number 9 : hidden-single-in-block B6 ==> R5C7 = 9
number 9 : hidden-single-in-block B3 ==> R1C9 = 9
number 9 : hidden-single-in-block B1 ==> R3C2 = 9
number 7 : hidden-single-in-row R3 ==> R3C8 = 7
number 7 : hidden-single-in-block B9 ==> R8C9 = 7
number 4 : row R9 interaction with block B9
==> 4 eliminated from the candidates for R8C8
number 4 : row R9 interaction with block B9
==> 4 eliminated from the candidates for R8C7
number 5 : block B2 interaction with column C4
==> 5 eliminated from the candidates for R9C4
number 5 : block B2 interaction with column C4
==> 5 eliminated from the candidates for R4C4
number 4 : block B3 interaction with column C7
==> 4 eliminated from the candidates for R9C7
number 4 : block B3 interaction with column C7
==> 4 eliminated from the candidates for R4C7
number 2 : x-wing-in-columns C4 and C9 with rows R4 and R9
==> 2 eliminated from the candidates for R9C8
number 2 : x-wing-in-columns C4 and C9 with rows R4 and R9
==> 2 eliminated from the candidates for R9C7
number 2 : x-wing-in-columns C4 and C9 with rows R4 and R9
==> 2 eliminated from the candidates for R9C6
number 2 : x-wing-in-columns C4 and C9 with rows R4 and R9
==> 2 eliminated from the candidates for R4C7
numbers 1 and 5 : naked-pairs-in-row R4: R4C3-R4C7
==> 5 eliminated from the candidates for R4C5
numbers 1 and 5 : naked-pairs-in-row R4: R4C3-R4C7
==> 1 eliminated from the candidates for R4C5
number 2 : c4-chain row-bl-col on cells R1C2-R1C8-R2C7-R8C7
==> 2 eliminated from the candidates for R8C2
number 5 : xyzt9-chain-type-1 on cells R9C6*, R7C6*, R5C6, R5C5, R5C8, R1C8, R3C7, R3C1 and R7C1* with numbers 5, 1, 2, 5, 1, 2, 3, 4 and 3
==> 5 eliminated from the candidates for R7C5
number 5 : column C5 interaction with block B5
==> 5 eliminated from the candidates for R5C6
number 3 : xyt9-chain on cells R7C5*, R9C6, R7C6, R5C6, R5C5, R5C8, R1C8, R3C7 and R3C1* with numbers 3, 1, 5, 2, 1, 5, 2, 3 and 4
==> 3 eliminated from the candidates for R7C1
number 3 : c4-chain row-bl-col on cells R1C8-R1C3-R3C1-R8C1
==> 3 eliminated from the candidates for R8C8
number 5 : xyzt8-chain-type-1 on cells R4C7*, R5C8*, R5C6, R9C6, R7C6, R9C4, R9C7 and R8C8* with numbers 5, 1, 2, 1, 5, 2, 3 and 1
==> 5 eliminated from the candidates for R6C8
number 3 : xyt10-chain on cells R7C5*, R9C6, R7C6, R7C1, R7C2, R7C3, R8C3, R4C3, R4C7 and R9C7* with numbers 3, 1, 5, 2, 5, 7, 3, 1, 5 and 1
==> 3 eliminated from the candidates for R9C4
number 2 : naked-single ==> R9C4 = 2
number 3 : naked-single ==> R4C4 = 3
number 4 : naked-single ==> R4C5 = 4
number 2 : naked-single ==> R4C9 = 2
number 4 : naked-single ==> R9C9 = 4
number 4 : hidden-single-in-column C8 ==> R6C8 = 4
number 2 : hidden-single-in-row R5 ==> R5C6 = 2
number 3 : hidden-single-in-column C5 ==> R7C5 = 3
number 2 : row R7 interaction with block B7
==> 2 eliminated from the candidates for R8C1
number 3 : row R9 interaction with block B9
==> 3 eliminated from the candidates for R8C7
number 1 : xyzt7-chain-type-3 on cells R4C3*, R4C7, R5C8, R8C8*, R1C8, R1C3 and R7C3* with numbers 1, 5, 1, 5, 2, 3 and 7
==> 1 eliminated from the candidates for R8C3
number 5 : xyt5-chain on cells R6C2*, R4C3, R8C3, R1C3 and R1C4* with numbers 5, 1, 5, 3 and 7
==> 5 eliminated from the candidates for R1C2
number 2 : xyt5-chain on cells R1C2*, R1C4, R1C3, R8C3 and R7C1* with numbers 2, 7, 5, 3 and 5
==> 2 eliminated from the candidates for R7C2
number 2 : hidden-single-in-block B7 ==> R7C1 = 2
number 5 : xyzt5-chain-type-3 on cells R6C2*, R4C3, R8C3, R8C1* and R8C2* with numbers 5, 1, 5, 3 and 4
==> 5 eliminated from the candidates for R7C2
number 1 : c6-chain on cells R9C6-R7C6-R7C3-R4C3-R4C7-R5C8
==> 1 eliminated from the candidates for R9C8
number 5 : xyz-wing on cells R4C7*, R9C7* and R9C8* with numbers 5, 1 and 3
==> 5 eliminated from the candidates for R8C7
number 5 : xy5-chain on cells R7C6*, R7C2, R1C2, R1C8 and R9C8* with numbers 5, 1, 7, 2 and 3
==> 5 eliminated from the candidates for R9C6
number 1 : naked-single ==> R9C6 = 1
number 5 : naked-single ==> R7C6 = 5
number 1 : row R7 interaction with block B7
==> 1 eliminated from the candidates for R8C2
number 5 : row R9 interaction with block B9
==> 5 eliminated from the candidates for R8C8
row R1 : hxy5-cn-chain on cn-cells C2N2*, C7N2, C7N1, C3N1 and C3N7* with rows R1, R2, R8, R4 and R7
==> R1 eliminated from the cn-candidates for C2N7
i.e. 7 eliminated from the candidates for R1C2
…(NS and HS)…
GRID 3949 SOLVED IN CONTEXT cont-0, AT DEPTH 0. MAX-DEPTH = 0. LEVEL = L10, TECHNIQUE = XYT10
125764839
478593261
396128475
961347582
734852916
852916743
217435698
543689127
689271354
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Sat Jul 28, 2007 10:34 am

Denis, posting the output of programmed solvers in this forum is generally unacceptable, fullstop.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby sirdave » Sun Jul 29, 2007 9:14 pm

Denis B: Try to solve it before looking at the solution.

Yes, there seems to be a disconnect here where human manual solvers are challenged to solve a puzzle where computer solver output of the solution is shown. IMO, this is not in keeping with the whole idea of the challenge inherent in sudoku solving (not to mention the impressive manner in which new methods have been introduced in the hallowed halls of this section of the Player's forum over the last 2 years+).
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby denis_berthier » Mon Jul 30, 2007 5:48 am

ronk, sirdave OK, I could have done better than this listing.
Nevertheless, from it, you can see something very characteristic of my approach:
any step in the resolution is the identification of a pre-defined pattern with a predefined conclusion.
In my solutions, you will never see any ad hoc extra reasoning, for which one never knows if it is part of a rule or T&E.

BTW, SudoRules is not a program in the ordinary sense, it is the direct transcription of my set of resolution rules.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Fri Aug 31, 2007 7:13 am

In response to a private question: "Do the new nrc(z)(t) chains make the (h)xy(z)(t) chains obsolete?"

NO, because:
- nrc(z)(t) chains subsume the corresponding (h)xy(z)(t) chains, i.e. they are more general,
- but more general doesn't mean better, it means more complex, more difficult to find,
- (h)xy(z)(t) are simpler because they can be found in one of the 2D spaces (rc-, rn- or cn-) using the extended Sudoku Board designed for this purpose,
- 97% of the randomly generated puzzles can still be solved with the (h)xy(z)(t) chains; the introduction of the nrc(z)(t) chains raises this percentage to almost 100% but it doesn't change the previous results.

What is true is that, in some cases, using nrc(z)(t) chains allows to use shorter (although more complex) chains. But that'd be true for any new kind of rule: whenever you define a new pattern, it will make some puzzles appear as easier to solve for some people. For any puzzle, there are always multiple solution paths. Which rules you prefer is a matter of personal taste and cannot be usefully debated.

Notice that the nrc-notation I recently introduced for nrc-chains can be applied as well to the (h)xy(z)(t) chains, for which it is a clear improvement wrt my initial notation. But this doesn't change the nature of these chains.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Previous

Return to Advanced solving techniques