Andrew wrote:In its original sense bifurcation means forking in two directions. The people who have invented advanced techniques in the last couple of years didn't like that. They have therefore taken the view that techniques that start with forking but are thereafter logical are not considered to be bifurcation even though they really are in the pure sense of that word.
Andrew wrote:I've had Andrew Stuart's book since it first came out but, unlike Cathy and Mike who have well thumbed copies, I've only managed quick glances so far.
Yes, bifurcation does simply mean forking in its original sense. However, in Sudoku circles it's invariably reserved for a specific type of forking, namely forking of the entire grid state. For an example, see chapter 1 of Andrew Stuart's book, where he associates bifurcation with Ariadne's Thread. Another distinguishing feature of bifurcation in this sense is that the starting choice (e.g., cell candidate, cage combination, ...) is essentially arbitrary.
With the regular chain-based techniques in Sudoku, the situation is very different for a number of reasons:
The starting choice is not arbitrary. For example, for AICs, the starting choice is the candidate premise at one end of a strong link being false.
The grid is not modified. Note: This is important! Even the slightest modification to the grid would in general require saving the entire grid state at each branching point in the chain! I use AICs and Nice Loops quite a lot, so if anybody sees me using any strong links that weren't there at the start of the chain, I've made a mistake and would like to know about it!
The chain is built up "merely" by following weak and strong links, not by potentially using every solving technique under the sun. For automated solvers, this means using dedicated chain processing rather than simply allowing the solver to run further.
Although regular chains do often involve finding contradictions, one is looking out for particular termination conditions here, not simply responding to any unexpected error condition.
Glyn wrote:...unless one is prepared to bite the bullet and allow the links to modify the cage values to a certain extent. Perhaps we could call them strong active links. The chains would preferably be short as any of the active links would start to make the grid unrecognisable and carry the strong odour of T&E.
I use the term dynamic links for these, because the strong links arise dynamically as a result of side effects of earlier links in the chain. But the difference between these dynamic links and the "active" links you describe is merely one of terminology. The concept is identical.
All chains containing dynamic ("active") links are hypotheticals in my book. Hypotheticals are generally regarded as limited T&E, or even "guessing" (as Ruud has just expressed it on the A65 thread). However, whilst this is often true, to uniformly apply this equation would belittle the tremendous aptitude humans have for recognizing promising patterns and cutting off unpromising avenues of exploration in order to dramatically reduce the amount of searching to be performed. The problem is, how can hypotheticals be formalized? I agree with Glyn that a lot of research work still needs to be done here (and that it's best to do all this on another thread).
Last edited by mhparker on Mon Aug 27, 2007 3:50 pm, edited 1 time in total.
Interesting discussion developing here. Being a moderator on the Eureka forum, I never imagined that people could also discuss this subject in a civilized manner.
In my solving guide, I've written a section about Sudoku Controversies. It badly needs an update.
If you want to see bifurcation in action, take a puzzle that has no more logical solving steps and make an extra copy. Now pick a cell with 2 candidates or a cage with 2 combinations or a row, column or box where a certain number can only go in 2 places. Select one of the choices in the first copy and the other in the second. Now continue to solve both puzzles.
If you find the solution in one of the copies and you accept it, you have used a Guess.
If you find a contradiction in one of the copies and you reject it, you have used Trial & Error. Some might say that this is the same as a bad guess. I would not entirely disagree with this opinion. There is a special case to consider here, where the initial choice is part of the contradiction. When a path A => NOT A exists, there must also be a reverse path. Advanced solvers really appreciate reversible chains.
If you find a common truth in both copies, i.e. a candidate that is eliminated in both puzzles, or a placement made in both, you have used a Forcing Net. In my SudoCue program, the Tabling Verity technique works this way. Again, reversibility comes to the rescue here. When A => B and NOT A => B then there must be a path NOT B => NOT A => B which confirms B.
We do not need to limit ourselves to bifurcation. Why not trifurcation or quadruple ramification (who invented these words?). Well, the problem is that these will never lead to a reversibile proof without using branching in either direction.
This brings me to my current position on the acceptability of solving techniques:
A solving technique is acceptable when it can be rewritten as a (reversible) sequence of implications where each node in this sequence is a coherent group of candidates.
Because every sequence of implications is reversible, the use of this term is superfluous.
In regular Sudoku, a group of candidates is coherent when they all belong to the same row, column or box. In Killer Sudoku, candidates in a single (split) cage are also a coherent group.
This leaves room for more than just singles. Any pattern that can connect two coherent groups could be placed in the chain, as long as that pattern creates a reversible link between these nodes. Almost Locked Sets, Almost UR's and Almost Fish can be placed between the nodes.
Finally, this is just a personal opinion and it is certainly not carved in stone. I'm learning new things about Sudoku everyday. I'm not even sure which techniques would qualify or fail this test. I'd really appreciate your input on this so we may refine this definition in a way that we can all agree with.
Thanks for the suggestions. Here are a few quick points to get the ball rolling. Maybe other forum members can add a few more.
Ruud wrote:If you want to see bifurcation in action, take a puzzle that has no more logical solving steps and make an extra copy. Now pick a cell with 2 candidates or a cage with 2 combinations or a row, column or box where a certain number can only go in 2 places.
Actually (just in case anyone's getting the wrong impression), as far as the first two solving techniques you mentioned are concerned (Guess and Trial & Error), one can pick a cell with more than two candidates (or a cage with more than two combinations), and it's still only bifurcation (not trifurcation, etc.). As such, only one copy of the grid state needs to be made, and the two branches are essentially cell = chosen candidate (or cage = chosen combination) and cell <> chosen candidate (or cage <> chosen combination).
For the Tabling Verity technique, one clearly needs as many copies of the grid (including the original) as the number of candidates in the chosen cell, combinations in the chosen cage, or candidate positions in the chosen unit, respectively, in order to be able to compare the results. So this is real N-furcation. I presume this is what Andrew had in mind in his previous post.
Ruud wrote:If you find the solution in one of the copies and you accept it, you have used a Guess.
Care must be taken here. Strictly speaking, one has found a solution, not necessarily the solution. So, by completing the grid after making a guess, one is also making the implicit assumption that the puzzle only has one solution.
Ruud wrote:If you find a common truth in both copies, i.e. a candidate that is eliminated in both puzzles, or a placement made in both, you have used a Forcing Net.
Just for info: We also recently had a slightly more complicated case (Cathy's step 22 in her A61X WT), where trifurcation was involved that, whilst not yielding a common placement, nevertheless locked a digit into one of two positions within a unit, thus allowing that candidate digit to be eliminated elsewhere in that unit. A placement common to all branches can in this sense just be seen as being the special case where a particular digit is locked into a single candidate position within a particular unit.
Ruud wrote:A solving technique is acceptable when it can be rewritten as a (reversible) sequence of implications where each node in this sequence is a coherent group of candidates.
Because every sequence of implications is reversible, the use of this term is superfluous.
True, it should in theory be superfluous. However, this requirement is clearly intended to filter out chains with dynamic links (see my previous post), which are what I usually mean when I refer to the term hypothetical. For example, if a side effect of a link in the chain changes the grid state from G to G', then a subsequent link may not be reversible, because the underlying grid state in the forward direction (G') differs from that in the reverse direction (G).
Assassin 64V2 was solved as a "tag" solution by Cathy, Mike, Howard, Richard, Para, Glyn & goooders. The original moves are earlier in this thread.
I had hoped to take part in the later stages, after I had solved Assassin 64 but the late spurt beat me to it. That was why I volunteered to write this after Cathy asked if anybody was inclined to do it.
Consolidated Walkthrough for Assassin 64V2
I’ve tried to keep fairly closely to the moves as posted in the “tag” solution in this thread. Some editing has been done to maintain a consistent format. I've retained the original step numbers; un-numbered steps have been added to existing steps. Alternatives, given as [Alternative …] after the original step, were posted in the “tag” solution. A few “withdrawn” moves have been retained for completeness.
Prelims
a) 24(3) r9c234 = {789) not elsewhere in r9 -> r8c1 <> 1,2; r8c9 <> 2,3,4
b) 22(3) r5c678 = {589/679} 9 not elsewhere in r5
c) 11(2) n1 and n9 – no 1
d) 8(2) n2 = {17/26/35}
e) 12(2) n3 = {39/48/57}
f) 20(3) r456c1 = {389/479/469/578} – no 1,2
g) 9(2) n7 = [36/45/54/63/72/81]
h) 6(2) n8 = {15/24}
i) 14(4) at r3c1 = {1238/1247/1256/1346/2345} – no 9
j) 9(3) r5c234 = {126/135/234}
k) 11(3) n7 = {128/137/146/236/245} – no 9
1. Innies c1: r37c1 = 5 = {14/23} -> max 4 in r7c1 -> r6c23, r7c2 <> 1
29. Split 12(3) r159c6 (step 18): {237/156} both blocked by 8(2) n2; 8,9 no longer available
29a. -> r159c6 = {147/246/345}
29b. -> must have 2 of {1234}, only available in r19c6
29c. -> no 5,6 in r19c6
29d. 4 locked in r19c6 for c6
30. 9 of 22(3) locked in r5c78 for n6
30a. {89} only available in r5c78
30b. -> no 5 in r5c78
31. LoL n5 (step 12): no 8,9 in r3c5
32. 10(3) r9 (step 11) must contain 1 of {56}, only available within n9
32a. -> 11(2) n9 <> {56}
41. 9 locked to r3c347 within split 26(4) -> 26(4) r3c3467 = {9...}
Options: {2789/3689/4589/4679}
If {4589} r3c6 = 5 -> r3c347 <> 5
42. No 4 in r6c23. Here's how:
42a. If r9c4=7, then r6c23 = 15
42b. If r9c4=8, then r6c23 = 14
42c. If r9c4=9, then r6c23 = 13 -> r7c12 = 10 = [19/46] = [4/9, ..]
(not [28/37] because 9 in r9c4 forces {78} into r9c23)
-> {49} combo in r6c23 blocked
42d. -> no 4 in r6c23
43. Outies n3: r1c6 + r4c78 = 15 (step 6)
43a. r4c78 max is 13 to fit with the 16(4) cage
43b. -> r1c6 <> 1
44. Outies n9: r6c78 + r9c6 = 8 (step 8)
44a. Options for 12(3) r456c9 are {138/147/156/246} ({237} is blocked by 11(2) n9, {345} is blocked 12(2) n3)
44b. Only possibility for r6c78 + r9c6 with 6 is {16}1 but {16} would block all possibilities in 12(3)n6
44c. -> r6c78 <> 6
45. 15(4) at r6c7 - only combinations with a 4 also require an 8, 7 or 6 which only occur at r7c9
45a. -> r7c9 <> 4
45b. -> r3c9 <> 6 (step 2)
[Alternatively. Innies/outie n9: r9c6 + 7 = r7c89 -> r7c89 = 8/9/10/11 -> r7c9 <> 4, r3c9 <> 6 (step 2).]
46. Split 25(4) in r4678c6 must have 8 and 9. Options: {1789/2689/3589}
47. Innies r123: r3c12589 = 19. Max from r1589 = 2+3+4+7 = 16 -> r3c2 <> 2
48. r3c12589 (step 47) = 19(5) = {12349}/{12358}/{12367}/{13457}/{13456}
48a. {12349} - no 9 so not possible
48b. {12358} - r3c5 = 5, r3c189={123} -> r3c2=8
48c. {12367} - r3c5 = 7, r3c189={123} -> r3c2=6
48d. {13457} - r3c5 = 5/7, r3c189={134} -> r3c2=7/5
48e. {13456} - r3c5 = 5, r3c189={134} -> r3c2=6
48f. -> r3c2 <> 3,4
[Two alternatives were also posted.
Alternative 1. r3c12589 (step 47) = 19(5) = {12358/12367/12457/13456} -> needs 3 of {1234} which need to go in r3c189, so nowhere else in r3c12589 -> r3c2 = {5678}.
Alternative 2. If r3c2 = 3/4 it forms quadruplet r3c1289={1234}, requires r3c5 = 9 -> r3c2 <> 3,4.]
49. No 5 in 20(4) n2. Here's how:
49a) If r3c5 = 7, r1c46 + r3c5 = 17 (step 15) -> r1c46 = 10 = [64/82]
Taken together they block {17} and {26} combos for 8(2) cage. Only remaining alternative is {35}
49b) Alternative is r3c5=5
49c) -> no 5 in 20(4) cage -> r1c5, r2c45 <> 5
51. If 12(3) n6 = {147} => 12(2) n3 = {39} together block all combos for 11(2) n9 ->
r456c9 <> 7
[The poster of step 51 hinted that r3c2 <> 5 from a forcing chain through n6 and back into r3. This wasn’t used in the “tag” solution. You can work it out for your own amusement; the first part of the chain was used in step 54.]
52. Outies n9: r6c78 + r9c6 = 8 (step 8). = {152}/{134}/{224}/{233} (we already removed {116})
52a. {224} - means r7c89 must total 9= [18/36] and r9c78 totals 8 ={53}
52aa. r7c89 = [18] is possible
52ab. r7c89 = [36] and r9c78 = {53} contradiction - so not possible
52b. {233} - means r7c89 must total 10 = [19/46] and r9c78 totals 7 = {25} ({16} would clash with r7c89)
52ba. r7c39 = [19] would force 12(3) n6 = 1{47}/{56} and r3c9 = 1 (step 2) contradiction - so not possible
52bb. r7c89 = [46] would force r9c78 = {25} but that would eliminate all candidates in r9c9
52c. Remaining options for r6c78 + r9c6 are {152}/{134}/{224}
53. 9(2) n7 cannot be {45} - blocks 11(2) n1 and 20(3) n4 - 11(2) would be forced to {29} or {38} and 20(3) to {389} – contradiction
54) Forcing Chain
If r3c5 = 7 => r5c678 = 7{69} => r7c9 = 6 (hidden single in c9) => 25(4) n8 must contain 6 whilst blocked for 7 in c56. Only combo is {2689} forcing r78c4 = {15}
Alternative r3c5=5
CPE r3c5 =5 or r78c4 = {15} -> r46c4, r789c5 <> 5
[Alternatively. If r3c5 = 7 => r5c678 = 7{69} => r7c5 <> 6 (LoL n5, step 12) …]
At this stage an implication chain and its results were expressed verbally. The first parts of this were re-phrased after steps 55 to 65 had been posted and are included as step 66.
55. 5 in r9 locked in r9c78, not elsewhere in n9
55a. 10(3) r9c678 = {145/235}, no 6
56. No 6 in r7c5. Here's how.
56a. Outies c123 (step 17): r159c4 = 19(3)
56b. Innies n8 (step 16): r7c5 + r9c46 = 14(3), r7c5 can only be 6 if r9c4 = 7
56c. Only options with 7 in r9c4 are [847/937]
56d. -> r7c5 = {34} (LoL n5, step 12)
56e. -> Innies n8 = {347}
56f. -> {167} blocked for n8 innies (step 16)
56g. -> No 6 in r7c5
57. LoL, n5 (step 12): no 6 in r5c6
58. 22(3)n56 = [5]{89}/[7]{69}
58a. -> no 7 in r5c78
59. 7 in n6 locked in r4c78, not elsewhere in r4
59a. 16(4) at r3c8 = {(126/135/234)7}, no 8
60. 6 in n8 locked in 25(4) = {2689/3679/4678}, no 5
61. 5 in n8 locked in r78c4
61a. -> 6(2) n8 = {15}, locked for c4 and n8
62. Both of {16} now unavailable to c789 outies
62a. -> r159c6 = {345} (only remaining combo, see step 29a)
62b. -> r5c6 = 5
62c. r19c6 = {34}, locked for c6
63. r3c5 = 5 (hidden single in n2)
64. From 62b 22(3) r5c678 = 5{89}, {89} locked for r5/n6
65. 12(3) n6 - {138} not now possible because no 8, so no 3 either (combo {345} was eliminated in step 44a)
65a. -> 12(3) n6 = 6{15}/{24} - 6 locked for n6 and c9
65b. -> no 4 at r3c9 (step 2)
This is the first part of the implication chain that was expressed verbally after step 54.
66. 1 in c1 locked to split 5(2) r37c1 and r9c1
66a. If r9c1 = 1 -> r8c1 = 8 -> r9c23 = {79}
-> split 5(2) r37c1 = {23}
-> 11(3) n7 = {245}
-> r7c1 = 3, r7c2 = 6 -> r6c23 = {59}
BUT 20(3) r456c1 requires at least one of 8,9 CONFLICT -> r89c1 <> [81]
66b. Split 5(2) r37c1 = {14} -> 9(2) r89c1 = {36}/[72]
If 9(2) = [72] no options for 11(3) n7 ({146} clashes with r7c1)
-> 9(2) = {36} not elsewhere in n7
-> 11(2) r12c1 = {29} not elsewhere in n1
-> 20(3) r456c1 = {578} not elsewhere in n4
Now follow through newly revealed naked single and naked pairs and the rest is straightforward.
Mike has posted an alternative solution starting from the position after step 27. He has also posted a message showing how SudokuSolver and JSudoku came up with different ways to solve this puzzle.
Last edited by Andrew on Tue Aug 28, 2007 7:18 pm, edited 1 time in total.
Many thanks to Andrew for consolidating the A64V2.
Thanks also to Mike and Ruud for interesting discussion on solving methods and what may be deemed acceptable. Perhaps we can start a new thread in the Solving Techniques devoted to Killer techniques.
I have set up a thread in Solving Techniques with some stuff I have been running past Mike/Ruud so we can all find it without having to check back in this thread which is getting a bit cluttered.
CathyW wrote:Edit: Answering my own question! Having gone through this using JSudoku, my step 29 is apparently an xy-loop.
I recognized this at the time and wasn't ignoring your question. It's just that I positively refuse to discuss any techniques in tiny text!
The problem is, by the time the puzzle is no longer current and I could openly talk about such stuff without potentially spoiling it for others, I've normally either forgotten it or been distracted by new activities related to the next Assassin! Indeed, I just finally remembered to re-visit this thread to answer your question, only to find out that you've already answered it yourself!
BTW(1), I've noticed that JSudoku refers to a continuous AIC loops as XY-Loops, even if they are often hybrids of XY-chains and X-Cycles. I don't blame J-C for doing this, because most chains/loops are probably going to be hybrids in practice.
BTW(2), I also found an XY-Loop in A65V2, but Para beat me to it with his breakthrough move that circumvented the need for it. But I might decide to use it as the basis for a tutorial-style post, because it's a very interesting one, with one aspect I bet even JSudoku doesn't see...
Thanks Mike - I know what you mean about getting distracted by later puzzles!
So, my step 29 could be rewritten as an AIC. I'll try and figure it out and post again later.
Edit: Going through the puzzle again, I had missed an elimination earlier in the puzzle (3rd line of step 17 removes 5s from the 27(4) cage). Having made it this time, step 19 led to a naked quad in c1 (4589) with 8 and 9 locked in c1N1! I'll make a note in my WT but I'm not going to redo it now.
Nonetheless, I can't figure out how to notate the step 29 as it was. Advice please!
Going through the puzzle again, I had missed an elimination earlier in the puzzle (3rd line of step 17 removes 5s from the 27(4) cage). Having made it this time, step 19 led to a naked quad in c1 (4589) with 8 and 9 locked in c1N1! I'll make a note in my WT but I'm not going to redo it now.