## Abominable TRIAL-and-ERROR and lovely BRAIDS

Advanced methods and approaches for solving Sudoku puzzles
999_Springs wrote:I am not very familiar with almost-hidden sets, so could someone please tell me whether this is how they work, and how useful they are?

I believe you've got it correct. Nice loops and AICs are easier, naye much easier, for me to understand using ALSs ... so I would use ALS:r2c12357. Not surprisingly, the eliminations would be identical.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Or work with the hidden triple (469)r2c137 :
triple=>all those eliminations (and others)
not triple=>7r2c7=>all those eliminations (and different others)
In common : all those eliminations.
aran

Posts: 334
Joined: 02 March 2007

Top1465 #2 (SER 9.5) is one of the 3 puzzles (# 2, SER 9.5 - #3, SER 9.6 - #77, SER 9.8) in the top1465 collection that can be solved neither by nrczt-whips nor by nrczt-braids.
It is not in T&E(ECP+NS+HS), i.e. it is not even solvable by nrczt-braids. But it is in T&E(ECP+NS+HS+BI), i.e. it is solvable by grouped-nrczt-braids (not programmed in SudoRules).

First, let's try SudoRules with the usual rules for nrczt-whips (no braids)
***** SudoRules version 13.7w-bis *****
7.8...3.....2.1...5.........4.....263...8.......1...9..9.6....4....7.5...........
hidden-single-in-a-block ==> r6c9 = 3
interaction row r2 with block b3 for number 8 ==> r3c9 <> 8, r3c8 <> 8, r3c7 <> 8
interaction row r2 with block b3 for number 7 ==> r3c9 <> 7, r3c8 <> 7, r3c7 <> 7
interaction block b6 with column c7 for number 8 ==> r9c7 <> 8, r7c7 <> 8, r2c7 <> 8
interaction block b6 with row r5 for number 5 ==> r5c6 <> 5, r5c4 <> 5, r5c3 <> 5, r5c2 <> 5
hidden-pairs-in-a-row {n7 n8}r3{c4 c6} ==> r3c6 <> 9, r3c6 <> 6, r3c6 <> 4, r3c6 <> 3, r3c4 <> 9, r3c4 <> 4, r3c4 <> 3
interaction block b2 with column c5 for number 3 ==> r9c5 <> 3, r7c5 <> 3, r4c5 <> 3

At this point, the PM is:
Code: Select all
`*--------------------------------------------------------------------------------------* | 7        126      8        | 459      4569     4569     | 3        1456     1259     | | 469      36       3469     | 2        34569    1        | 4679     45678    5789     | | 5        1236     123469   | 78       3469     78       | 12469    146      129      | |----------------------------+----------------------------+----------------------------| | 189      4        1579     | 3579     59       3579     | 178      2        6        | | 3        1267     12679    | 479      8        24679    | 147      1457     157      | | 268      25678    2567     | 1        2456     24567    | 478      9        3        | |----------------------------+----------------------------+----------------------------| | 128      9        12357    | 6        125      2358     | 127      1378     4        | | 12468    12368    12346    | 3489     7        23489    | 5        1368     1289     | | 12468    1235678  1234567  | 34589    12459    234589   | 12679    13678    12789    | *--------------------------------------------------------------------------------------*`

And we now have three short whips:

nrczt-whip-cn[4] n2{r9c1 r6c1} - n2{r6c3 r3c3} - n2{r3c7 r7c7} - {n2r7c5 .} ==> r9c2 <> 2
nrczt-whip-cn[4] n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - {n9r4c1 .} ==> r2c9 <> 9
nrczt-whip-rn[6] n7{r9c3 r9c2} - n7{r9c9 r2c9} - n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - {n9r5c6 .} ==> r5c3 <> 7

