The New Sudoku Players' Forum

[MrHamilton]

So r3c3<>2 by contradiction? I thought braid analysis was 100% direct deduction, without an elimination-by-contradiction component.

It gives focus to any search for contradictions, at least.
I don't use the rigorous approach shown in the sudopedia article, which is effective but tedious.
I use a hybrid approach which allows for other methods to fill in the gaps.
There is no easy established way (yet) of deducing the pattern. The main thing is to recognize it and gradually fill it in however you wish to do that, until enough information is known to solve.
It is also possible to work with "travelling pair cells" i.e. cell which must contain a traveler, though it's not narrowed down to a specific digit yet, or again with cells which are forced to be single, in the context of a stack or band. A small vertical line in the cell may be used to indicate a vertical traveller (in a stack) and a horizontal line for one in a band. This occasionally helps establish a pattern. A trick to remember is that if two digits in a segment don't travel with each other, the third digit is definitely a traveler.

My side notation is similar to Condor's with a line dividing the list but I have N's where he has Z's and I simply put an N or Z at the top or side where he might use backslashes or forward slashes.

[Condor]

Wow. After this thread being ' in the bottom of the draw collecting dust' so to speak, it has finally come to life.

As an aside.

I have been preparing a post for David Bird in his forum, and decided to look back at the postings in the Su-Doku's Maths thread.

When I came to Frazers posting, I realised that his calculations were similar to mine in the second half of my earlier posting here.

Both contains the germ of the idea for Braid Analysis - that numbers in a triplet can occur in some order. The difference being that I used XXX YYY ZZZ for the top row and he stuck with numbers.

I remember reading through quite a few pages of that thread at the time, but don't remember his standing out. I must have read his posting and probably absorded something from it.

In a private message he said

Anyway, while you may be right to say that the nub of the idea of braid analysis is already present in my early post, I certainly didn't envisage it as part of a solution technique, only as part of an enumeration technique, so I don't think that I deserve any credit for this! Thanks for bringing it to my attention, though -- I'll have to think a little more about it now!

A summary of those calculations (in a bit tidier form) are:

Code: Select all

XXX YYY ZZZ | 987 654 321
ZZZ XXX YYY | 321 321 321
YYY ZZZ XXX | 321 321 321

The top row is just 9! and the next 2 rows are 6 triplets of 3!. So that equals 9! * 6^6.

The other one is

Code: Select all

XXQ YYR ZZS |  987  654  321
ZZR XXS YYQ | 3321 3321 3321
YYS ZZQ XXR |  321  321  321

The first extra 3 is the 3 possibilities for R, the second extra 3 is the 3 possibilities for S, and the third is for Q. So that equals 9! * 6^6 * 27, and the whole lot equalling 9! * 6^6 * 56.

[Condor]

I use a hybrid approach which allows for other methods to fill in the gaps.

...

My side notation is similar to Condor's with a line dividing the list but I have N's where he has Z's and I simply put an N or Z at the top or side where he might use backslashes or forward slashes.

Thanks MrHamilton for holding down the fort. I'm still catching up with all the things that other people have developed from this discovery. David Birds stuff takes a while to assimulate. I am having a close look ravels question.



I have been on a different timeline to most other people with this.

When I first started using this technique I thought that this must be the weirdest solving technique arround. I have got used to it since then.

Maybe I should have said I used method 1. I looked up my old photocopies of puzzles from the newspaper, (I have a growing pile of them) and saw that I was noting the pairs and singles on 17/6/2005. I started using method 1 on the 22nd. The first time I used it, it was a little different and found it a bit harder to check things, so that was changed the next day.

The last time I used method 1 appears to be 12/4/2006. I have just been using method 2 since then. It has been sufficient for the ones in the paper by Pappacom.

My /'s are the same as the Z's and the \'s as the N's. I just came up with my notation before David Bird did. I think he chose those letters because they have slashes in the middle.

