An example of how using restricted forms of nrc-chains can be helpful

Consider the following puzzle

.12...3..

...4...5.

6..3..2..

.....7..4

..3.1.6..

8..5.....

..7..4..2

.2...9...

..6...79.

This is puzzle "Extra252-hard", from papyg, here:

http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=836 (I've already mentioned this French forum, where nrczt-chains are used daily)

Its ER is 9.1

If I try to solve it with the most general nrczt-chains, I get a memory overflow.

***** SudoRules version 13 *****

hidden-singles ==> r6c5 = 4, r8c7 = 4, r3c3 = 4, r1c8 = 4

interaction column c8 with block b9 for number 6 ==> r8c9 <> 6

interaction column c4 with block b8 for number 1 ==> r9c6 <> 1

naked-pairs-in-a-row {n1 n9}r6{c3 c7} ==> r6c9 <> 9, r6c9 <> 1, r6c8 <> 1, r6c2 <> 9

nrc2-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} ==> r8c9 <> 5

nrc2-chain n5{r7c7 r4c7} - n5{r4c3 r8c3} ==> r7c2 <> 5, r7c1 <> 5

xyt4-chain {n9 n1}r6c7 - {n1 n9}r6c3 - {n9 n8}r2c3 - {n8 n9}r2c7 ==> r4c7 <> 9

hxyt-cn4-chain {r7 r4}c7n5 - {r4 r8}c3n5 - {r8 r2}c3n8 - {r2 r7}c7n8 ==> r7c7 <> 1

nrc4-chain n5{r8c3 r4c3} - n5{r4c7 r5c9} - n9{r5c9 r6c7} - n1{r6c7 r6c3} ==> r8c3 <> 1

interaction column c3 with block b4 for number 1 ==> r4c1 <> 1

nrct5-chain n3{r9c6 r6c6} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 ==> r9c6 <> 2

nrct5-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 ==> r4c5 <> 2

nrct5-chain n2{r4c1 r5c1} - n4{r5c1 r5c2} - n7{r5c2 r6c2} - n6{r6c2 r6c6} - n2{r6c6 r4c4} ==> r4c8 <> 2

nrct6-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} - n8{r8c3 r2c3} - n8{r2c7 r7c7} - n8{r7c2 r9c2} - n4{r9c2 r5c2} ==> r5c2 <> 5

nrct6-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 - {n2 n9}r5c4 ==> r4c5 <> 9

interaction column c5 with block b2 for number 9 ==> r1c4 <> 9

;;;

example of a chain whose t- or z- candidates need nrc links:

nrczt6-chain n8{r2c3 r8c3} - n8{r9c2 r3c2} - n5{r3c2 r1c1} - n5{r9c1 r9c2} - n5{r9c6 r3c6} - n1{r3c6 r2c6} ==> r2c6 <> 8

nrczt7-chain n8{r2c3 r8c3} - n8{r7c2 r3c2} - n5{r3c2 r1c1} - n5{r8c1 r9c2} - n5{r9c6 r3c6} - n1{r3c6 r2c6} - n2{r2c6 r2c5} ==> r2c5 <> 8

nrczt7-lr-lasso {n8 n2}r5c6 - {n2 n7}r5c8 - {n7 n3}r6c9 - {n3 n1}r4c8 - n1{r6c7 r2c7} - {n1 n6}r2c6 - {n6 n2}r6c6 ==> r5c9 <> 8

nrczt8-chain n8{r2c3 r8c3} - n8{r9c2 r3c2} - n5{r3c2 r1c1} - n5{r9c1 r9c2} - n5{r9c6 r3c6} - n1{r3c6 r2c6} - n2{r2c6 r2c5} - n6{r2c5 r2c9} ==> r2c9 <> 8

;;;

example of a chain whose t- or z- candidates need nrc links:

nrczt8-lr-lasso n3{r4c5 r4c8} - n3{r6c9 r9c9} - n5{r9c9 r5c9} - n9{r5c9 r6c7} - n1{r6c7 r4c7} - {n1 n8}r2c7 - n8{r3c9 r8c9} - n8{r8c3 r2c3} ==> r8c5 <> 3

nrczt9-lr-lasso n5{r3c2 r1c1} - n7{r1c1 r5c1} - n7{r5c8 r6c8} - n2{r6c8 r6c6} - n2{r2c6 r2c5} - n7{r2c5 r2c9} - n6{r2c9 r2c6} - {n6 n8}r1c6 - {n8 n2}r5c6 ==> r3c2 <> 7

