## 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
|---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.)
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
An alternative route through logical analysis amounts to hypothesizing that Node "a" CAN be eliminated and then
working
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
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.)
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. |