It really helps when people post a reply about something they don't understand.

To be honest, i never was interested in your method. You show some samples, that can be solved with singles only and make complicated notations and conclusions. When i remember right, Mr.Hamiltons traveling pairs only found eliminations, that are catched by singles and locked candidates also. So what is the purpose of your analysis ?

My postings aren't meant to be a comparision of solving techniques. I have often found the number for a cell only to find when rechecking that I could have found it by an easier technique.

Easy's often have several ways of identifing the correct number for a cell. Because I have used puzzles for my examples from programs that have been developed with other techniques in mind, that will always happen. In my second posting in this thread, I knew that alternate methods could be seen quite easily for the first example. I decided to use that example anyway because people could then see that this method did produce the same results. I tried to find an example where it was harder to see those techniques for the second example.

My side notation does help with checking the puzzle is correct when it is finished. I posted how to do that here.

1 last thing. From time to time this technique enables you to insert several numbers into the puzzle at once.

From noticing 1 number I was able to place 8 numbers straight into the grid.

Here I noticed 7 could be placed in r6c8 and 2 then went in r6c9, and then identified triples so was immediately able to place another 6 numbers. Then with updating my notes saw the singles in the middle stack, so was able to identify all the pairs and remaing single for that stack. With that information another 11 numbers were entered into the grid. Can you do that with other techniques you are using?

[ronk]

Using only a direct deduction based on braid analysis (traveling pairs/triples), what is the next placement for the puzzle below?

Code: Select all

 . . 5 | 1 6 . | . . .
 6 . . | . 7 3 | . . .
 3 . . | . . 5 | 7 . 6
-------+-------+-------
 . . . | . 3 . | 6 9 1
 1 3 9 | 7 5 6 | 4 8 2
 8 6 2 | 4 9 1 | . . 7
-------+-------+-------
 4 . 1 | . . . | . . 5
 . . . | 5 . . | . . 8
 . . . | . . 7 | 2 . .

Direct deduction means no elimination-by-contradiction.

