This post reports a surprising fact about multiple solution puzzles, that solutions found by backtracking tree search can be logically inconsistent. Specifically, such solutions may violate the strong link network implied by the givens. I happened on this fact by means of a multiple solution puzzle, my mistaken copy of A.D. Ardson’s puzzle 38 from his Sudoku Very Hard Puzzles, v.2. As reported earlier, diligent readers discovered my miscopied puzzle has 63 computer solutions, and my additional solving error that made it appear to have the unique solution published by Ardson.
Here is the critical grid of my miscopied Ardv2 38. My copying error was the omission of a given 1r7c6. The solving error was identified by my diligently critical reader Guenter Todt. It is the omission of candidate 2r7c8 in my line marking.
The unique rectangle is Type 3. Since one 5 is true in NEr1, either 6 would bring a too obvious multiplicity on the rectangle.
The AIC’s of the south bank extend the Medusa coloring cluster of a dead 9-wing and dead 9-swordfish to additional candidates. The SW chain creates an AIC strong link between candidates of different values, green 9 and 4r9c2. The SW slinks and the cell wink convey the AIC inferences both ways: If green 9 is false, blue 9 is true, hence 4r7c2 is false and 4r9c2 is true. Of course 4 coloring depends on the reverse being true: if 4r9c2 is false, 4r7c2 is true, blue 9 is false and green 9 is true. A strong link does exist between these two candidates, and the cluster is extended to the two 4’s. The South box AIC slink and coloring extension are similarly verified.
Now 2r9c2 sees both colors. It is false whichever color is true. These eliminations generate a clue 2r3c2. Also, both 12 and 67 traps are valid. AIC strong links have to be accepted as part of the slink network represented by coloring.
With these eliminations, a blue trial leads to Ardson’s solution and a green trial, to two more solutions. At left are these three solutions.
What are the other 60 solutions? When I asked my friend Gordon Fick, who also reported the 63 solutions from Andrew Stuart’s solver, he sent them right over.
As you can imagine, a display of 63 solutions in grid form, even the superimposed type of grid here, is not practical for human comprehension.
But there is a way.
Here, stretched out row by row, are the eight solutions containing the blatant paired solutions of the Type 3 unique rectangle. We know we have them all because the 56 and 65 patterns appear nowhere else in the listing in the columns corresponding to the rectangle corners.
It’s notable that even though Andrew’s book and site deal with UR methods thoroughly, the solver includes an option to include these “dirty rectangle” solutions in its list.
Next we notice a large number of solutions placing 1r7c2. This marks them as solutions that do not recognize the SW AIC slink elimination. In the solutions that do, blue places 9 and green places 4.
Are you getting the drift? Although these solutions agree with the givens and clues derived to this point,
they do not accept the restrictions imposed by the slink network derived from them. And why should they? Backtracking tree search finds all solutions, without regard to any strong links between candidates.
It turns out that all 60 of the “extra” solver solutions have the same type of logical inconsistency. Here is the set placing 1r3c2 where the 2 clue has to be:
And the solutions not joining these groups place 6 or 7 in r9c5 where blue 9 or green 2 ( the top three solutions) are placed.
So what do we make of this?
The objective of Sudoku is to find the unique placement solution.
This accidental encounter with the truth about multiple solutions may not surprise you, but it is disturbing, isn’t it?. Composers use backtracking search to check that given patterns have solutions. Certainly they should run the search long enough to verify single solutions.
But is a unique solution automatically consistent with the slink network of Sysudoku coloring and AIC? The answer, thankfully, is still “yes”, based on the slink definition:
Candidates A and B are strongly linked if (not A) => B and (not B) => A.
Nothing else, please. Not “same value”. Not “in the same unit”. Not ” A => not B” as well.
It’s surprising that I never thought to use an AIC slink as I did here, but doubly surprising to discover that logically compromised Sudoku solutions could exist. Raising the issue invites a more serious examination. If this embarrassing case is verified, more direct cases will be found. Human solving power is demonstated, but does this mean that the concept of a Sudoku solution has to be qualified in barely detectable manner?
No. Going back to the definition above, (not A) means “not in the solution”. It does not mean “not in any solution”. For multiple solution puzzles, the strong link definition is meaningless.
That delivers us from this dilemma. We can have the AIC slink and the honor of Sudoku as well. Coloring is as simple as I thought.
It is the multiple solution puzzle itself that is meaningless. The slink network of its givens is not credible, as this blog has discovered before. Know where? That’s your research assignment.
On a lighter topic, how about an outlandish exercise on the bypass 3-fill bars? The bypass 3-fill was added to the Sysudoku bypass last April 11, with the 3-fill rule, in which you fill the cell seen by two of the missing numbers with the third number, or the cell not seen by one of the numbers with that number. That post displayed a case with two parallel 3-fills generating two crossing 3-fills, from Michael Rios’ Mensa Sudoku
My favorite breakfast chore, Dave Green’s Sudoku, just published another 3-fill wonder, in Ohio’s award winning Akron Beacon Journal. It’s the Friday 4-star of July 7, 2017. It features three 3-fill columns. Is Dave a reader?
Anyway, it’s clear that a tracing convention is required for the bypass 3-fill, and one will be added to the trace page. List the 3-fill effects in parentheses, and place the list first ahead of other effects. That’s it. Start your trace with c3.