Dead End, but not really: Demonstration that any logical chain analysis is just trial and error and that "bifurcation" is just the beginningShown below is the configuration part way through the Sudoku Assistant analysis of this puzzle from the top95 collection:920300008006408090830500000000200080709005000002006004008000010001000402200700809 92.|3..|..8 ..6|4.8|.9. 83.|5..|... ---+---+--- ...|2..|98. 7.9|1.5|... ..2|9.6|..4 ---+---+--- 4.8|6..|.1. ..1|85.|4.2 2..|7..|8.9 Hypothesis and Disproof -- Looking for a logical inconsistency -- one of the "dead ends":
|---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9-- |
|
This configuration
is one of the "dead ends" arising from logical "hypothesis and disproof." At this point, Sudoku Assistant moves on to another hypothesis.
(To get this table from the original top95 puzzle, load
that puzzle,
set the 3D Medusa analysis level to "+weak", and press "Solve".
The solver will get stuck. Change the 3D level to "+hypothesis and disproof", check the "details" link,
and then press "Step" once. Look down the list for the dead end at "Logical analysis: Chain 2(0) Dead End at k." Click the "Table" link.)
How "Hypothesis and Disproof" Works In this analysis, you pick a "node A" (a specific possible value in a certain cell) hypothesize, "A cannot be eliminated," and see if that leads to a logical inconsistency (an "error"). If it does, then you know that the hypothesis is false, and "A" CAN be eliminated. The cycle of finding a solution is restarted. This node can be either a strong-chain node (a candidate in a cell with only two possible values or a candidate that has exactly two possible locations in a row, column, or 3x3 block) or a weakly associated node (one of a strong node's "buddies" -- in the same row, column, or block as that strong node). If this analysis does not lead to a logical inconsistency, two outcomes are possible: Either you have found a "Magic Cell" -- the puzzle is solved -- or you have reached a "dead end." When I started in on this hypothesis and proof business with the Sudoku Assistant, it didn't solve some of the top95 and "impossible 520" puzzles. The problem, I discovered, was that I was "missing" the idea that if N-1 members of a set of 'buddies' are found to be eliminated due to the hypothesis, then the Nth can be "set TRUE," and the process can be continued. Addition of this consideration allows for the solving of all of these puzzles. Indeed, I have yet to find a 9x9 Sudoku that can't be solved this way. Some have referred to the analysis as "logical bifurcation" when this special step is included. "Bifurcation Logic" is the Same An alternative route through logical analysis amounts to hypothesizing that Node "a" CAN be eliminated and then working backward to what would lead to this hypothesis being true. Sort of a "trial" without the "error." You can see this sort of analysis in action by selecting "proof" instead of "disproof" in the Sudoku Assistant. You will see that it is absolutely identical logic, just conceptualized in a slightly different way. The "bifurcation" rule in that case becomes the following: If any one of N-1 members of a set of 'buddies' not eliminated (TRUE) would prove the hypothesis, then the Nth can be set FALSE (elimination would prove the hypothesis) and the process can be continued. To each his/her own. {?FFF...} --> {TFFF...} Is Just the Beginning But it turns out that there isn't anything special about adding this particular consideration. Really all it is is just starting over with the human solving stage -- looking for hidden singles. ("If you can't put 5 anywhere else, then it must go HERE....") We could have continued past this "logical dead end" looking for block row/column exclusions ("locked" cells), subsets, X-wings, chain analysis --- the works. So, for example, if you look at the "dead end" shown above, it isn't really a dead end. The 5 in r8c1 can be eliminated. That's because the 5 in this block is "locked" into being in row 9 by the absence of 5s in row 9, columns 4-9. If you load this configuration and try to solve it, you will see that several other eliminations continue from there, ultimately leading to a logical inconsistency. Thus, node r4c6#4 can be eliminated because 4 must be in the third column of block 8. Node r8c4#6 can be eliminated by a nifty XY-Wing involving the three duples at r8c1 (just 36, once the 5 is gone), r8c6, and r7c4. Etc., etc. Clearly this is only a dead end because we have chosen to give up at this point. The Beginning is Just Trial and Error Depth Search If this sounds a lot like just solving a Sudoku, well, it is. We're just "starting over" with this particular configuration arising from our trial hypothesis. Continuing all the way through block row/column exclusion, subset elimination, grid analsysis, and chain analysis to an additional round of hypothesis and (dis)proof amounts at some point to a "depth-based" trial and error search with added "human" short-cuts. (An efficient solver will just dispense with ALL the human stuff and do this sort of logical analysis directly.) My conclusion It is interesting to try to solve Sudoku puzzles using "human" methods. All of these methods amount to "short-cuts" to simple trial and error. The spotting of a hidden triple, an X-wing, a swordfish -- these are just quick tricks that will suffice for the sort of puzzle generally presented in print. But all of these tricks will ultimately fail for some Sudoku. (This, I believe, is a fundamental aspect of the "NP-complete" nature of Sudoku. There is no GENERAL non-[trial and error] solution to such problems.) At this point, one can employ more advanced techinques -- coloring, tabling, and other simiplified variants of general logical chain analysis. But, for SOME puzzles, in the end this will not be enough. Whether you refer to the next step as "depth search" or just "continuing to look for logical inconsistencies", the process would continue by cycling through whatever method you have chosen to greater and greater depth until the job is done.
Logical analysis: Chain 2(0)
A: The hypothesis is this:
Chain 2(0) cannot be eliminated. |