[With only one naked pair step, it's an easy puzzle using pencilmarks.]

[MrHamilton]

Using only a direct deduction based on braid analysis (traveling pairs/triples), what is the next placement for the puzzle below?

Code: Select all

 . . 5 | 1 6 . | . . .
 6 . . | . 7 3 | . . .
 3 . . | . . 5 | 7 . 6
-------+-------+-------
 . . . | . 3 . | 6 9 1
 1 3 9 | 7 5 6 | 4 8 2
 8 6 2 | 4 9 1 | . . 7
-------+-------+-------
 4 . 1 | . . . | . . 5
 . . . | 5 . . | . . 8
 . . . | . . 7 | 2 . .

Direct deduction means no elimination-by-contradiction.

[With only one naked pair step, it's an easy puzzle using pencilmarks.]

3 and 6 must go in some order in r8c3 and r9c3 (N travellers), then 7 must go into r4c3 as it is the only place left in the third column.
That's the first one that jumps out at me at any rate. Then 5 travels with 8 in the left stack, and away we go.
By elimination-by-contradiction you mean forcing chains, nice loops and the like. true?

[ravel]

3 and 6 must go in some order in r8c3 and r9c3 (N travellers), then 7 must go into r4c3 as it is the only place left in the third column.

Nice sample for a direct hidden pair

Then 5 travels with 8 in the left stack, and away we go.

You get the 5's (and a 9) in stack one, but then i need another pair.

[ronk]

3 and 6 must go in some order in r8c3 and r9c3 (N travellers), then 7 must go into r4c3 as it is the only place left in the third column.

I'm having a tough time accepting that as braid analysis.

Then 5 travels with 8 in the left stack, and away we go.

Code: Select all

 . . 5 | 1 6 . | . . .
 6 . . | . 7 3 | . . .
 3 . . | . . 5 | 7 . 6
-------+-------+-------
 5 4 7 | . 3 . | 6 9 1
 1 3 9 | 7 5 6 | 4 8 2
 8 6 2 | 4 9 1 | . . 7
-------+-------+-------
 4 . 1 | . . . | . . 5
 . . . | 5 . . | . . 8
 9 5 . | . . 7 | 2 . .

r7c2=8 seems a much better example of braid analysis than r4c3=7 above.

By elimination-by-contradiction you mean forcing chains, nice loops and the like. true?

I was referring to your recent r3c2<>2 post.

[MrHamilton]

3 and 6 must go in some order in r8c3 and r9c3 (N travellers), then 7 must go into r4c3 as it is the only place left in the third column.

Nice sample for a direct hidden pair

Then 5 travels with 8 in the left stack, and away we go.

You get the 5's (and a 9) in stack one, but then i need another pair.

N is the general direction of travel in the left stack, and it is a braid not a rope. There's a 48 naked pair (and they can't travel with each other) in the third column, along with the 36 pair (which do travel) and the lone 7. Once I get r4c1 r4c2 r4c3, it becomes clear that 5 goes with 8.
As far as ronk's difficulty is concerned, surely seeing where a braid must exist, and (formally or informally) analyzing it, and its implications, is an example of Braid analysis.
At least as I understand the term. You are, I think, trying to narrow the discussion of the technique down to a particular implementation of it, whereas it can be used in many different ways and situations.

[ravel]

Once I get r4c1 r4c2 r4c3, it becomes clear that 5 goes with 8.

You are free to reinvent the wheel. For me the 8 has to go to r7c2 because of the (direct) hidden pair 36 in r89c3, not because 5 goes with 8.

[Added:] Please dont misunderstand me, i dont critizise your way of solving. I just wanted to find out, what Braid methods can do more than basics.

[MrHamilton]

Once I get r4c1 r4c2 r4c3, it becomes clear that 5 goes with 8.

You are free to reinvent the wheel. For me the 8 has to go to r7c2 because of the (direct) hidden pair 36 in r89c3, not because 5 goes with 8.

[Added:] Please dont misunderstand me, i dont critizise your way of solving. I just wanted to find out, what Braid methods can do more than basics.

Of course.
But I am afraid that the last example sheds no new light on this question one way or the other, as it is easily solved with or without braids.
In the Sudopedia example however, Simple Sudoku gets stuck, but the braiding methods make progress, either in the laborious charting way, or the rough and ready "let's refute triples hypothesis" way.

[ronk]

But I am afraid that the last example sheds no new light on this question one way or the other, as it is easily solved with or without braids.

I posted that "easy" puzzle to see if braid analysis was an alternative to techniques over and above singles and locked candidates.

Judging from your solution, it's not an alternative to locked sets (pairs, triples, etc.), but it may make them easier to find.

[ravel]

In the Sudopedia example however, Simple Sudoku gets stuck, but the braiding methods make progress, either in the laborious charting way, or the rough and ready "let's refute triples hypothesis" way.

Really ? My question, if Braid analysis could continue, where Simple Sudoku gets stuck, was never answered other than by your solution, that definitely used a contradiction chain.
I wanted to save the time to study the article for hours to find out, what "Remaining digits 3 and 6 can now be fixed in strands 4Z and 6Z" means, when at the end "non chaining" Braid analysis is stuck with this puzzle too.
So i only can repeat my question:

Code: Select all

 . . 5 | . 9 . | . . .
 . . 4 | 5 7 . | . . .
 6 9 . | 8 4 . | . 3 5
-------+-------+-------
 . . 1 | . 8 7 | . . .
 4 7 . | 1 5 . | 8 2 .
 . . . | 4 6 . | 5 7 1
-------+-------+-------
 3 . . | . 1 4 | . 5 8
 . 4 . | . 3 . | 2 1 .
 1 . 9 | . 2 . | 3 . .

Can the technique described in Sudopedia solve this puzzle (and i read nothing about contradiction chains there) ?

[MrHamilton]

Remember that you asked for this!
Readers, feel free to skip ahead to the last few paragraphs.
Simple Sudoku gets us this far:

Code: Select all

 *-----------*
 |..5|.9.|...|
 |..4|57.|...|
 |69.|84.|.35|
 |---+---+---|
 |..1|.87|...|
 |47.|15.|82.|
 |...|46.|571|
 |---+---+---|
 |3..|.14|.58|
 |.4.|.3.|21.|
 |1.9|.2.|3..|
 *-----------*


 *-----------*
 |..5|.9.|...|
 |..4|57.|...|
 |69.|84.|.35|
 |---+---+---|
 |..1|.87|...|
 |47.|15.|82.|
 |...|46.|571|
 |---+---+---|
 |3..|.14|.58|
 |.4.|.3.|21.|
 |1.9|.2.|3..|
 *-----------*

 
 *-----------------------------------------------------------*
 | 278   13    5     | 23    9     236   | 1467  468   2467  |
 | 28    13    4     | 5     7     1236  | 169   689   269   |
 | 6     9     27    | 8     4     12    | 17    3     5     |
 |-------------------+-------------------+-------------------|
 | 259   256   1     | 23    8     7     | 469   469   3469  |
 | 4     7     36    | 1     5     39    | 8     2     369   |
 | 29    28    238   | 4     6     239   | 5     7     1     |
 |-------------------+-------------------+-------------------|
 | 3     26    267   | 679   1     4     | 679   5     8     |
 | 57    4     678   | 679   3     58    | 2     1     679   |
 | 1     58    9     | 67    2     58    | 3     46    467   |
 *-----------------------------------------------------------*


"no hint available"

Here's a suitable blank template we may start with:

Code: Select all

Tower N Strands
1N   1   2   3   4   5   6   7   8   9
2N   1   2   3   4   5   6   7   8   9
3N   1   2   3   4   5   6   7   8   9
4N   1   2   3   4   5   6   7   8   9
5N   1   2   3   4   5   6   7   8   9
6N   1   2   3   4   5   6   7   8   9
7N   1   2   3   4   5   6   7   8   9
8N   1   2   3   4   5   6   7   8   9
9N   1   2   3   4   5   6   7   8   9
Floor N Strands
1N   1   2   3   4   5   6   7   8   9
2N   1   2   3   4   5   6   7   8   9
3N   1   2   3   4   5   6   7   8   9
4N   1   2   3   4   5   6   7   8   9
5N   1   2   3   4   5   6   7   8   9
6N   1   2   3   4   5   6   7   8   9
7N   1   2   3   4   5   6   7   8   9
8N   1   2   3   4   5   6   7   8   9
9N   1   2   3   4   5   6   7   8   9
Tower Z Strands
1Z   1   2   3   4   5   6   7   8   9
2Z   1   2   3   4   5   6   7   8   9
3Z   1   2   3   4   5   6   7   8   9
4Z   1   2   3   4   5   6   7   8   9
5Z   1   2   3   4   5   6   7   8   9
6Z   1   2   3   4   5   6   7   8   9
7Z   1   2   3   4   5   6   7   8   9
8Z   1   2   3   4   5   6   7   8   9
9Z   1   2   3   4   5   6   7   8   9
Floor Z Strands
1Z   1   2   3   4   5   6   7   8   9
2Z   1   2   3   4   5   6   7   8   9
3Z   1   2   3   4   5   6   7   8   9
4Z   1   2   3   4   5   6   7   8   9
5Z   1   2   3   4   5   6   7   8   9
6Z   1   2   3   4   5   6   7   8   9
7Z   1   2   3   4   5   6   7   8   9
8Z   1   2   3   4   5   6   7   8   9
9Z   1   2   3   4   5   6   7   8   9


Now the same chart filled out after analysis, where * indicates a strand placement, and 0 means no strand placement,

and the rest strand candidates:

Code: Select all

Tower N Strands
1N   0   2   0   0   0   6   7   8   0
2N   1*   0   3*   0   0   0   0   0   0
3N   0   2   0   4*   5   0   0   0   0
-------------------------------------------------------------------------
4N   0   0   0   0   5*   0   0   8*   0
5N   0   0   0   0   0   0   7*   0   9*
6N   1*   2   3   0   0   0   0   0   0
-------------------------------------------------------------------------
7N   0   0   0   4   0   6   7   0   9
8N   0   0   3*   0   0   6   0   0   9
9N   0   0   0   4   5*   6   0   0   0

Floor N Strands
1N   1   0   3   0   5*   0   7   0   0
2N   1   2   0   4*   0   0   0   8   0
3N   0   2   0   0   0   6   0   0   9*
-------------------------------------------------------------------------
4N   1*   0   0   0   5*   0   0   0   0
5N   0   0   3   4*   0   6   0   0   0
6N   0   2   3   0   0   0   0   8*   9
-------------------------------------------------------------------------
7N   0   0   3*   0   0   6   7   0   0
8N   0   0   0   0   5   6   7   8   0
9N   1*   0   0   0   0   0   0   0   9

Tower Z Strands
1Z   0   2   0   0   0   6   0   8   0
2Z   0   0   0   0   0   0   0   0   9*
3Z   0   0   0   0   5   0   7   0   0
-------------------------------------------------------------------------
4Z   0   2   3   0   0   0   0   0   0
5Z   0   0   0   4*   0   0   0   0   0
6Z   0   0   0   0   0   6*   0   0   0
-------------------------------------------------------------------------
7Z   1*   0   0   4   0   6   0   0   0
8Z   0   0   0   4   0   6   0   8*   9
9Z   0   2*   0   0   0   6   7   0   9

Floor Z Strands
1Z   1   2   0   0   0   0   0   8   0
2Z   0   0   3   0   0   0   0   8   0
3Z   0   2   0   0   0   6   7   0   0
-------------------------------------------------------------------------
4Z   0   2   0   0   0   6   0   0   9
5Z   0   0   0   0   0   0   7*   0   0
6Z   0   0   3   0   0   0   0   0   9
-------------------------------------------------------------------------
7Z   0   2   0   0   0   6   7   0   0
8Z   0   0   0   4*   0   6   7   0   0
9Z   0   0   0   0   5   0   0   8   9


The rules from the Sudopedia article:

"A pair of digits in one of the intersections in a chute can only appear in 0 or 2 other intersections in that

chute.

This rule is the direct result of the way digits are distributed in a chute. A pair will either repeat in all

boxes [cells] of a chute or not at all.

A pair of digits present in a boxrow can only appear in 0 or 1 boxcol in the tower that contains it.
A pair of digits present in a boxcol can only appear in 0 or 1 boxrow in the floor that contains it.

These rules are based on the fact that within a single box, a certain pair can only exist in a boxrow or a

boxcol, but not in both. The crossing chute will have at least one intersection without that pair. Because there

cannot be 2 pairs of the same digits in a chute, there can only be one or none at all.

A pair of digits which repeats in a floor can only appear in 0 or 1 boxcol in each tower.
A pair of digits which repeats in a tower can only appear in 0 or 1 boxrow in each floor.

A direct extension of the previous rules.

...
A fixed digit in any N strand eliminates the Z-Rope.
A fixed digit in any Z strand eliminates the N-Rope.
2 fixed digits in any N strand eliminates the Z-Braid.
2 fixed digits in any Z strand eliminates the N-Braid."

Code: Select all

 *-----------------------------------------------------------*  N  |  Z
 | 278   13    5     | 23    9     236   | 1467  468   2467  |  4  | 
 | 28    13    4     | 5     7     1236  | 169   689   269   |  9  |
 | 6     9     27    | 8     4     12    | 17    3     5     |  5  |
 |-------------------+-------------------+-------------------|     |
 | 259   256   1     | 23    8     7     | 469   469   3469  |  4  |
 | 4     7     36    | 1     5     39    | 8     2     369   |  8  |
 | 29    28    238   | 4     6     239   | 5     7     1     |  15 |  7
 |-------------------+-------------------+-------------------|     |
 | 3     26    267   | 679   1     4     | 679   5     8     |     |
 | 57    4     678   | 679   3     58    | 2     1     679   |  1  |  2
 | 1     58    9     | 67    2     58    | 3     46    467   |  3  | 
 *-----------------------------------------------------------*     |

 N 13    4             79    1     58      3     5
 -------------------------------------------------------------
 Z             9       6           4       2     1     8



We may rule out all Z-ropes at one go, as all towers and floors haves fixed N digits.
N-rope is only possible in the top floor (269/357/148).
Tower 123: N-braid
Tower 456: N-braid
Tower 789: N-braid or Z-braid
Floor 123: N-rope or N-braid or Z-braid
Floor 456: N-braid
Floor 789: N-braid or Z-braid


In Tower 123, 13 travel and 9 does not, therefore r78c3 contain a traveling pair.
What can it be?
78 pair is impossible, that would leave cells r8c1 r9c2 depleted.
The two cells cannot be 27, as that would deplete r3c3.
Nor can they be 26, as that depletes r7c2.
67 forces 8 in r6c3 and 2 in r7c2, depleting r6c2 (but perhaps you will consider this too long an implication chain
with 3 steps, and disallow it? Please...).
What's left? 68 and 28.
Both contain 8 so... r8c3=8, and the rest are singles.

[ravel]

Mr Hamilton,

thanks for the elaborate explanation. Interestingly i dont need all the Braids and Ropes to understand your deduction.

Obviously you dont need the Braiding fact, that r78c3 contain a traveling pair, it suffices to know, that there are 2 numbers. Then you rule out 26, 27, 78, 67, 76 and are left with 28/68.

So my next question is, if this is a valid Braiding deduction too:

Code: Select all

 *-----------------------------------------------------------*
 | 278   13    5     | 23    9     236   | 1467  468   2467  |
 | 28    13    4     | 5     7     1236  | 169   689   269   |
 | 6     9     27    | 8     4     12    | 17    3     5     |
 |-------------------+-------------------+-------------------|
 | 259   256   1     | 23    8     7     | 469   469   3469  |
 | 4     7     36    | 1     5     39    | 8     2     369   |
 | 29    28    238   | 4     6     239   | 5     7     1     |
 |-------------------+-------------------+-------------------|
 | 3     26    267   | 679   1     4     | 679   5     8     |
 | 57    4     678   | 679   3     58    | 2     1     679   |
 | 1     58    9     | 67    2     58    | 3     46    467   |
 *-----------------------------------------------------------*


Lets take r12c1:
72 depletes r3c3.
78 gives a 2 in r3c3 and r7c2, then 6 in r4c2 and 5 in r4c1, therefore r8c1 depleted.
So r3c3 must be 7, solving the puzzle.

Or is it not valid, because i dont need r2c1 to rule out r1c1=7 ?

btw, the chain
r9c2=8 => r4c2=5 => r5c3=6 => r6c3=3 => r8c3=8
also gives r8c3=8

[MrHamilton]

I would be the first to agree that the Sudopedia method is too much paperwork, I don't use it in practice when simpler methods suffice.
I think its ruleset also needs to be expanded or further defined as well, to be ready for general use.
I like the hybrid approach with side notation, useful when solving with pencil and paper. Not so much work but it can suggest placements and exclusions before pencilmarks are needed, and after.
I have solved some puzzles using just that and URs and maybe x-wing.
And yes your deduction about r12c1 is another way to do it. [edit: another way to solve the puzzle that is!]