nrczt9-lr-lasso {n7 n3}r6c9 - {n3 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 - {n2 n6}r6c6 - n3{r6c6 r4c5} - {n3 n1}r4c8 - n1{r6c7 r2c7} - {n1 n2}r2c6 ==> r5c9 <> 7

Memory overflow

Now, if Iuse the restricted version of nrczt-chains, I get the solution:

***** SudoRules version 13 *****

hidden-singles ==> r6c5 = 4, r8c7 = 4, r3c3 = 4, r1c8 = 4

interaction column c8 with block b9 for number 6 ==> r8c9 <> 6

interaction column c4 with block b8 for number 1 ==> r9c6 <> 1

naked-pairs-in-a-row {n1 n9}r6{c3 c7} ==> r6c9 <> 9, r6c9 <> 1, r6c8 <> 1, r6c2 <> 9

nrc2-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} ==> r8c9 <> 5

nrc2-chain n5{r7c7 r4c7} - n5{r4c3 r8c3} ==> r7c2 <> 5, r7c1 <> 5

xyt4-chain {n9 n1}r6c7 - {n1 n9}r6c3 - {n9 n8}r2c3 - {n8 n9}r2c7 ==> r4c7 <> 9

hxyt-cn4-chain {r7 r4}c7n5 - {r4 r8}c3n5 - {r8 r2}c3n8 - {r2 r7}c7n8 ==> r7c7 <> 1

nrc4-chain n5{r8c3 r4c3} - n5{r4c7 r5c9} - n9{r5c9 r6c7} - n1{r6c7 r6c3} ==> r8c3 <> 1

interaction column c3 with block b4 for number 1 ==> r4c1 <> 1

nrct5-chain n3{r9c6 r6c6} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 ==> r9c6 <> 2

nrct5-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 ==> r4c5 <> 2

nrct5-chain n2{r4c1 r5c1} - n4{r5c1 r5c2} - n7{r5c2 r6c2} - n6{r6c2 r6c6} - n2{r6c6 r6c8} ==> r4c8 <> 2

nrct6-chain n5{r5c9 r4c7} - n5{r4c3 r8c3} - n8{r8c3 r2c3} - n8{r2c7 r7c7} - n8{r7c2 r9c2} - n4{r9c2 r5c2} ==> r5c2 <> 5

nrct6-chain n3{r4c5 r4c8} - {n3 n7}r6c9 - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 - {n2 n9}r5c4 ==> r4c5 <> 9

interaction column c5 with block b2 for number 9 ==> r1c4 <> 9

;;; same path as above, downto this point

nrczt7-chain n8{r2c2 r3c2} - n8{r2c3 r8c3} - n5{r8c3 r4c3} - n5{r4c2 r9c2} - n5{r8c1 r8c5} - n5{r3c5 r3c6} - n1{r3c6 r2c6} ==> r2c6 <> 8; instead of an nrczt6-chain

nrczt7-chain n8{r2c2 r3c2} - n5{r3c2 r1c1} - {n5 n6}r1c6 - {n6 n7}r1c4 - n7{r8c4 r8c5} - n5{r8c5 r8c3} - n8{r8c3 r2c3} ==> r2c5 <> 8

nrczt7-lr-lasso {n8 n2}r5c6 - {n2 n7}r5c8 - {n7 n3}r6c9 - {n3 n1}r4c8 - n1{r6c7 r2c7} - {n1 n6}r2c6 - {n6 n2}r6c6 ==> r5c9 <> 8

nrczt9-rl-lasso n8{r2c2 r3c2} - {n8 n9}r2c3 - n9{r6c3 r6c7} - {n9 n1}r2c7 - n1{r2c6 r3c6} - n5{r3c6 r3c5} - n5{r3c2 r1c1} - n5{r8c1 r8c3} - n8{r8c3 r2c3} ==> r2c9 <> 8; instead of an nrczt8-chain

;;; same eliminations as above, downto this point

