Braid Analysis

Advanced methods and approaches for solving Sudoku puzzles

Braid Analysis

Postby David P Bird » Fri Dec 04, 2015 12:23 pm

.
I have started slowly exploring when it may be profitable to consider braid patterns to crack tough puzzles and was pleased to find the example that follows. I'm posting it in case any other contributors are looking for a new avenue to explore.

Fundamentals

Within a band of boxes (in a tier or a stack) a particular digit will a repeat in the mini-lines either in the / or \ diagonal directions which can be seen in this example solution grid.

Code: Select all
- - - - - *--------*--------*--------*
\    /389 | 9 8 3  | 7 4 6  | 2 1 5  |
\    /467 | 6 7 4  | 1 5 2  | 9 3 8  |
\    /125 | 1 2 5  | 3 9 8  | 6 7 4  |
- - - - - *--------*--------*--------*
\15  /4   | 5 4 1  | 6 3 9  | 8 2 7  |
\28  /3   | 2 3 8  | 5 1 7  | 4 9 6  |
\69  /7   | 7 6 9  | 2 8 4  | 3 5 1  |
- - - - - *--------*--------*--------*
\4   /16  | 4 1 6  | 9 7 3  | 5 8 2  |
\8   /79  | 8 9 7  | 4 2 5  | 1 6 3  |
\3   /25  | 3 5 2  | 8 6 1  | 7 4 9  |
- - - - - *--------*--------*--------*

On the left of the grid, for each row the digits in the first mini-rows have been split according to the diagonals 'strands' they follow
There are therefore 6 possible strands in a band and there are only two ways the digits may be distributed between them.
1) All 3 digits repeat (or travel) together – known as a rope pattern as in tier 1 (rare)
2) Two digits follow one diagonal and the third follows the opposite one – a braid pattern as in tiers 2 & 3 (common)
No amount of column or row swapping will ever convert one pattern to the other.

The point to note here is that the same pattern applies to all the mini-lines in a band as otherwise some cells would need to hold two digits. Therefore during a solution, if it has been discovered that a pair of digits follow a particular strand, then the parallel strands must also contain repeating pairs.

As a puzzle is being solved this often allows pairs of digits that either must or must not share the same strands to be identified. This is of most help when simple puzzles are being tackled without pencil marks. When pencil marks are being used, the technique is generally far less useful as it most of the information it provides is already obvious. However, for purists it can provide a way to avoid using net methods when an impasse has been reached using linear chains, so it might be considered as a method of Almost last resort.

Example

.8.2..4.3.4.....6.7.....89..3...2.....15.96.....7...1..58.....6.9.....2.2.6..3.4. Ruud 0065
Code: Select all
 *-----------------------*-----------------------*-----------------------*
 | 1569   <8>    59      | <2>    15679  1567    | <4>    57     <3>     |
 | 1359   <4>    2359    | 1389   15789  1578    | 1257   <6>    1257    |
 | <7>    126    235     | 1346   1456   1456    | <8>    <9>    125     |
 *-----------------------*-----------------------*-----------------------*
 | 45689  <3>    4579    | 1468   1468   <2>     | 579    578    4579    |
 | 48     27     <1>     | <5>    348    <9>     | <6>    378    247     |
 | 45689  26     2459    | <7>    3468   468     | 2359   <1>    2459    |
 *-----------------------*-----------------------*-----------------------*
 | 134    <5>    <8>     | 149    2      147     | 1379   37     <6>     |
 | 134    <9>    347     | 1468   145678 145678  | 1357   <2>    1578    |
 | <2>    17     <6>     | 189    15789  <3>     | 1579   <4>    15789   |
 *-----------------------*-----------------------*-----------------------*

(7)r4c3 = (7)r8c3 - (7=1)r9c2 - (1=34)r78c1 - (4=8)r5c1 - (8)r5c8 = (8)r4c8 => r4c8 <> 7
(16)r4c45 = (6)r6c56 - (6=2)r6c2 - (2=7)r5c2 - (7=1)r9c2 - (1=34)r78c1 - (4=8)r5c1 (8)r5c8 = (8)r4c8 => r4c45 <> 8
(6a)r1c1 = (6-1)r3c2 = (1)r9c2 - (1=34)r78c1 - (4=8)r5c1 - (8)r5c8 = (8-5)r4c8 = (5b)r1c8 - (5=9c)r1c3
=> [ab]r1c1 <> 5, [ac]r1c1 <> 9
(7)r4c3 = (7)r8c3 - (7=1)r9c2 - (1=34)r78c1 - (4=8)r5c1 - (8)r5c8 = (8-5)r4c8 = (5)r1c8 - (5=9)r1c3 => r4c3 <> 9
(5)r1c8 = (5-8)r4c8 = (38-2)r5c8,r6c7 = (2)r2c7 => r2c7 <> 5

