This post reports a surprising fact about multiple solution puzzles, that solutions found by backtracking tree search can be logically inconsistent. Specifically, such solutions violate the coloring 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 later, diligent readers discovered my miscopied puzzle has 63 computer solutions, and my additional solving error that made it appear to have the unique solution of the correct puzzle 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 strongly link 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. The South box AIC slink is similarly verified.
Here I was misled by a faulty view that it is the strong link network that is represented by Medusa coloring. Strong links allow both terminal candidates to be true. Coloring clusters are stronger, meaning more restrictive. They require that only one of the oppositely colored slink partners can be true. Two readers, Dov Mittleman and Guenter Todt reminded me of this fact.
Accordingly, the “coloring” extensions beyond 9 in the grid are incorrect. The colors extend the slink network, but not the coloring network.
The requirement that chain terminals are not both true distinguishes the network types. Coloring requires an exclusive-or between terminals. We’ll call it the not-both requirement. The not-both requirement does not rule out AIC slinks.
In the South box above, the elimination is valid, regardless of the not-both. Either the coloring is valid (not-both true) or 9r7c4 and 2r9c5(both true and not-both false).
“Coloring over” the not-both requirement in the Southwest is a trial. If not-both, the SW and S slink network extensions trap five candidates. In the 2r9c2 trap, green or blue remove 2. These eliminations generate a clue 2r3c2. Also, both 12 and 67 traps are valid.
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. Solvers not based on human methods, the easily coded back tracking solvers, naturally present these. Unfortunately, this has led some to reject UR and other uniqueness methods, which are based on the expectation that blatantly multiple solutions would not be in a properly composed Sudoku.
Next we notice a large number of solutions placing 1r7c2. This marks them as solutions that do not recognize the “coloring” restrictions of the SW AIC slink elimination. In the solutions that do, blue places 9 and green places 4. The 1r7c2 also accounts for the other two SW AIC slink eliminations.
Note that in these solutions, the SW slink terminals are both true. Not-both fails. Had no solutions been found in a “coloring” trial of the AIC slink, the both true side would be tested.
Here, more solutions place 1r3c2 where the “coloring” says a 2 clue has to be:
But wait. Five of these solutions are subject to the SW “coloring”, because 4r9c2 is false. These five renegades defy the logic of the slink network derived from the givens and clues they accept, shown here:
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.
These fail the not-both requirement for the South coloring, and but make the eliminations it requires. They do satisfy not-both for SW coloring, and are consistent with the SW coloring eliminations.
In summary, with my completed trial of the coloring network eliminations from the slink network, I did find 5 logically inconsistent solutions. That proves such solutions exist, at least for solvers not undertaking this slink network trial, like Andrew’s. And certainly for backtracking solvers taking no account of the slink network or coloring network.
So what do we make of logically inconsistent, impossible to derive, solutions?
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.
Can a unique solution be inconsistent with the slink network and the coloring network? No.
But multiple solutions? The coloring network accommodates multiple solution. It uses traps and wraps to extend itself over the multiple solutions, given enough time and patience.
The slink network, which includes AIC slinks, does not accommodate multiples in this way.
Candidates A and B are strongly linked if (not A) => B and (not B) => A.
In this fundamental definition, “(not A)” means “not in the solution”. It does not mean “not in any solution”. For multiple solution puzzles, the definition of the strong link is meaningless.
That delivers us from this “logical inconsistency” dilemma. We can have the AIC slink and the honor of Sudoku as well. 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.
Coloring is stronger, but demands more than the slink network. Among the solutions of the miscopied ardv2 38, I found a not-both misdemeanor, where originally I thought I had a coloring felony conviction, but I’ll take it. Three readers had my back, and I was forceful fully relieved of a careless belief.
And, let’s not forget, that when coloring would be decisive, but the not-both cannot be confirmed, then a slink network “coloring” trial is still possible. Either the coloring is valid, or both terminals are true. Here, that trial would have led you to the complete human analysis of the miscopied puzzle’s multiplicity. Let’s not buy in to computer backtracking solutions as anything superior to human reasoning.
On a lighter topic for next time, 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.
You still assert that the eliminations of 12r7c2 and 67r9c5 are logically correct. But in the same post you present numerous solutions which are counterexamples to this statement. You argue: if 9r9c1 is false, then 9r7c2 is true, hence 4r7c2 is false and 4r9c2 is true. Then you argue: if 4r9c2 is false, 4r7c2 is true, 9r7c2 is false and 9r9c1 is true. I agree with both argumentations. But the second is not the reverse of the first. It is the contraposition of the first and therefore logically equivalent to the first. What is really needed, is the reverse implication: if 4r9c2 is true, then 4r7c2 is false, then 9r7c2 is true and 9r9c1 is false. In this chain 9r7c2 may not be true – as the counterexamples show. There is no chance to get the green color for 4r7c2. In the South box the wrong implication is: if 2r9c5 is false, then 9r9c5 is true. There is no chance to get the green color for 2r9c5.
Four of the 63 solutions are missing. Here they are:
I’m sure many readers are uneasy with the AIC slink, but it’s OK. I’m planning more examples. The miscopied Ardv2 38 eliminations are correct. Are you labeling the solutions that violate them as counterexamples? Of what? They are solutions, but not logically derivable ones. That’s what the post was all about, Guenter. It’s a fault of the puzzle itself.
The reversal you mention is a weak link, not a requirement for a strong link. Coloring is a representation of a strong link network of candidates. The blue extensions come from the AIC (forcing chain) slinks. The green colorings simply follow from regular strong links of the respective boxes. Did I mislay four solutions? Thanks for supplying them.
12r7c2 and 67r9c5 are clues in some of the 63 solutions. Therefore it is impossible to eliminate these candidates without further assumptions. The logic of your green coloring is like this: if 9r1c2 is a clue, then 9r9c1 is a clue, then 4r7c2 is a clue. But the last implication is wrong as some solutions show.
The same coloring means that the candidates must be in the same solution. But 9r9c1 and 4r7c2 need not be in the same solution.
Guenter, the post has been rewritten to pass along what I learned from a series of mistakes. Thanks for contributing. It now shows clearly why multiple solutions cannot be used to evaluate Sudoku solving logic.