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.