Details for these three whips:
- the first whip is completely built on number 2. It is a champion of z-candidates: it has 2 additional z-candidates in its first cell, 3 in its second cell, 1 in its third cell:
nrczt-whip-cn[4] n2{r9 r6 r7* r8*}c1 - n2{r6 r3 r5#n2r6c1 r7* r8* r9*}c3 - n2{r3 r7 r9*}c7 - n2{r7 . r6#n2r6c1 r9*}c5 ==> r9c2 <> 2

nrczt-whip-cn[4] n8r2{c9 c8} - n5r2{c8 c5 c9*} - {n5 n9}r4c5 - n9{r4 . r2*}c1 ==> r2c9 <> 9
nrczt-whip-rn[6] n7{r9c3 r9c2 r7c3*} - n7{r9 r2 r5*}c9 - n8r2{c9 c8} - n5r2{c8 c5 c9#n7r2c9} - {n5 n9}r4c5 - n9r5{c6 . c3* c4#n9r4c5} ==> r5c3 <> 7

At this point, the PM is:
Code: Select all
`*--------------------------------------------------------------------------------------* | 7        126      8        | 459      4569     4569     | 3        1456     1259     | | 469      36       3469     | 2        34569    1        | 4679     45678    578      | | 5        1236     123469   | 78       3469     78       | 12469    146      129      | |----------------------------+----------------------------+----------------------------| | 189      4        1579     | 3579     59       3579     | 178      2        6        | | 3        1267     1269     | 479      8        24679    | 147      1457     157      | | 268      25678    2567     | 1        2456     24567    | 478      9        3        | |----------------------------+----------------------------+----------------------------| | 128      9        12357    | 6        125      2358     | 127      1378     4        | | 12468    12368    12346    | 3489     7        23489    | 5        1368     1289     | | 12468    135678   1234567  | 34589    12459    234589   | 12679    13678    12789    | *--------------------------------------------------------------------------------------*`

;;; end common part

nrczt-whip-rc[10] n2{r9c1 r6c1} - n2{r6c5 r9c5} - n1{r9c5 r7c5} - {n1 n8}r7c1 - n8{r4c1 r4c7} - n8{r6c7 r6c2} - n5{r6c2 r9c2} - n7{r9c2 r5c2} - n7{r5c9 r6c7} - {n7r7c7 .} ==> r7c3 <> 2
nrczt-whip-bn[21] n5{r6c2 r9c2} - n5{r9c4 r1c4} - n5{r2c5 r7c5} - {n5 n9}r4c5 - n9{r4c1 r2c1} - n9{r2c5 r1c6} - n6{r1c6 r5c6} - n9{r5c6 r5c3} - n2{r5c3 r5c2} - n7{r5c2 r6c2} - {n7 n6}r6c3 - {n6 n8}r6c1 - {n8 n1}r4c1 - {n1 n2}r7c1 - n2{r9c3 r3c3} - n2{r3c7 r9c7} - n9{r9c7 r3c7} - n6{r3c7 r2c7} - {n6 n3}r2c2 - {n3 n4}r2c5 - {n4r2c3 .} ==> r6c6 <> 5
GRID 2 NOT SOLVED. 62 VALUES MISSING.

From this resolution path, one can see that this puzzle has few chains/whips; this is why a very long one is found (relatively) easily.

Now, let's try with nrczt-whips and nrczt-braids together:
***** SudoRules version 13.7wB-bis *****
Unchanged until "end common part".
nrczt-braid-bn[7] n5{r9c2 r6c2} - n8{r6c2 r8c2} - {n8 n2}r7c1 - n7{r6c2 r5c2} - n1{r9c5 r7c5} - {n1 n7}r7c7 - {n7r6c7 .} ==> r9c2 <> 1
nrczt-braid-bn[9] n2{r9c1 r6c1} - n2{r6c5 r9c5} - n1{r9c5 r7c5} - {n1 n8}r7c1 - n8{r9c2 r6c2} - n5{r6c2 r9c2} - n7{r9c2 r5c2} - {n1 n7}r7c7 - {n7r6c7 .} ==> r7c3 <> 2

Unfortunately, I can't go further with the current non optimised implementation of braids in SudoRules, because it leads to memory overflow.
It is already a miracle that a braid of length 9 is found (usually, memory overflow occurs much before this. But this puzzle has few chains and relatively few braids).

These two braids are interesting for two reasons.
Firstly, they are much shorter than those we could get indirectly from a T&E procedure. This illustrates the difference between using T&E and looking for braids.
Secondly, they have few branching points, as shown by the details below:
- the first braid is moderately short and it has two branching points (indicated by ".." instead of "-"):
nrczt-braid-bn[7] n5{r9 r6}c2 - n8{r6 r8}c2 - {n8 n2 n1*}r7c1 .. n7{r6 r5 r9*}c2 .. n1{r9 r7}c5 - {n1 n7 n2#n2r7c1}r7c7 - n7{r6c7 . r45c7#n7r7c7 r5c89#n7r5c2} ==> r9c2 <> 1
- the second braid, although it is longer, has only one branching point, just before the end:
nrczt-braid-bn[9] n2{r9 r6 r7* r8*}c1 - n2{r6 r9 r7*}c5 - n1{r9 r7}c5 - {n1 n8 n2*}r7c1 - n8{r9 r6 r8#n8r7c1}c2 - n5{r6 r9}c2 - n7{r9 r5 r6#n8r6c2}c2 .. {n1 n7 n2*}r7c7 - n7{r6c7 . r45c7#n7r7c7 r5c89#n7r5c2} ==> r7c3 <> 2

The constraint that, in SudoRules, we look for short braids before longer ones is enough to avoid useless branches in the braids that lead to an elimination.
(Unfortunately from the programming POV, it is not enough to avoid many useless partial braids with useless branches).
Last edited by denis_berthier on Sun Nov 23, 2008 3:49 pm, edited 2 times in total.
denis_berthier
2010 Supporter

Posts: 3970
Joined: 19 June 2007
Location: Paris

Denis,

As I was looking at your last grid, I came across a couple of eliminations that makes me think something is amiss. I refer to the point you call "end of common" where you branch into the long whips or the braids. At this point, I find two rather simple eliminations that I think either whips or braids would find. They are the size of whip[5].

One of them, 9r2c7 is about the same as 9r2c9 ,which you removed with a whip[4], so I think something is out of whack. Otherwise it makes an interesting story.

Code: Select all
`Elimination r2c7<>9 (notation is RCN)======================+--------------------------------------------------------------------------------------+  | 7        126      8        | 459      4569     4569     | 3        1456     1259     |  | 46(9)    36       3469     | 2        3469(5)  1        | 469(7)   46(578)  (578)    |  | 5        1236     123469   | 78       3469     78       | 12469    146      129      |  +--------------------------------------------------------------------------------------+  | 18(9)    4        1579     | 3579     (59)     3579     | 178      2        6        |  | 3        1267     1269     | 479      8        24679    | 147      1457     157      |  | 268      25678    2567     | 1        2456     24567    | 478      9        3        |  +--------------------------------------------------------------------------------------+  | 128      9        12357    | 6        125      2358     | 127      1378     4        |  | 12468    12368    12346    | 3489     7        23489    | 5        1368     1289     |  | 12468    135678   1234567  | 34589    12459    234589   | 12679    13678    12789    |  +--------------------------------------------------------------------------------------+     5c5  2n8  2n9  9r4  2n7  9r27R2:      728==729=======727                  |    |         |5R2: 525==528==529        |      |    |    |         |8R2:  |   828==829        +---p279 = eliminate      |                        |4N5: 545============945        |                     |         |9C1:                941=======921  Elimination r5c6<>7 (notation is RCN)======================     4n7  6n7  6n5  6n6  5n6  7r57B6: 747==767=================757      |    |                  758        |    |                  759        |    |                   |8C7: 847==867                  |           |              +---p567 = eliminate4R6:      467==465==466   |                |    |    |2B5:           265==266==256                       |    |    |        6B5:           665==666==656 `
Allan Barker

Posts: 266
Joined: 20 February 2008

Denis
Code: Select all
`*--------------------------------------------------------------------------------------* | 7        126      8        | 459      4569     4569     | 3        1456     1259     | | 469      36       3469     | 2        34569    1        | 4679     45678    5789     | | 5        1236     123469   | 78       3469     78       | 12469    146      129      | |----------------------------+----------------------------+----------------------------| | 189      4        1579     | 3579     59       3579     | 178      2        6        | | 3        1267     12679    | 479      8        24679    | 147      1457     157      | | 268      25678    2567     | 1        2456     24567    | 478      9        3        | |----------------------------+----------------------------+----------------------------| | 128      9        12357    | 6        125      2358     | 127      1378     4        | | 12468    12368    12346    | 3489     7        23489    | 5        1368     1289     | | 12468    1235678  1234567  | 34589    12459    234589   | 12679    13678    12789    | *--------------------------------------------------------------------------------------*`

And we now have three short whips:

nrczt-whip-cn[4] n2{r9c1 r6c1} - n2{r6c3 r3c3} - n2{r3c7 r7c7} - {n2r7c5 .} ==> r9c2 <> 2
nrczt-whip-cn[4] n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - {n9r4c1 .} ==> r2c9 <> 9
nrczt-whip-rn[6] n7{r9c3 r9c2} - n7{r9c9 r2c9} - n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - {n9r5c6 .} ==> r5c3 <> 7

Details for these three whips:
- the first whip is completely built on number 2. It is a champion of z-candidates: it has 2 additional z-candidates in its first cell, 3 in its second cell, 1 in its third cell:
nrczt-whip-cn[4] n2{r9 r6 r7* r8*}c1 - n2{r6 r3 r5#n2r6c1 r7* r8* r9*}c3 - n2{r3 r7 r9*}c7 - n2{r7 . r6#n2r3c3 r9*}c5 ==> r9c2 <> 2

Just to be clear, do you agree that r3c3 in bold above should be r6c1 ?

I recently said that the manual solver could approach nrczt-whips in the following way :
- choose the target (candidate), target cell, and starting cell
- mentally remove the target from all cells seen by the target cell other than start cell
- then if there is an xyt chain leading to an empty cell (from which a target cell was removed) => eliminate target.
I see that slight modification is required :
- t candidates can be internal or external to the cells in the chain. I'll use t° for external candidates
- empty cell or empty unit (ie void of a candidate).

Illustration for the first nrczt-whip above :
- target=2 in r9c2, start cell = r9c1 or r8c1 or r7c1. Use r9c1.
- remove 2 from all cells seen by r9c2 except r9c1 : <2> : r78c1, r789c3, r1358c2, r9c5679.
Then we have the following xyt chain with 2 t° candidates :

2 : r9c1=r6c1-r6c3=r3c3(r5c3#r6c1)-r3c7=r7c7-r7c5=>(r6c5#r6c1) c5 void 2
=> r9c2 <2>.

Aside from the fact that the manual solver will probably not want to work outside rc space, he will have greater potential in rc for his xyt chains since he does not have the dual restrictions of cn, rn space ie :
- he can use boxes
- for ordered right-link candidates he can switch between rows and columns.
aran

Posts: 334
Joined: 02 March 2007

aran wrote:Just to be clear, do you agree that r3c3 in bold above should be r6c1 ?

Yes, thanks, I've just corrected in my post.
Additional candidates are not output by SudoRules and I have made an error in adding that one.
aran wrote:Aside from the fact that the manual solver will probably not want to work outside rc space,

The "manual solver" is constantly working out of rc-space when he considers conjugate candidates - that's what rn, cn and bn spaces are used for.

For the rest of your post, the 2D counterpart of nrczt-chains or whips is xyzt-chains, that I've described long ago in my book and in another thread.
Last edited by denis_berthier on Sun Nov 23, 2008 1:33 am, edited 1 time in total.
denis_berthier
2010 Supporter

Posts: 3970
Joined: 19 June 2007
Location: Paris

Allan Barker wrote:As I was looking at your last grid, I came across a couple of eliminations that makes me think something is amiss. I refer to the point you call "end of common" where you branch into the long whips or the braids. At this point, I find two rather simple eliminations that I think either whips or braids would find. They are the size of whip[5].
One of them, 9r2c7 is about the same as 9r2c9 ,which you removed with a whip[4], so I think something is out of whack. Otherwise it makes an interesting story.

I can't see any whip or braid. Which sequences of candidates are you considering?
denis_berthier
2010 Supporter

Posts: 3970
Joined: 19 June 2007
Location: Paris

denis_berthier wrote:
Allan Barker wrote:As I was looking at your last grid, I came across a couple of eliminations that makes me think something is amiss. I refer to the point you call "end of common" where you branch into the long whips or the braids. At this point, I find two rather simple eliminations that I think either whips or braids would find. They are the size of whip[5].
One of them, 9r2c7 is about the same as 9r2c9 ,which you removed with a whip[4], so I think something is out of whack. Otherwise it makes an interesting story.

I can't see any whip or braid. Which sequences of candidates are you considering?

The two short chains in the code block of my post, one for r2c7<>9 and one for r5c6<>7. Both are length 5. For sure one must be a small whip and they are both easy eliminations. I posted them as diagrams as my notation abilities are not so good. I have double checked the grids and they are the same.
Allan Barker

Posts: 266
Joined: 20 February 2008

Allan Barker wrote:
denis_berthier wrote:
Allan Barker wrote:As I was looking at your last grid, I came across a couple of eliminations that makes me think something is amiss. I refer to the point you call "end of common" where you branch into the long whips or the braids. At this point, I find two rather simple eliminations that I think either whips or braids would find. They are the size of whip[5].
One of them, 9r2c7 is about the same as 9r2c9 ,which you removed with a whip[4], so I think something is out of whack. Otherwise it makes an interesting story.

I can't see any whip or braid. Which sequences of candidates are you considering?

The two short chains in the code block of my post, one for r2c7<>9 and one for r5c6<>7. Both are length 5. For sure one must be a small whip and they are both easy eliminations. I posted them as diagrams as my notation abilities are not so good. I have double checked the grids and they are the same.

But the question is precisely: are they chains/whips/braids, i.e. are they linearly ordered? Your diagrams display nets, not sequences of candidates.
It's not a matter of notation. Could you simply write the sequence of candidates you're considering - in whichever notation you want, but a sequence?
denis_berthier
2010 Supporter

Posts: 3970
Joined: 19 June 2007
Location: Paris

Using GEM to track families of AICs and picking out linear deduction paths (the only branching allowed is within known patterns) I get this solution for 1465#2:
(Abbreviations: AHT = Almost Hidden Tuple, ANT = Almost Naked Tuple)

Code: Select all
`-|----------------------------|----------------------------|----------------------------| | 7        126      8        | 459      4569     4569     | 3        1456     1259     |  | 469      36       3469     | 2        34569 d  1        | 4679 f   45678 e  5789 e   |  | 5        1236     123469   | 78       3469     78       | 12469    146      129      | -|----------------------------|----------------------------|----------------------------| | 189      4        1579     | 3579     59 c     3579     | 178 g    2        6        |  | 3        1267! a  1267!9 a | 479 b    8        2467!9 a | 147 g    1457 h   157 h    |  | 268      25678    2567     | 1        2456     24567    | 478 g    9        3        | -|----------------------------|----------------------------|----------------------------| | 128      9        12357    | 6        125      2358     | 127      1378     4        |  | 12468    12368    12346    | 3489     7        23489    | 5        1368     1289     |  | 12468    1235678  1234567  | 34589    12459    234589   | 12679    13678    12789    | -|----------------------------|----------------------------|----------------------------|`

(269)AHT:r5c236 = (9)r5c4 - (9=5)r4c5 - (5)r12c5 = (58-7)AHT:r2c89 = (7)r2c7 - (7)r456c7 = (7)r5c89 => r5c236 <> 7
(57)HiddenPair:r69c2 => r6c2<>268, r9c2<>12368
Single r8c2 = 8
(3)LineBox:c2b1 => r23c3 <> 3

Code: Select all
`-|-------------------------------|-------------------------------|-------------------------------| | 7         126       8         | 459       45!69     4569      | 3         1456      1259      |  | 469       36        469       | 2         34569 e   1         | 4679 c    4!56!78 d 5789! d   |  | 5         1236      12469     | 78        3469      78        | 12469     146       129       | -|-------------------------------|-------------------------------|-------------------------------| | 189       4         1579      | 3579      5!9       3579      | 17!8      2         6         |  | 3         126       1269      | 479       8         2469      | 147!      1457      157       |  | 268       57        2567      | 1         245!6     24567     | 47!8      9         3         | -|-------------------------------|-------------------------------|-------------------------------| | 12 a      9         1!2!357   | 6         125 a     2!358     | 127 b     1!378     4         |  | 1246      8         12346     | 349       7         2349      | 5         136       129       |  | 1246      57        1234567   | 34589     1245!9    234589    | 1267!9    13678     12789     | -|-------------------------------|-------------------------------|-------------------------------|`

(5)r7c5 = (12)ANT:r7c15 - (1|2=7)r7c7 - (7)r2c7 = (78-5)AHT:r2c89 = (5)r2c5 - Loop
=>r7c38<>1, r7c36<>2, r1469 <>5, r2c8 <> 46, r2c9 <>9, r4569c7 <> 7

The puzzle now collapses with simple methods.
David P Bird
2010 Supporter

Posts: 1043
Joined: 16 September 2008
Location: Middle England

denis_berthier"][quote="Allan Barker wrote:I refer to the point you call "end of common" where you branch into the long whips or the braids. At this point, I find two rather simple eliminations that I think either whips or braids would find.

Sorry, My examples are only to show that the candidates are easy to remove. My question is why would you not find and eliminate these candidates before proceeding with much larger whips or longer braids?

As far as recognizing proper sequences of candidates, I would trust you long before I trusted my self.
Allan Barker

Posts: 266
Joined: 20 February 2008

Allan Barker wrote:
Allan Barker wrote:I refer to the point you call "end of common" where you branch into the long whips or the braids. At this point, I find two rather simple eliminations that I think either whips or braids would find.

Sorry, My examples are only to show that the candidates are easy to remove. My question is why would you not find and eliminate these candidates before proceeding with much larger whips or longer braids?

The answer is simple: whips and braids don't find these eliminations because these patterns are neither whips not braids (at least not the simple nrczt ones; they may be braids with inserts but I wasn't looking for that). I wasn't looking for nets, but only for whips or braids.
denis_berthier
2010 Supporter

Posts: 3970
Joined: 19 June 2007
Location: Paris

I get the same insertion as you David, although by foul means !

If we remove a given clue from this puzzle say the 4 @ r7c9, we get a subpuzzle with more than 1 solution.

The "real" pm board of this subpuzzle [as opposed to the above "virtual" board] reveals many eliminations.

In particular the 8 @ r8c2 can be inserted !.

Does this indicate or confirm a [or the] weak spot in this puzzle ?

C
coloin

Posts: 2380
Joined: 05 May 2005
Location: Devon

denis_berthier wrote:
aran wrote:Aside from the fact that the manual solver will probably not want to work outside rc space,

The "manual solver" is constantly working out of rc-space when he considers conjugate candidates - that's what rn, cn and bn spaces are used for.

For the rest of your post, the 2D counterpart of nrczt-chains or whips is xyzt-chains, that I've described long ago in my book and in another thread.

1. I understand all of that entirely.
2. xyzt-chains are not a 2D counterpart of whips : your book "of long ago" presents xyzt chains with a single z candidate, and so does not deal with whips, even if the extension is in effect obvious.
3. The point of my post was to illustrate how in practice a manual solver might look for whip eliminations.
aran

Posts: 334
Joined: 02 March 2007

aran wrote:your book "of long ago" presents xyzt chains with a single z candidate, and so does not deal with whips, even if the extension is in effect obvious.

I've introduced the 3D chains and lassos on Eureka and here and then in the second edition of my book.
It's true that the 2D xyzt-chains initially had only one z-candidate, but that's an unjustified limitation. I now consider that the correct definition is the 2D counterpart of the nrczt-chains. And there can also be 2D lassos and whips.

Whips have the theoretical and practical advantage of unifying chains and lassos in a single pattern. But they are nothing really new: whip = chain or lasso.

aran wrote:The point of my post was to illustrate how in practice a manual solver might look for whip eliminations.

But you're limiting this to 2D chains/whips. 3D chains/whips are much more powerful.
The extension is the same as the passage from xy-chains to Nice Loops.
denis_berthier
2010 Supporter

Posts: 3970
Joined: 19 June 2007
Location: Paris

PreviousNext