This post compares Sysudoku trial strategy with the chain or disproof hypothesis strategy described in Bob Hanson’s Sudoku Assistant report. My opinion is that Bob’s strategy contributions and his Sudoku Assistant solving records are both compromised by a willingness to resort to trial-and-error. His acceptance of Gail Nelson’s blatant T&E method confirms my position on the T&E issue.
Trials have become an important part of the Sysudoku solving repertoire, as the targeted puzzles have reached extreme and monster class. These trials involve the assembly of set of candidates that would be true or false together, and marking the assumption that they are all true. A contradiction then has a good likelihood of confirming a corresponding set of candidates as true. To support trials I introduced a method of breadth first marking and tracing that permitted the trace writer to document graphically the shortest inference path to a contradiction.
A recent theoretical triumph of this strategy is the discovery of the double nasty loop that confirms the Hanson and Marans four slink loops and duplicates the “opening volley” SK loop’s removals in the HM Easter Monster.
Sysudokie trials are undertaken when direct methods seem to be exhausted, with one major exception being the verification of alternatives in the Sue de Coq. Other trials include colors, or alternative directions in chains, or alternative patterns, with one polarity being necessarily false when the other is proved true, and vice versa.
Bob’s SA report section, Hypothesis and (Dis)Proof, is about chains of two possible states, but he misses completely the idea of constructing as large a bipolar chain as possible, for trial of one or both sides. Instead Bob starts with an arbitrary candidate, assigns it an arbitrary true (Hypothesis) or false (Disproof) value, then marks chain nodes according to their confirmation or disproof of this guess.
Bob doesn’t seem to understand that neither the right or wrong state of his hypothesis or disproof guess tells us anything about the logic of the puzzle. It only tells us a piece of the solution. He compounds the error by suggesting his trial method as a way to solve a regular XYZ-wing. The point of this suggestion escapes me.
In Sysudoku bipolar chain trials, when we cannot identify the solution with simpler logic, we invest more of the puzzle constraints into larger sets of candidates. These investments are observed facts, not arbitrary supposes. If we have to go to trial, at least the conclusion has logical weight.
Even though it was not programmed into Sudoku Assistant When the report was written, Bob passes on another suggestion from a friend. I’ll be calling it bv bifurcation nets. Bob readily accepts this blatant trial-and-error method:
Pick a bv and simultaneously try both values as true, distinguishing by marking candidates confirmed by the two cell candidates. Bob says
“You often don’t have to go far in either direction to come to a satisfactory conclusion:
- The two logical chains converge to a particular value in a specific cell. Then that cell is that value.
- The two logical chains converge to two different values in the same cell, row, column, or block. Then every other possibility in that cell, row, column, or block can be eliminated.”
As he has been throughout the SA report, Bob is being unclear and incomplete. Let’s do it properly:
- If no contradiction is reached, candidates which both truth nets deem true are clues: candidates which the nets agree are false are removed.
This was the original rationale for forcing chain method that Sue de Coq thought would obviate her method. As Bob’s friend Gail Nelson undoubtedly did, and as Bob does here, the promoters of forcing chains from randomly chosen bv (Rule 1) carelessly or deliberately omitted the “if” clause..
- If no contradiction is reached, where the two truth nets confirm two different candidates in the same cell, all other candidates of the cell are removed.
- If no contradiction is reached, where the two truth nets confirm two different locations of a number in a unit, all remaining candidates of that number are removed from the unit.
Rules 2 and 3 (Bob’s 2) extend the power of the bv bifurcation nets, and may originate with Hanson . The idea goes even further. As they stand, rules 2 and 3 offer a systematic way to find eliminating and confirming ANL (almost nice loops). My post Digit Forcing Chains? revealed this Andrew Stuart fantasy in November 2012.
“This simple AIC proves that either 3 in r1c2 or 9 in r5c2 is true, eliminating 3 in r5c2 that sees them both. Stuart picks the bv in r1c2 for his dual cell forcing chains, but the bv r1c9 and r7c9 could have served just as well. “
Stuart’s folly was to masquerade a legitimate elimination method as a new method, marked as T&E by the arbitrary choice of starting points.
But note how the almost nice loop differs from bv bifurcated nets. The ANL was constructed as a complete entity. The loop invokes only one of the winks from each bv candidate. The elimination in no way depends on the actual value of the any bv candidate.
Not clear on the difference? For a checkpoint next post, pick r1c9 and color 2 green, 8 blue. Then do the two way truth nets that Bob describes. You can use colors, but this is nothing like Medusa coloring. Winks, not slinks, are in control. For contrast, we’ll also solve this Stuart example puzzle by a Medusa coloring trial in the next post.
But the bifurcated nets idea goes much further. If you had the time, you could initiate forcing chains in every candidate of a number in a line or box, as a way to find Stuart’s Unit Forcing Chains . I dismissed this idea as a human solving tool, but that is no barrier to computer solver programmers.
Getting back to the proper statement of the bv bifurgated nets list:
- When a contradiction is reached, then the bv value and all of its 1-3 conclusions remain, and the contradicting value and its confirmations are discarded. Be careful how you mark the removals of 2 and 3, so they can be reversed. Do not extend the truth net based on its removals.
Rule 4, the most likely outcome of a bv bifurcated truth net, reveals it as blatant trial-and-error method, requiring nothing but basic marking skill to get the solution of any puzzle that offers enough bv.
This leaves us with a profound question about the bifurcated truth net or multifurcated truth net:
If we expand the truth nets concurrently, and stop before a contradiction is reached, are we entitled to the confirmations and removals of rules 1 – 3?
Think about that for a minute. It is the kernel of the trial vs trial-and-error issue. I encountered this issue very early in the Sysudoku blog with Denis Berthier’s xyt-chains, arriving at rule that limited toxic sets generated by the rule that avoids T&E. This was possible because the origination of these chains is far from arbitrary. With this discipline, the xyt-chain becomes a legitimate extreme method, although I’ve not yet been desperate enough to use it.
In the trial vs T&E issue, there is Sysudoku ‘construction first and trial as late as possible’ on one side, and the ‘pick a cell or unit at random and generate truth nets’ on the other. I’m not judging, but for my own satisfaction of discovery, I consider arbitrarily located truth net results as forbidden fruit, with the arbitrary choice of origination as the poison.
In the last section of the SA report, Bob describes two levels of depth in SA’s backtracking code. +Depth is trying single entities per step, while ++depth is assembling entities into groups of identical polarity (true or false). For human solving of difficult puzzles, ++depth is the only practical answer. It adds spice to the human solving game, where it is a triumph to assemble trial sets decisive enough to cut the depth of trials to a humanly manageable size.
Bob ends his SA report with:
“Obviously this can’t solve all Sudoku puzzles. But so far no one has shown me a puzzle that can’t be solved using ++depth. Using the above techiniques together Sudoku Assistant has solved all of the puzzles I have thrown at it”.
These are encouraging words that support Sysudoku trials. Bob attributes the SA success to ++depth backtracking. The report offers no guarantees, but we hope that the SA codes order of battle promotes logically advanced and extreme measures ahead of ++depth trials, and that the implementation of +depth trials has been and will be resisted.