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: 957
Joined: 16 September 2008
Location: Middle England

Re: Braid Analysis

Postby zealot17 » Sun Sep 10, 2017 7:34 am

I don't think this elimination is valid. If you know for sure that 18 travels \ direction then it is okey to remove 8 from r5c8 since placing 8 will cause 3 to be placed r5c8 too. But 18 traveling \ way is not the only case as in the solution it appears it is 47 that travels / way.
Last edited by zealot17 on Sun Sep 10, 2017 10:00 am, edited 1 time in total.
zealot17
 
Posts: 3
Joined: 19 August 2017

Re: Braid Analysis

Postby eleven » Sun Sep 10, 2017 8:45 am

Agreed. From stack 3 alone you cannot eliminate 8 in r5c8.
As the 4th drawback of braid analysis Ruud mentioned "Error Prone".
eleven
 
Posts: 1537
Joined: 10 February 2008

Re: Braid Analysis

Postby David P Bird » Sun Sep 10, 2017 12:10 pm

zealot17 wrote:I don't think this elimination is valid. İf you know for sure that 18 travels \ direction than it is okey to remove 8 from r5c8 since placing 8 will cause 3 to be placed r5c8 too. But 18 traveling \ way is not the only case as in the solution it appears it is 47 that travels / way.

Hi zealot17 and welcome to the forum. I'm impressed that you chose such a difficult topic for your first post, and look forward to your future contributions.

On checking it I find you are right that the elimination is not justified by the chain alone. It leaves the option of the strands in r123c7 being 8\ 24/ when (8)r5c8 could be true.

I can't remember what other input I used to reach that conclusion, but it doesn't matter – it's not included in the justification.

Mischief maker Eleven is also right (for once), it's very easy to slip up using strand node inferences because they are a lot of work and are often forcing so they only work in one direction. The technique is best reserved for manually checking the options when solving simple puzzles without pencil marks.

David PB
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Braid Analysis

Postby zealot17 » Sun Sep 10, 2017 12:44 pm

Hi David,
Thank you for your welcoming post. I am interested in sudoku for a while and I just meet the technique braid analysis. I have seen it for the first from sudopedia and this was the second article I saw that is written for braiding. Even sudopedia there is a missing 2 in second tower.

I am starting to think that this method isn't useful as I used to think. Simply because it requires lots of work and secondly you need to consider too many cases in order to make an elimination that (probably) can be made by easier techniques.

I once made an remarkable elimination with this technique but it required a lot of work and as I said there is probably chains that cam make same job.

May be I can post a case that braiding can make a elimination

Zealot
zealot17
 
Posts: 3
Joined: 19 August 2017

Re: Braid Analysis

Postby eleven » Sun Sep 10, 2017 7:46 pm

David P Bird wrote:Mischief maker Eleven is also right (for once),

Sorry David, there were 2 reasons for my comment.
The one is, that i never had read that before. Probably because i did not appreciate braid analysis.
The other was, that you have not posted for longer time, so i wanted to let the newcomer know, that i share his opinion - didn't know that zealot17 is so firm with that topic.
btw when was i not right ? :)
eleven
 
Posts: 1537
Joined: 10 February 2008

Re: Braid Analysis

Postby David P Bird » Mon Sep 11, 2017 10:19 am

eleven,
Yes I'm not very active with Sudoku now as I've run out of new ideas and don't wish to contribute manually found AIC solutions against those that came from a computer solver or result from forcing or branched chains and possibly have weird and wonderful notations. You earned the 'mischief maker' title back in 2015 when you led me a merry dance on the puzzle for Aug 5th. The 'for once ' comment was my own bit of mischief.
David
.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Braid Analysis

Postby eleven » Wed Sep 13, 2017 8:17 pm

David P Bird wrote:You earned the 'mischief maker' title back in 2015 when you led me a merry dance on the puzzle for Aug 5th.

Old stuff. Still can't see, what was in your mind then.
But though i guess, you know it, let me assure, that i appreciate your contributions.
eleven
 
Posts: 1537
Joined: 10 February 2008


Return to Advanced solving techniques