BRAID EXAMPLEI've had a hard time coding braids in SudoRules in a way that doesn't lead to memory overflow. I can't yet say I've done it in a fully satisfactory way (computation times remain very long and lots of optimisations are still possible, but I'm not here to speak of implementation details in CLIPS). At least, I can now find braids of decent length.

Once introduced in SudoRules, braids blend perfectly with whips, as shown by the following example.

I had to make some choice about where to put braids in my complexity hierarchy.

As shown in the "rating" thread (here:

http://forum.enjoysudoku.com/viewtopic.php?t=5995), length remains the best criterion from a statistical POV.

I have therefore extended SudoRules default strategy so as to include braids of length n just after whips of length n and before any chain of length n+1.

(As braids of length n subsume all the chains of the same length in the xy-to-nrczt family, this is a natural choice).

As for the rest of SudoRules, the way braids are coded would allow me to change this strategy in a very straightforward way if an alternative one was needed. But this is beyond the purpose of this example, which is only to show how resolution rules for braids (here, only the most elementary ones - nrczt-braids) can be used effectively as any other resolution rule.

The example I'll consider is # 89 (SER = 9.3) in the top1465 collection.

1) # 89 is one of the 5 puzzles in the top1465 collection that can't be solved by nrczt-whips only.(Notice that this is very rare for a puzzle with SER = 9.3).

More specifically, if I run SudoRules with the usual rules for nrczt-whips (no braids), I get the following resolution path.

Some eliminations are preceded by a capital letter at the beginning of their line.

Corresponding eliminations in the resolution path with braids will be indicated by the same capital letter in the path with braids; they will be primed if the justifying pattern is different.

***** SudoRules version 13.7wbis *****

...3..5...5..1..3...7..4..12.....4...6..9......1..6..28..7..2...9..8..5...5..9..7

hidden-single-in-a-row ==> r8c1 = 7

nrczt-whip-rn[2] n7{r5c8 r5c6} - {n7r2c6 .} ==> r6c7 <> 7

swordfish-in-columns n2{r3 r9 r1}{c2 c5 c8} ==> r9c4 <> 2, r3c4 <> 2, r1c6 <> 2, r1c3 <> 2

nrc-chain[3] n5{r4c9 r5c9} - n5{r5c1 r6c1} - n9{r6c1 r4c3} ==> r4c9 <> 9

nrczt-whip-cn[3] n9{r4c3 r4c8} - n9{r6c7 r3c7} - {n9r3c4 .} ==> r2c3 <> 9

nrc-chain[4] n9{r4c3 r6c1} - n5{r6c1 r5c1} - n5{r5c9 r4c9} - n6{r4c9 r4c8} ==> r4c8 <> 9

hidden-single-in-a-row ==> r4c3 = 9

nrczt-whip-rn[7] n9{r7c9 r7c8} - n9{r1c8 r1c1} - n1{r1c1 r1c2} - n1{r7c2 r7c6} - n5{r7c6 r7c5} - n5{r3c5 r3c4} - {n9r3c4 .} ==> r2c9 <> 9

;;; end common part

A: nrczt-whip-rn[9] n7{r2c7 r5c7} - n7{r6c8 r1c8} - n9{r1c8 r1c1} - n1{r1c1 r9c1} - n1{r9c7 r8c7} - n1{r8c6 r7c6} - n5{r7c6 r7c5} - n5{r3c5 r3c4} - {n9r3c4 .} ==> r2c7 <> 9

B: nrczt-whip-cn[11] n7{r2c7 r1c8} - {n7 n8}r1c6 - n8{r1c3 r5c3} - n8{r5c9 r4c9} - n8{r6c8 r9c8} - n4{r9c8 r7c8} - n9{r7c8 r7c9} - n9{r1c9 r1c1} - n1{r1c1 r1c2} - n3{r8c3 r7c2} - {n3r8c3 .} ==> r2c7 <> 8

C: nrczt-whip-cn[18] {n8 n7}r1c6 - n7{r2c6 r2c7} - n7{r5c7 r5c8} - {n7 n9}r6c8 - n9{r7c8 r7c9} - n9{r1c9 r3c7} - n9{r1c8 r1c1} - n1{r1c1 r1c2} - n2{r1c2 r1c5} - n2{r2c6 r2c3} - n8{r2c3 r5c3} - n8{r5c9 r4c9} - n8{r6c7 r9c7} - n6{r9c7 r8c7} - n3{r8c7 r8c9} - n3{r8c3 r7c3} - n6{r7c3 r9c1} - {n1r9c1 .} ==> r1c8 <> 8

GRID 89 NOT SOLVED. 55 VALUES MISSING.

Notice that the presence of the final very long whip is, as very often, an indication that this puzzle has few nrczt-chains.

Puzzles with SER 9.3 can usually be solved with shorter whips. For examples of such resolution paths for the hardest puzzles in the top1465 collection, see my web pages, in particular:

http://www.carva.org/denis.berthier/HLS/Results-Classif/magictour-top1465-sol.txt2) Using an easy implementation of the T&E procedure (independent of SudoRules), it can be checked that # 89 is solvable by T&E = T&E(ECP+NS+HS).(Indeed, # 89 is one of the 2 puzzles (together with #187, SER 9.4) in the top1465 collection that can't be solved by nrczt-whips but can be solved by nrczt-braids.)

Thanks to my T&E vs braids theorem (see the "abominable T&E" thread, here

http://forum.enjoysudoku.com/viewtopic.php?t=6390), we know that there must be a resolution path with nrczt-braids, but we don't yet have such a path. We could get one from the output of the T&E procedure but, as I explained elsewhere, it would be hard manual work, the path wouldn't be optimised and we wouldn't be able to guarantee any minimality of the braids it uses.

3) Resolution path with nrczt-braids***** SudoRules version 13.7wbis-B2 *****

;;; Path unchanged down to "end common part"

;;; The next two eliminations are done by slightly shorter braids

A': nrczt-braid-bn[8] n9{r1c8 r1c1} - n9{r3c1 r3c4} - n5{r3c4 r3c5} - n5{r7c5 r7c6} - n1{r1c1 r9c1} - n7{r2c7 r5c7} - n1{r5c7 r8c7} - {n1r9c4 .} ==> r2c7 <> 9

B': nrczt-braid-cn[10] n7{r2c7 r1c8} - {n7 n8}r1c6 - n8{r1c3 r5c3} - n8{r9c7 r9c8} - n4{r1c8 r7c8} - n9{r7c8 r7c9} - n9{r1c8 r1c1} - n1{r1c1 r9c1} - {n1 n3}r7c2 - {n3r8c3 .} ==> r2c7 <> 8

;;; Now the two paths diverge completely:

nrczt-braid-cn[11] n9{r7c9 r1c9} - n9{r3c7 r6c7} - n3{r6c7 r5c7} - n3{r5c3 r8c3} - n2{r8c3 r2c3} - n7{r5c7 r2c7} - {n2 n8}r2c6 - {n8 n7}r1c6 - n7{r5c6 r5c8} - n8{r5c9 r6c8} - {n8r5c9 .} ==> r7c9 <> 3

nrczt-braid-cn[10] n6{r4c8 r4c9} - n5{r4c9 r5c9} - n3{r5c9 r8c9} - n7{r5c8 r5c6} - {n7 n8}r1c6 - n8{r5c9 r2c9} - n8{r3c8 r3c2} - {n8 n3}r4c2 - n3{r8c6 r7c6} - {n3r8c3 .} ==> r4c8 <> 7

nrczt-braid-rn[12] n9{r3c7 r6c7} - n8{r9c7 r9c8} - {n9 n7}r6c8 - {n8 n1}r5c8 - {n8 n3}r5c7 - n3{r8c7 r8c9} - n7{r5c8 r5c6} - {n7 n8}r1c6 - {n8 n2}r2c6 - n3{r8c3 r7c3} - n2{r1c5 r9c5} - {n3r9c5 .} ==> r3c7 <> 8

nrct-chain[8] {n7 n6}r2c7 - {n6 n9}r3c7 - n9{r1c9 r1c1} - n1{r1c1 r9c1} - n6{r9c1 r3c1} - {n6 n4}r2c1 - {n4 n8}r1c3 - {n8 n7}r1c6 ==> r2c6 <> 7

hidden-single-in-a-row ==> r2c7 = 7

nrczt-whip-bn[4] n7{r5c8 r5c6} - {n7 n8}r1c6 - n8{r3c4 r3c2} - {n8r6c2 .} ==> r5c8 <> 8

nrczt-braid-rc[9] {n8 n2}r2c6 - n9{r2c4 r3c4} - {n9 n6}r3c7 - {n8 n4}r2c9 - n2{r2c3 r8c3} - n4{r8c9 r8c4} - n6{r8c4 r9c4} - n6{r9c1 r7c3} - {n8r2c3 .} ==> r2c4 <> 8

nrczt-braid-cn[9] {n2 n8}r2c6 - n9{r2c4 r3c4} - {n9 n6}r3c7 - {n8 n4}r2c9 - {n8 n6}r2c3 - n6{r8c3 r9c1} - n6{r9c4 r8c4} - n4{r8c9 r8c3} - {n2r8c3 .} ==> r2c4 <> 2

nrczt-braid-cn[11] n2{r8c3 r2c3} - {n2 n8}r2c6 - n3{r8c9 r9c7} - n8{r9c7 r9c8} - n8{r3c8 r1c9} - n8{r2c3 r5c3} - {n8 n1}r5c7 - n1{r9c8 r7c8} - {n3 n4}r7c2 - n4{r1c3 r1c8} - {n4r1c3 .} ==> r8c3 <> 3

nrczt-whip-cn[9] {n6 n9}r3c7 - n9{r1c9 r1c1} - n1{r1c1 r9c1} - n6{r9c1 r3c1} - n3{r3c1 r3c2} - n3{r7c2 r7c3} - n6{r7c3 r8c3} - n6{r8c7 r9c7} - {n6r9c4 .} ==> r2c9 <> 6

nrczt-whip-rc[3] n6{r2c3 r2c4} - n9{r2c4 r3c4} - {n9r3c7 .} ==> r3c1 <> 6

nrczt-braid-rc[9] n2{r5c4 r5c6} - n2{r2c6 r2c3} - n7{r5c6 r5c8} - n8{r5c3 r1c3} - n8{r3c4 r3c8} - {n8 n9}r6c8 - {n8 n3}r3c2 - n9{r6c7 r3c7} - {n3r3c1 .} ==> r5c4 <> 8

nrczt-braid-rc[10] n1{r1c1 r9c1} - n6{r9c1 r2c1} - {n6 n8}r1c3 - n9{r2c1 r3c1} - n9{r3c7 r6c7} - n4{r2c3 r2c9} - n8{r2c9 r3c8} - {n9 n7}r6c8 - n7{r5c8 r5c6} - {n8r1c6 .} ==> r1c1 <> 4

nrczt-whip-bn[6] n4{r6c5 r5c4} - n2{r5c4 r5c6} - {n2 n8}r2c6 - {n8 n4}r2c9 - n4{r8c9 r8c3} - {n4r1c3 .} ==> r6c2 <> 4

nrczt-braid-rn[8] n4{r7c2 r1c2} - n3{r7c3 r5c3} - n4{r7c8 r9c8} - n4{r9c5 r6c5} - n3{r6c5 r6c7} - n9{r6c7 r3c7} - n9{r1c9 r1c1} - {n1r1c2 .} ==> r7c3 <> 4

nrczt-braid-rc[9] n6{r2c3 r2c4} - n1{r1c1 r9c1} - {n6 n4}r9c4 - n1{r9c2 r1c2} - n4{r1c2 r7c2} - n4{r9c8 r1c8} - n2{r1c8 r1c5} - {n4 n8}r2c9 - {n8r2c6 .} ==> r1c1 <> 6

nrczt-braid-cn[8] n6{r9c1 r2c1} - n6{r4c8 r4c9} - n6{r1c9 r1c5} - n6{r7c9 r7c3} - n3{r7c3 r5c3} - n3{r5c9 r6c7} - n6{r9c7 r3c7} - {n9r6c7 .} ==> r9c8 <> 6

nrczt-braid-rc[9] n4{r5c1 r5c3} - n4{r2c3 r2c9} - n3{r5c3 r7c3} - n6{r9c1 r8c3} - {n6 n3}r8c9 - {n6 n1}r8c7 - {n1 n8}r9c8 - n8{r3c8 r1c9} - {n8r1c3 .} ==> r9c1 <> 4

nrczt-braid-cn[9] n6{r9c1 r2c1} - n2{r9c5 r9c2} - n6{r9c4 r3c4} - n6{r9c7 r8c7} - {n6 n4}r8c3 - n4{r9c2 r1c2} - n1{r1c2 r1c1} - {n6 n9}r3c7 - {n9r3c1 .} ==> r9c5 <> 6

nrczt-whip-rc[10] {n6 n9}r3c7 - n9{r1c9 r1c1} - n1{r1c1 r9c1} - n6{r9c1 r9c7} - n6{r8c9 r8c3} - n2{r8c3 r2c3} - {n2 n8}r2c6 - {n8 n4}r2c9 - n4{r8c9 r8c4} - {n4r9c4 .} ==> r3c4 <> 6

nrczt-whip-cn[8] n2{r1c8 r3c8} - n6{r3c8 r3c5} - n5{r3c5 r3c4} - n8{r3c4 r3c2} - n8{r6c2 r5c3} - n3{r5c3 r7c3} - n6{r7c3 r7c9} - {n6r9c7 .} ==> r1c8 <> 6

;;; Here, in order to make computations faster, I've deactivated braids; there's nothing new after this point.

nrczt-whip-rc[10] {n6 n9}r3c7 - n9{r1c8 r1c1} - n1{r1c1 r1c2} - n1{r9c2 r9c1} - {n1 n4}r9c4 - n4{r9c2 r7c2} - n4{r7c8 r1c8} - n2{r1c8 r1c5} - {n2 n8}r2c6 - {n8r2c9 .} ==> r9c7 <> 6

nrczt-whip-cn[11] {n8 n7}r1c6 - n7{r5c6 r5c8} - {n7 n9}r6c8 - n9{r6c7 r3c7} - n9{r1c9 r1c1} - n1{r1c1 r1c2} - n2{r1c2 r1c5} - n2{r9c5 r9c2} - n4{r9c2 r7c2} - n6{r8c7 r8c3} - {n6r8c7 .} ==> r1c8 <> 8

nrczt-whip-rc[8] n8{r1c9 r3c8} - n8{r3c4 r6c4} - n8{r6c2 r1c2} - n8{r2c3 r2c6} - n2{r2c6 r2c3} - {n2 n3}r3c2 - {n3 n7}r6c2 - {n7r4c2 .} ==> r4c9 <> 8

nrczt-whip-rn[7] n8{r4c2 r5c3} - n8{r5c9 r2c9} - {n8 n2}r2c6 - n2{r1c5 r1c8} - n4{r1c8 r1c9} - n9{r1c9 r1c1} - {n1r1c1 .} ==> r1c2 <> 8

nrczt-whip-rn[11] n3{r5c3 r7c3} - n3{r9c2 r3c2} - {n3 n9}r3c1 - n9{r3c7 r6c7} - n3{r6c7 r6c5} - n3{r9c5 r9c7} - n8{r9c7 r9c8} - {n8 n7}r6c8 - n7{r5c8 r5c6} - n8{r3c4 r1c6} - {n8r3c4 .} ==> r5c1 <> 3

nrczt-whip-rc[11] {n3 n6}r7c3 - {n6 n1}r9c1 - n1{r9c2 r1c2} - n4{r1c2 r9c2} - n2{r9c2 r3c2} - n2{r3c8 r1c8} - n4{r1c8 r7c8} - {n4 n8}r9c8 - n8{r3c8 r3c4} - n5{r7c5 r3c5} - {n5r7c5 .} ==> r7c2 <> 3

nrczt-whip-cn[7] n9{r6c7 r3c7} - n9{r1c8 r1c1} - n1{r1c1 r9c1} - {n1 n3}r9c7 - n3{r9c1 r7c3} - n6{r7c3 r8c3} - {n6r8c7 .} ==> r6c7 <> 8

nrczt-whip-cn[9] {n3 n9}r6c7 - {n9 n6}r3c7 - {n6 n1}r8c7 - {n1 n8}r5c7 - {n8 n7}r6c8 - n7{r5c8 r5c6} - {n7 n8}r1c6 - n8{r1c9 r2c9} - {n8r2c3 .} ==> r9c7 <> 3

interaction block b9 with row r8 for number 3 ==> r8c6 <> 3

nrct-chain[4] {n6 n3}r7c3 - n3{r7c5 r9c5} - n2{r9c5 r9c2} - n2{r8c3 r2c3} ==> r2c3 <> 6

hidden-pairs-in-a-row {n6 n9}r2{c1 c4} ==> r2c1 <> 4

interaction column c1 with block b4 for number 4 ==> r5c3 <> 4

hidden-pairs-in-a-block {n4 n5}{r5c1 r6c1} ==> r6c1 <> 3

x-wing-in-rows n6{r2 r9}{c1 c4} ==> r8c4 <> 6

nrct-chain[4] n4{r2c9 r2c3} - n2{r2c3 r8c3} - {n2 n1}r8c6 - {n1 n4}r8c4 ==> r8c9 <> 4

nrczt-whip-rn[4] {n1 n2}r8c6 - {n2 n4}r8c4 - {n4 n6}r8c3 - {n6r9c1 .} ==> r9c4 <> 1

xyzt-chain[5] {n6 n3}r8c9 - {n3 n5}r4c9 - {n5 n8}r5c9 - {n8 n3}r5c3 - {n3 n6}r7c3 ==> r7c9 <> 6

nrczt-whip-rn[5] n5{r7c5 r7c6} - n3{r7c6 r7c3} - n6{r7c3 r7c8} - n6{r8c9 r8c3} - {n4r8c3 .} ==> r7c5 <> 4

nrct-chain[5] {n8 n2}r2c6 - n2{r3c5 r9c5} - n4{r9c5 r6c5} - {n4 n5}r6c1 - {n5 n8}r6c4 ==> r5c6 <> 8

nrct-chain[5] {n8 n2}r2c6 - n2{r3c5 r9c5} - n4{r9c5 r6c5} - {n4 n5}r6c1 - {n5 n8}r6c4 ==> r4c6 <> 8

interaction column c6 with block b2 for number 8 ==> r3c4 <> 8

swordfish-in-columns n8{r5 r2 r1}{c3 c6 c9} ==> r5c7 <> 8

hidden-single-in-a-column ==> r9c7 = 8

nrct-chain[2] n1{r5c7 r8c7} - n1{r8c6 r7c6} ==> r5c6 <> 1

nrc-chain[3] n1{r5c7 r8c7} - {n1 n2}r8c6 - n2{r8c4 r5c4} ==> r5c4 <> 1

interaction row r5 with block b6 for number 1 ==> r4c8 <> 1

nrc-chain[5] {n7 n8}r1c6 - {n8 n2}r2c6 - {n2 n1}r8c6 - n1{r8c7 r5c7} - {n1 n7}r5c8 ==> r5c6 <> 7

hidden-singles ==> r5c8 = 7, r5c7 = 1

interaction row r8 with block b8 for number 1 ==> r7c6 <> 1

naked-pairs-in-a-block {n3 n6}{r8c7 r8c9} ==> r7c8 <> 6

interaction block b9 with row r8 for number 6 ==> r8c3 <> 6

nrc-chain[4] n3{r3c1 r3c2} - n8{r3c2 r3c8} - {n8 n9}r6c8 - n9{r6c7 r3c7} ==> r3c1 <> 9

naked-single ==> r3c1 = 3

hidden-pairs-in-a-row {n2 n3}r9{c2 c5} ==> r9c5 <> 4

naked and hidden singles

914378526

658912734

327564981

289137465

463295178

571846392

846753219

792481653

135629847