At this point no further linear chains seem to be available (but I stand to be corrected).

In the grid below the strand candidates are now shown as extra pencil marks above and to the left of the grid. The diagonal symbol separates the candidates that are and aren't locked in the strand. Hence (8) is confined to the \ strand originating in the mini-column c7b3 and continuing through c8b6 & c9b9 and (4) is confined to the / strand c7b3,c9b6,c8b9. The candidates shown are those that occur in all three of the diagonal mini-lines involved.

In stack 3, because (4) and (8) follow different diagonal directions there is the derived inference that it must contain a braid pattern, but which diagonal will contain the digit pairs has yet to be determined.

Code: Select all
                 \367   \124    9\5      3\1468  \4689  \14567   8\17   \579   \237
                 /157  8/46      /23     2/4689  /14567 /1468    4/27  6/579   /1357
               *-----------------------*-----------------------*-----------------------*
89\1     /16   | 16     <8>    59      | <2>    15679  1567    | <4>    57     <3>     |
 4\35    /12   | 1359   <4>    2359    | 1389   15789  1578    | 127    <6>    1257    |
 7\126   /35   | <7>    126    235     | 1346   1456   1456    | <8>    <9>    125     |
               *-----------------------*-----------------------*-----------------------*
  \3459  /3467 | 45689  <3>    457     | 146    146    <2>     | 579    58     4579    |
  \478  1/24   | 48     27     <1>     | <5>    348    <9>     | <6>    378    247     |
  \246   /4589 | 45689  26     2459    | <7>    3468   468     | 2359   <1>    2459    |
               *-----------------------*-----------------------*-----------------------*
  \1458  /1358 | 134    <5>    <8>     | 149    2      147     | 1379   37     <6>     |
  \1379  /1479 | 134    <9>    347     | 1468   145678 145678  | 1357   <2>    1578    |
 2\17   6/17   | <2>    17     <6>     | 189    15789  <3>     | 1579   <4>    15789   |
               *-----------------------*-----------------------*-----------------------*

Using group strand nodes the following chain is possible in stack 3
(18)r456c8a,r89c9,r23c7b, - (24)r12c7c = (2)r23c9 d,r8c7,r6c7e - (3)r6c7f = (3g-8h)r5c8 => [ah]r5c8 <> 8

Each strand node combines the three mini-columns the digits would need to occupy to be true in the strand, so they are all true or false together.
In the first strand node this shows that (18)r456c8a and (18)r23c7b are equivalent.
The mini-columns in the group nodes are ordered so that those on left and right provide the links to the adjacent nodes (this is rather unnatural but it makes the logic easier to follow).
The evidence used to support the links in the chains comes either from the usual pencil marks or from the extra ones showing the strand candidates.

Comments

Anyone who has studied the JExocet pattern will appreciate that many of its derived inferences arise from the braiding strands through the pattern's base cells.

At the simple level Braid Analysis shows that if a pattern has been determined for one strand it will also apply to the others in the same band. The approach used here takes this one step back to explore the effects of possible patterns to see if there are any eliminations that can be made because they would be common to rival patterns.

Braids require a lot of work; firstly the extra pencil marks for the strand candidates must be recorded, and secondly they greatly increase the chaining possibilities to investigate. They are therefore only worth exploring once basic methods have been exhausted and if the braiding patterns for a band appear to be doubly limited. In the case of the example it is the restrictions on the strands through c7b3 and (2) being confined to one of two strands that have been exploited.

When I first explored the approach back in the Eureka days, expecting great things to result, I also produced a shorthand notation system and a number of theorems. Ruud then created a rather elaborate <entry> in Sudopedia, but it turned out that the benefits from it were very limited. The notation used here therefore follows customary practice although it is somewhat longer.

DPB

TAGdpbBraidAnalysis
.
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Return to Advanced solving techniques