nrczt9-lr-lasso {n7 n3}r6c9 - {n3 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 - {n2 n6}r6c6 - n3{r6c6 r4c5} - {n3 n1}r4c8 - n1{r6c7 r2c7} - {n1 n2}r2c6 ==> r5c9 <> 7

;;; new eliminations:

nrczt10-lr-lasso n3{r9c6 r6c6} - n3{r4c5 r4c8} - {n3 n7}r6c9 - n7{r5c8 r3c8} - {n7 n2}r6c8 - {n2 n8}r5c8 - {n8 n2}r5c6 - n2{r4c4 r9c4} - n1{r9c4 r9c9} - n1{r7c8 r8c8} ==> r9c1 <> 3

nrczt10-lr-lasso n7{r6c2 r5c1} - n7{r5c8 r6c8} - n2{r6c8 r6c6} - n2{r2c6 r2c5} - n7{r2c5 r2c9} - n6{r2c9 r2c6} - n1{r2c6 r3c6} - n5{r3c6 r3c5} - {n5 n8}r1c6 - {n8 n2}r5c6 ==> r3c2 <> 7

nrct11-chain n5{r7c7 r4c7} - n5{r5c9 r5c1} - n4{r5c1 r9c1} - n4{r9c2 r5c2} - n7{r5c2 r5c8} - n8{r5c8 r4c8} - {n8 n1}r3c8 - n1{r3c6 r2c6} - n2{r2c6 r2c5} - n2{r9c5 r9c4} - n1{r9c4 r9c9} ==> r9c9 <> 5

naked and hidden singles ==> r7c7 = 5, r5c9 = 5, r6c7 = 9, r6c3 = 1

nrczt3-chain n8{r1c4 r1c9} - {n8 n1}r2c7 - n1{r2c6 r3c6} ==> r3c6 <> 8

nrczt7-chain n8{r2c7 r4c7} - n1{r4c7 r2c7} - {n1 n7}r3c8 - {n7 n2}r5c8 - n2{r6c8 r6c6} - {n2 n6}r2c6 - n6{r2c9 r1c9} ==> r1c9 <> 8

interaction row r1 with block b2 for number 8 ==> r3c5 <> 8

nrczt6-lr-lasso n3{r9c6 r6c6} - n3{r4c5 r4c8} - n1{r4c8 r4c7} - n8{r4c7 r2c7} - n8{r2c3 r8c3} - n8{r8c9 r3c9} ==> r9c9 <> 3

nrc2-chain n3{r8c9 r6c9} - n3{r6c6 r4c5} ==> r8c5 <> 3

nrct6-chain n3{r9c6 r6c6} - n3{r6c9 r8c9} - n3{r7c8 r4c8} - n1{r4c8 r4c7} - {n1 n8}r2c7 - n8{r3c9 r9c9} ==> r9c6 <> 8

nrczt7-chain {n1 n8}r9c9 - {n8 n3}r8c9 - {n3 n5}r8c1 - n5{r1c1 r3c2} - n8{r3c2 r3c8} - {n8 n1}r2c7 - n1{r4c7 r4c8} ==> r8c8 <> 1

nrczt7-lr-lasso n5{r3c5 r3c2} - n5{r3c6 r9c6} - n3{r9c6 r6c6} - n3{r4c5 r4c8} - n1{r4c8 r4c7} - n8{r4c7 r2c7} - n8{r2c2 r2c3} ==> r1c5 <> 5

nrczt5-chain n5{r1c1 r1c6} - n5{r3c5 r3c2} - n5{r9c2 r9c5} - n2{r9c5 r9c4} - n2{r4c4 r4c1} ==> r4c1 <> 5

nrc3-chain n5{r1c1 r3c2} - n5{r4c2 r4c3} - n9{r4c3 r2c3} ==> r1c1 <> 9

nrct4-chain {n9 n8}r2c3 - {n8 n5}r8c3 - n5{r9c1 r1c1} - {n5 n9}r3c2 ==> r2c2 <> 9

nrct4-chain {n9 n8}r2c3 - {n8 n5}r8c3 - n5{r9c1 r1c1} - {n5 n9}r3c2 ==> r2c1 <> 9

nrct6-chain n9{r2c3 r4c3} - n9{r4c4 r5c4} - n9{r5c1 r7c1} - {n9 n2}r4c1 - n2{r4c4 r9c4} - n2{r9c5 r2c5} ==> r2c5 <> 9

nrczt6-lr-lasso n8{r8c3 r2c3} - n8{r2c7 r4c7} - n8{r5c8 r5c6} - n8{r1c6 r1c5} - n9{r1c5 r1c9} - n9{r2c9 r2c3} ==> r8c4 <> 8

nrct7-chain n3{r4c5 r6c6} - {n3 n5}r9c6 - n5{r1c6 r1c1} - n5{r3c2 r4c2} - n5{r4c3 r8c3} - n8{r8c3 r2c3} - n8{r2c7 r4c7} ==> r4c5 <> 8

nrczt7-rl-lasso n3{r4c5 r4c8} - n1{r4c8 r4c7} - n8{r4c7 r5c8} - n8{r4c8 r4c4} - n8{r7c4 r7c2} - n8{r3c2 r3c9} - n8{r2c7 r4c7} ==> r7c5 <> 3

interaction block b8 with row r9 for number 3 ==> r9c2 <> 3

nrczt7-lr-lasso {n1 n8}r2c7 - {n8 n7}r3c8 - {n7 n9}r3c9 - {n9 n5}r3c5 - n5{r1c6 r1c1} - n5{r8c1 r8c3} - n8{r8c3 r2c3} ==> r2c9 <> 1

nrc5-chain n3{r4c5 r9c5} - {n3 n5}r9c6 - {n5 n1}r3c6 - n1{r2c6 r2c7} - n1{r4c7 r4c8} ==> r4c8 <> 3

hidden-singles ==> r4c5 = 3, r9c6 = 3

interaction column c6 with block b2 for number 5 ==> r3c5 <> 5

naked-pairs-in-a-block {n1 n8}{r4c7 r4c8} ==> r5c8 <> 8

interaction row r5 with block b5 for number 8 ==> r4c4 <> 8

nrc4-chain {n8 n1}r2c7 - n1{r2c6 r3c6} - n5{r3c6 r3c2} - n9{r3c2 r2c3} ==> r2c3 <> 8

naked-singles ==> r2c3 = 9, r4c3 = 5, r8c3 = 8

nrc3-chain {n7 n5}r1c1 - n5{r8c1 r8c5} - n7{r8c5 r8c4} ==> r1c4 <> 7

hidden-single-in-a-column ==> r8c4 = 7

nrc5-chain n1{r7c4 r9c4} - n2{r9c4 r9c5} - n2{r2c5 r2c6} - n1{r2c6 r2c7} - n1{r4c7 r4c8} ==> r7c8 <> 1

interaction block b9 with column c9 for number 1 ==> r3c9 <> 1

nrczt5-lr-lasso {n8 n1}r9c9 - {n1 n3}r8c9 - n3{r6c9 r6c8} - n2{r6c8 r6c6} - n2{r4c4 r5c4} ==> r9c4 <> 8

nrc6-chain {n7 n3}r2c1 - n3{r2c2 r7c2} - n9{r7c2 r7c1} - n1{r7c1 r7c4} - {n1 n2}r9c4 - n2{r9c5 r2c5} ==> r2c5 <> 7

hidden-pairs-in-a-block {n7 n9}{r1c5 r3c5} ==> r1c5 <> 8

interaction column c5 with block b8 for number 8 ==> r7c4 <> 8

hidden-pairs-in-a-block {n7 n9}{r1c5 r3c5} ==> r1c5 <> 6

nrc4-chain {n8 n5}r3c2 - {n5 n7}r1c1 - {n7 n9}r1c5 - n9{r3c5 r3c9} ==> r3c9 <> 8

hidden-singles ==> r9c9 = 8, r7c5 = 8, r8c9 = 1, r6c9 = 3

interaction column c9 with block b3 for number 7 ==> r3c8 <> 7

naked-triplets-in-a-column {n5 n7 n3}{r1 r2 r8}c1 ==> r9c1 <> 5, r7c1 <> 3, r5c1 <> 7

interaction column c1 with block b1 for number 7 ==> r2c2 <> 7

nrc3-chain n6{r2c5 r8c5} - n5{r8c5 r8c1} - n5{r1c1 r1c6} ==> r1c6 <> 6

xy4-chain {n6 n7}r2c9 - {n7 n3}r2c1 - {n3 n5}r8c1 - {n5 n6}r8c5 ==> r2c5 <> 6

naked-singles

GRID /Users/berthier/Documents/INT-Projets/SudoRules/SudoRules13/Puzzles/papyg/Extra252-hard-mem-overflow.sdk SOLVED. LEVEL = L11, MOST COMPLEX RULE = NRCT11

712895346

389426157

654371289

295637814

473918625

861542973

937184562

528769431

146253798

This may seem to be only an implementation problem of SudoRules, but it is not. As SudoRules searches for shorter chains before longer ones, memory overflow is directly related to the number of partial chains one has to consider before eventually reaching a solution.

This puzzle belongs to the category of puzzles that have many useless partial chains and for which the difficulty consists of finding the useful ones. In such cases, using restricted forms of chains may lead to an easier solution (but there's no guarantee that it will always be the case).

Another example of this situation is given by puzzle Sudogen0 #707.

(In the opposite case of puzzles that have few partial chains, one could try to use more general chains. But, useable generalisations of nrczt-chains, which are not overly general, are not yet obvious.)

Note: when I give a solution of a puzzle, I use the unrestricted version of nrczt-chains, unless otherwise stated.