The New Sudoku Players' Forum

[rjamil]

Hi experts,

While I understood, coded and tested Bi-value Universal Grave 0 (BUG+0) as warning and BUG+1 as move. A question arises in my mind, how to check a puzzle if it has multi-solutions?

Please note that, I am not interesting to check second solution of a puzzle by brute force/backtracking. I need fast and shortcut method to detect the same.

Please also note that the zero solution puzzle is easy to check and not considered at the moment.

After implementing BUG+0 warning (yes, it will not stop after reaching the puzzle state where all unsolved cells contain only two values after all pre-programmed logical techniques (not uniqueness assumptive techniques) exhausted and before guessing.)

My question is that, is a BUG+0 warning (as described above) sufficient for 100% multi-solution puzzles OR only brute force/backtracking routine detect the same? Is there any proof if other than BUG+0 required to check multi-solution puzzle?

Another wild question is that, what are the techniques required to solve the puzzle from state where all unsolved cells contain only two values, provided that the puzzle has single solution? (e.g., HS, XY-Wing, ???)

I see BUG+0 definition found in HoDoKu as overloaded, unless if checked before any other technique. Or, if check each value in every unsolved cell appears exactly twice in any row, column, and box will be enough to confirm for all multi-solution puzzles?

R. Jamil

[tdillon]

If you have a puzzle that's been reduced to bi-value cells, and if there are no remaining hidden singles, then a simple pigeonhole argument shows that in each house each of the remaining candidates appear exactly twice. That's to say the Hodoku description of BUG+0 is implied by the simpler description "bi-value cells, no hidden singles".

So if you're interested in detecting multi-solution puzzles once you've already reduced them to bi-value cells then the BUG+0 warning suffices since there are no other cases.

If you're interested in detecting multi-solution puzzles more generally, then BUG+0 certainly does not suffice. It's easy to construct puzzles with multiple solutions that cannot be reduced to a bi-value state using conventional patterns (or, indeed, even with unrestricted resolution).

If fast is what you're looking for, why are you intent on avoiding backtracking in your multi-solution check? Backtracking solvers with constraint propagation are exceptionally fast.

[rjamil]

Hi tdillon,

Thanks for the reply.

Actually, I read under Andrew's Sudokuwiki Unique Rectangle's comments. As per Harmen Dijkstra comment, dated Friday 5-Mar-2010, puzzle having 17 solutions solved with UR assuming unique solution.

Similarly, Thinkist comment, dated Friday 29-Apr-2016, emphasized the same point again for which Andrew asked to proof: "a) all valid sudoku puzzles can be solved using only these strategies minus uniqueness strategies and b) that all multi-solution (non-valid) puzzles cannot complete."

Where as, in my opinion, point "a" is not true, but, point "b" is true, to the best of my knowledge and limited experience.

Now, if all multi-solution puzzles can't be solved with all logical deductive moves (not limited to Sudokuwiki offered moves), then there must be some logical way to check before applying the trial and error method to confirm the uniqueness of the puzzle.

R. Jamil

[tdillon]

w.r.t. Andrew Stuart's requested proof part (a), it's status hinges on what kinds of logical inference procedures you'll allow, and I'm unaware of commonly accepted principles for this.

One the one hand, there are definitely sound and complete deductive inference procedures that solve any Sudoku puzzle that has a unique solution. For example, if you encode the rules of Sudoku in CNF and conjoin the given clues you can use a prime implicates algorithm to find all clausal consequences, including the solution. Tison's algorithm would be a simple choice (though it's strangely hard to find this written up; the original 1967 paper is paywalled, but you can read about it here: https://pdfs.semanticscholar.org/3fb6/f637a74ef2b694e8aceb61e876331a599a94.pdf)

Certainly, Tison's algorithm would be infeasibly slow and space-intensive for trying to solve a Sudoku, even for a powerful computer. But it is an interesting stake in the ground. Not only is it simple, sound, and complete, but it does none of the backtracking that people find so distasteful. i.e., it never speculatively extends a partial solution only to back up if an inconsistency results. Instead it proceeds via ordered resolution to find all deductive consequences, and along the way it never adds a consequence that is not strictly entailed.

The obvious problem with a prodedure like this is that it generates a fantastic number of consequences, the vast majority of which do not contribute to the proof of any elimination that's part of the eventual solution. Even if this were within the reach of today's computers and time were not a factor it would be a nonstarter for humans since we're so limited by working memory.

Actually, maybe that's a principle that captures reasonably well what folks have in mind for admissible "logical techniques" for Sudoku. It's not so much that we insist on avoiding search (Tison's avoids search but it's not OK; inversely, some chaining methods are effectively doing search and limited what-if as well, but they are OK). Rather, we insist on inferences that can be reached with bounded memory. A huge number of the usual Sudoku strategies can be mapped to pigeonhole inferences, cycles in binary implication graphs, or combinations of the two, all of which share the feature that they can be identified without keeping track of much state.

Coming back to (a), my unproven and informal hunch (which is aligned with yours) is that there is no complete inference procedure for Sudoku whose space requirements are bounded enough for human comfort. That is, there exist puzzles with unique solutions that can only be found with (1) backtracking and constraint propagation requiring an onerous amount of working memory, or (2) no backtracking, but new and complex strategies whose recognition requires an onerous amount of working memory, and would therefore be controversial and considered too search-like.

As for Andrew Stuart's part (b), if you have a multi-solution puzzle, and if you apply a sound inference procedure (which excludes uniqueness strategies since these are unsound if there are multiple solutions), and if you task it only with finding deductive consequences, then yes, it will never complete the puzzle.

But your last statement ("there must be some logical way to check before applying the trial and error method to confirm the uniqueness of the puzzle") doesn't follow if you place restrictions on what counts as a logical way to check.

In the unrestricted sense, a prime implicates algorithm is one a logical way to check. You could run Tison's algorithm, find all consequences, and see if there remain any cells whose state is unknown. And, of course, you could also search. But these are probably not what you have in mind. If restrictions are placed on the inference procedure then there may not be a way to check, since we can't distinguish a failure to solve a multi-solution puzzle from a failure to solve a single solution puzzle that's just very hard.

BTW, having said the statement doesn't follow, I don't mean to say that it is necessarily false. I mean, there might exist more of a meta way to check relying on something interesting about the structure of Sudoku. I'm not aware of one, but my experience is also limited. Maybe folks who have studied unavoidable sets have some insight. It such a method exists it seems like it would be an interesting and notable result.

[rjamil]

Hi tdillon,

Thanks for your kind consideration and attention to this matter. I greatly appreciate your kind words.

A similar question was asked here and the answered by Ali Safari, dated Jun 10, 2019 at 18:23, was almost the same as I already proposed here (proposed method fitness yet to be confirmed by op creator).

However, the same question come in to my mind again due BUG+0 move detects limited multi-solution puzzles without going to involve in brute force/backtracking hectic. I rethink that there might be some set of logics or one gigantic logic that will detect rest/all of multi-solution puzzles.

Read Unavoidable Set and Deadly Pattern in Sudopedia. If all multi-solution puzzles always reached to some deadly pattern, then is there a way to detect it and warn multi-solution puzzle? (While solving a puzzle, after reaching the state where less than 30 unsolved cells remain and all consist entirely of bivalue cells without HS present, then the puzzle should be marked as multi-solution puzzle. But this state is easily detected by BUG+0 move.)

R. Jamil

[blue]

If you have a puzzle that's been reduced to bi-value cells, and if there are no remaining hidden singles, then a simple pigeonhole argument shows that in each house each of the remaining candidates appear exactly twice. That's to say the Hodoku description of BUG+0 is implied by the simpler description "bi-value cells, no hidden singles".

You need to add that in each house, each missing cell value, has at at least one candidate.

Code: Select all

+----------+----------+-----------+
| 3   5  9 | 8  7   4 |  1   2  6 |
| 8   6  1 | 9  5   2 | 37  37  4 |
| 4   2  7 | 1  3   6 |  8   5  9 |
+----------+----------+-----------+
| 6  79  8 | 4  2   5 | 79   1  3 |
| 1  79  3 | 6  8  79 |  4  79  5 |
| 2   4  5 | 3  1  79 | 79   6  8 |
+----------+----------+-----------+
| 7   3  6 | 2  9   8 |  5   4  1 |
| 5   8  4 | 7  6   1 | 39  39  2 |
| 9   1  2 | 5  4   3 |  6   8  7 |
+----------+----------+-----------+

----------

Please also note that the zero solution puzzle is easy to check and not considered at the moment.

You say that it's easy to check for a zero solution puzzle.
I don't know what you mean by that exactly.
It's easy to check for cells with no candidates, and for a house where a missing cell value doesn't have a candidate.
Is that what you meant ?

The puzzle above, doesn't have a solution,
It's easy to see that it doesn't.
There's no candidate for '2' in box 6, for example.

The one below, has a BUG+0, but it doesn't have multiple solutions.
It doesn't have any solution, but that isn't immediately obvious.

Code: Select all

+----------+---------+----------+
|  6  9 14 | 5  3  2 |  7  8 14 |
| 45  8  3 | 9  7  1 |  6 45  2 |
|  7  2 15 | 8  6  4 | 13 35  9 |
+----------+---------+----------+
|  2  3  7 | 1  8  5 |  4  9  6 |
| 59  1 59 | 6  4  7 |  8  2  3 |
|  8 46 46 | 3  2  9 |  5  1  7 |
+----------+---------+----------+
| 39  7 69 | 4  1  8 |  2 36  5 |
|  1 46  2 | 7  5  3 |  9 46  8 |
| 34  5  8 | 2  9  6 | 13  7 14 |
+----------+---------+----------+

On the other hand, it has an easy elimination, that leads (via singles) to a state where it's clear that it doesn't have a solution.
There's a skycraper in 4's, for example.
There's a 2-string kite (in 4's).
Maybe that's what you were getting at ?

In any case, there's this:
1) Suppose a puzzle shows a BUG+0.
2) Suppose that your list of solving techniques, is powerful enough to produce an elimination for any candidate where guessing that the candidate is "true" (in some solution), and following it up with naked and hidden single placements, leads to a "zero solution" state.
3) In that case, you can be sure that if no eliminations are detected, then the puzzle has multiple solutions.

Sudoku Explainer's Dynamic Contradiction Forcing Chains, are powerful enough to cover (2).
Denis Berthier's (basic/singles) "braids" are powerful enough.
Added: Since it's all bi-value cells and bi-local candidates, 3D Medusa Coloring (is it?), is probably powerful enough too.

Added3:

Actually you don't need anything as powerful as "braids" or "dynamic contradiction forcing chains".
Simple AICs are sufficient.
3D Medusa is suffiecient, see below, but any elimination coming from a 3D Medusa coloring, can done with a simple AIC too.
If 3D Medusa doesn't produce eliminations, then it can be used to produce solutions to the puzzle. On the other hand, if the puzzle doesn't have a solution, then 3D Medusa will produce an elimination, and the elimination could also come as an AIC elimination.
With that being true, if there are no (simple) AIC eliminations, then the puzzle has multiple solutions

Added2: 3D Medusa -- yeah, that's the one.
After choosing a starting cell, if the coloring stops with no conflicts or eliminations, then the every cell with a colored candidate, will contain a candidate with the opposite color, and for every colored candidate, and each house containing it, will the "other cell" in the house will have the candidate colored with the opposite color. The set of colored candidates (and containing cells) will be a "BUG-Lite + 0", and the colors will correspond to it's (only) two solutions.
If there are additional cells without uncolored candidates at that point, they will form another "BUG-Lite + 0", and choosing two more colors and repeating the process, will lead to either a conflict or elimination, or another fully-colored "BUG-Lite + 0".
If continuing on, leads to the entire grid being filled, then the number of solutions will be 2^N, where N is the number of color pairs.
At that point, solutions to the full puzzle, can be produced by combining one set of colored candidates from each color pair.
If, at any point, a conflict is seen (leading to either a candidate or a color being eliminated) then the entire puzzle will have zero solutions.
Note: That's so simple, it must have been discussed somewhere, long ago.

Cheers,
Blue.

[rjamil]

Hi blue,

You say that it's easy to check for a zero solution puzzle.
I don't know what you mean by that exactly.
It's easy to check for cells with no candidates, and for a house where a missing cell value doesn't have a candidate.
Is that what you meant ?

Correct. By applying Zero State check as described by StrmCkr here in step 2.

The one below, has a BUG+0, but it doesn't have multiple solutions.
It doesn't have any solution, but that isn't immediately obvious.

If Zero State (first resort) detect no-solution at the state, before applying any logical deductions, then BUG+0 (last resort but before t&e) will never be reached after singletons and logical deduction moves.

By the way, run both your given puzzles with my solver. First puzzle immediately detected as Zero State:

Code: Select all

359874126861952..44271368596.8425.131.368.4.524531..68736298541584761..2912543687
 +----------+----------+-----------+
 | 3  5   9 | 8  7  4  | 1   2   6 |
 | 8  6   1 | 9  5  2  | 37  37  4 |
 | 4  2   7 | 1  3  6  | 8   5   9 |
 +----------+----------+-----------+
 | 6  79  8 | 4  2  5  | 79  1   3 |
 | 1  79  3 | 6  8  79 | 4   79  5 |
 | 2  4   5 | 3  1  79 | 79  6   8 |
 +----------+----------+-----------+
 | 7  3   6 | 2  9  8  | 5   4   1 |
 | 5  8   4 | 7  6  1  | 39  39  2 |
 | 9  1   2 | 5  4  3  | 6   8   7 |
 +----------+----------+-----------+
0) Zero state: 2 @ Row 5
1) Error: Unsolvable Sudoku! # U1 # C70 # P22 # N0 # H0 # G0 # D0 # 0.000000

Where as: U1 = Unsolved puzzle count number, C70 = Clues, P22 = Pencil marks, N0 = NS count, H0 = HS count, G0 = Guess count, D0 = Depth count

Second Puzzle solved exactly as per your advise:

Hidden Text: Show

Code: Select all

69.53278..839716.272.864..9237185496.1.6478238..329517.7.4182.51.27539.8.58296.7.
 +------------+---------+------------+
 | 6   9   14 | 5  3  2 | 7   8   14 |
 | 45  8   3  | 9  7  1 | 6   45  2  |
 | 7   2   15 | 8  6  4 | 13  35  9  |
 +------------+---------+------------+
 | 2   3   7  | 1  8  5 | 4   9   6  |
 | 59  1   59 | 6  4  7 | 8   2   3  |
 | 8   46  46 | 3  2  9 | 5   1   7  |
 +------------+---------+------------+
 | 39  7   69 | 4  1  8 | 2   36  5  |
 | 1   46  2  | 7  5  3 | 9   46  8  |
 | 34  5   8  | 2  9  6 | 13  7   14 |
 +------------+---------+------------+
0) Skyscraper: Rows 1 9 Base Cells r1c9 r9c9 Cover Cells r1c3 r9c1 => -4 @ r7c3 r8c3 r2c1 r3c1
 +------------+---------+------------+
 | 6   9   14 | 5  3  2 | 7   8   14 |
 | 5   8   3  | 9  7  1 | 6   45  2  |
 | 7   2   15 | 8  6  4 | 13  35  9  |
 +------------+---------+------------+
 | 2   3   7  | 1  8  5 | 4   9   6  |
 | 59  1   59 | 6  4  7 | 8   2   3  |
 | 8   46  46 | 3  2  9 | 5   1   7  |
 +------------+---------+------------+
 | 39  7   69 | 4  1  8 | 2   36  5  |
 | 1   46  2  | 7  5  3 | 9   46  8  |
 | 34  5   8  | 2  9  6 | 13  7   14 |
 +------------+---------+------------+
1) Hidden single: 4 @ r1c3 from Values 14 in Box 1
 +------------+---------+------------+
 | 6   9   4  | 5  3  2 | 7   8   1  |
 | 5   8   3  | 9  7  1 | 6   45  2  |
 | 7   2   15 | 8  6  4 | 13  35  9  |
 +------------+---------+------------+
 | 2   3   7  | 1  8  5 | 4   9   6  |
 | 59  1   59 | 6  4  7 | 8   2   3  |
 | 8   46  6  | 3  2  9 | 5   1   7  |
 +------------+---------+------------+
 | 39  7   69 | 4  1  8 | 2   36  5  |
 | 1   46  2  | 7  5  3 | 9   46  8  |
 | 34  5   8  | 2  9  6 | 13  7   14 |
 +------------+---------+------------+
2) Naked single: 1 @ r1c9
 +------------+---------+-----------+
 | 6   9   4  | 5  3  2 | 7   8   1 |
 | 5   8   3  | 9  7  1 | 6   45  2 |
 | 7   2   15 | 8  6  4 | 3   35  9 |
 +------------+---------+-----------+
 | 2   3   7  | 1  8  5 | 4   9   6 |
 | 59  1   59 | 6  4  7 | 8   2   3 |
 | 8   46  6  | 3  2  9 | 5   1   7 |
 +------------+---------+-----------+
 | 39  7   69 | 4  1  8 | 2   36  5 |
 | 1   46  2  | 7  5  3 | 9   46  8 |
 | 34  5   8  | 2  9  6 | 13  7   4 |
 +------------+---------+-----------+
3) Hidden single: 4 @ r2c8 from Values 45 in Row 2
 +------------+---------+-----------+
 | 6   9   4  | 5  3  2 | 7   8   1 |
 | 5   8   3  | 9  7  1 | 6   4   2 |
 | 7   2   15 | 8  6  4 | 3   35  9 |
 +------------+---------+-----------+
 | 2   3   7  | 1  8  5 | 4   9   6 |
 | 59  1   59 | 6  4  7 | 8   2   3 |
 | 8   46  6  | 3  2  9 | 5   1   7 |
 +------------+---------+-----------+
 | 39  7   69 | 4  1  8 | 2   36  5 |
 | 1   46  2  | 7  5  3 | 9   6   8 |
 | 34  5   8  | 2  9  6 | 13  7   4 |
 +------------+---------+-----------+
4) Naked single: 5 @ r2c1
 +------------+---------+-----------+
 | 6   9   4  | 5  3  2 | 7   8   1 |
 | 5   8   3  | 9  7  1 | 6   4   2 |
 | 7   2   1  | 8  6  4 | 3   35  9 |
 +------------+---------+-----------+
 | 2   3   7  | 1  8  5 | 4   9   6 |
 | 9   1   59 | 6  4  7 | 8   2   3 |
 | 8   46  6  | 3  2  9 | 5   1   7 |
 +------------+---------+-----------+
 | 39  7   69 | 4  1  8 | 2   36  5 |
 | 1   46  2  | 7  5  3 | 9   6   8 |
 | 34  5   8  | 2  9  6 | 13  7   4 |
 +------------+---------+-----------+
5) Naked single: 1 @ r3c3
 +------------+---------+-----------+
 | 6   9   4  | 5  3  2 | 7   8   1 |
 | 5   8   3  | 9  7  1 | 6   4   2 |
 | 7   2   1  | 8  6  4 | 3   35  9 |
 +------------+---------+-----------+
 | 2   3   7  | 1  8  5 | 4   9   6 |
 | 9   1   59 | 6  4  7 | 8   2   3 |
 | 8   46  6  | 3  2  9 | 5   1   7 |
 +------------+---------+-----------+
 | 39  7   69 | 4  1  8 | 2   36  5 |
 | 1   46  2  | 7  5  3 | 9   6   8 |
 | 34  5   8  | 2  9  6 | 13  7   4 |
 +------------+---------+-----------+
6) Hidden single: 5 @ r3c8 from Values 35 in Row 3
 +------------+---------+-----------+
 | 6   9   4  | 5  3  2 | 7   8   1 |
 | 5   8   3  | 9  7  1 | 6   4   2 |
 | 7   2   1  | 8  6  4 | 3   5   9 |
 +------------+---------+-----------+
 | 2   3   7  | 1  8  5 | 4   9   6 |
 | 9   1   59 | 6  4  7 | 8   2   3 |
 | 8   46  6  | 3  2  9 | 5   1   7 |
 +------------+---------+-----------+
 | 39  7   69 | 4  1  8 | 2   36  5 |
 | 1   46  2  | 7  5  3 | 9   6   8 |
 | 34  5   8  | 2  9  6 | 13  7   4 |
 +------------+---------+-----------+
7) Naked single: 3 @ r3c7
 +------------+---------+----------+
 | 6   9   4  | 5  3  2 | 7  8   1 |
 | 5   8   3  | 9  7  1 | 6  4   2 |
 | 7   2   1  | 8  6  4 | 3  5   9 |
 +------------+---------+----------+
 | 2   3   7  | 1  8  5 | 4  9   6 |
 | 9   1   59 | 6  4  7 | 8  2   3 |
 | 8   46  6  | 3  2  9 | 5  1   7 |
 +------------+---------+----------+
 | 39  7   69 | 4  1  8 | 2  36  5 |
 | 1   46  2  | 7  5  3 | 9  6   8 |
 | 34  5   8  | 2  9  6 | 1  7   4 |
 +------------+---------+----------+
8) Hidden single: 5 @ r5c3 from Values 59 in Row 5
 +------------+---------+----------+
 | 6   9   4  | 5  3  2 | 7  8   1 |
 | 5   8   3  | 9  7  1 | 6  4   2 |
 | 7   2   1  | 8  6  4 | 3  5   9 |
 +------------+---------+----------+
 | 2   3   7  | 1  8  5 | 4  9   6 |
 | 9   1   5  | 6  4  7 | 8  2   3 |
 | 8   46  6  | 3  2  9 | 5  1   7 |
 +------------+---------+----------+
 | 39  7   69 | 4  1  8 | 2  36  5 |
 | 1   46  2  | 7  5  3 | 9  6   8 |
 | 34  5   8  | 2  9  6 | 1  7   4 |
 +------------+---------+----------+
9) Naked single: 9 @ r5c1
 +------------+---------+----------+
 | 6   9   4  | 5  3  2 | 7  8   1 |
 | 5   8   3  | 9  7  1 | 6  4   2 |
 | 7   2   1  | 8  6  4 | 3  5   9 |
 +------------+---------+----------+
 | 2   3   7  | 1  8  5 | 4  9   6 |
 | 9   1   5  | 6  4  7 | 8  2   3 |
 | 8   46  6  | 3  2  9 | 5  1   7 |
 +------------+---------+----------+
 | 3   7   69 | 4  1  8 | 2  36  5 |
 | 1   46  2  | 7  5  3 | 9  6   8 |
 | 34  5   8  | 2  9  6 | 1  7   4 |
 +------------+---------+----------+
10) Hidden single: 4 @ r6c2 from Values 46 in Row 6
 +-----------+---------+----------+
 | 6   9  4  | 5  3  2 | 7  8   1 |
 | 5   8  3  | 9  7  1 | 6  4   2 |
 | 7   2  1  | 8  6  4 | 3  5   9 |
 +-----------+---------+----------+
 | 2   3  7  | 1  8  5 | 4  9   6 |
 | 9   1  5  | 6  4  7 | 8  2   3 |
 | 8   4  6  | 3  2  9 | 5  1   7 |
 +-----------+---------+----------+
 | 3   7  69 | 4  1  8 | 2  36  5 |
 | 1   6  2  | 7  5  3 | 9  6   8 |
 | 34  5  8  | 2  9  6 | 1  7   4 |
 +-----------+---------+----------+
10) Zero state: 4 @ Row 8

If BUG+0 gives multi-solution puzzles, then how about MUG+0 (if exists)? A quick search about MUG gives Coffee mug instead!!

R. Jamil

[tdillon]

Hi blue,

You need to add that in each house, each missing cell value, has at at least one candidate.

Thanks for the more precise statement. I was assuming we've reached the bi-value state after propagation of hidden singles, in which case a missing value would have already been recognized as a conflict.

Thanks also for the interesting zero solution BUG+0 example. The statement in the BUG description on the Hodoku page ("Such a Sudoku has two solutions as well") doesn't acknowledge this possibility.

Sudoku Explainer's Dynamic Contradiction Forcing Chains, are powerful enough to cover (2).
Denis Berthier's (basic/singles) "braids" are powerful enough.
Added: Since it's all bi-value cells and bi-local candidates, 3D Medusa Coloring (is it?), is probably powerful enough too.

For rjamil,
If you're writing code (for the BUG+0 case), a simple and efficient method (that I think subsumes all these things) is to run a strongly connected components algorithm on the binary implication graph that results from the remaining unsolved cells and the standard binary constraints (e.g., see here or here or here). If (and only if) you find a component that contains both a literal and its negation then the puzzle is unsatisfiable. Also, if, during depth first search, you find a literal that's a consequence of its negation then you've found an elimination.

And w.r.t the broader question:

I rethink that there might be some set of logics or one gigantic logic that will detect rest/all of multi-solution puzzles. .... Read Unavoidable Set and Deadly Pattern in Sudopedia. If all multi-solution puzzles always reached to some deadly pattern, then is there a way to detect it and warn multi-solution puzzle?

As the sudopedia link discusses, there are lots of possible unavoidable sets/deadly patterns. If it's late in the game and the puzzle is already in a highly reduced form, as in the binary cell example we've been discussing, then maybe there are recognizable circumstances where a handful of deadly pattern checks can be shown to suffice. But I doubt it's feasible to enumerate deadly pattern checks that are guaranteed to identify any multi-solution puzzle at the point when deductive strategies fail and before doing any search.

[blue]

You need to add that in each house, each missing cell value, has at at least one candidate.

Thanks for the more precise statement. I was assuming we've reached the bi-value state after propagation of hidden singles, in which case a missing value would have already been recognized as a conflict.

I assumed as much Thks.

We're cross posting, I see.
Sorry to step on your latest post, but I wanted to report adding a final comment to my earlier post.

[rjamil]

Hi Tom,

Please note that I have already coded, tested and finalized the BUG+0 warning and BUG+1 move in to my solver. In addition to your provided links, Tison's algorithm also search second solution by solving the puzzle from start skipping the first solution. It won't detect multi-solution puzzle by pure logic.

As per blue "Added2", if 3D Medusa and BUG-Lite+0 used to detect multi-solution puzzle; and it was already discussed long ago, then there must have been implemented by someone in his/her solver too.

I need some practical suggestions as I did not read and understand 3D Medusa and BUG-Lite+0 techniques at the moment.

R. Jamil

[tdillon]

Hi rjamil,

To be clear, I'm not recommending Tison's algorithm as a practical or feasible thing to do! It was more of a theoretical answer to the earlier question of whether there exists a simple deductive procedure that solves any Sudoku and proves the solution is unique. Tison's algorithm does do this. It will either derive an empty clause (the Sudoku has no solution), or it will derive 729 unit clauses (representing a unique assignment of truth values for every value in every cell), or it will terminate without reducing everything to unit clauses (in which case the Sudoku has multiple solutions). You wouldn't have to run it twice or anything. But the procedure is exhaustive, a property it shares with backtracking search, another way to guarantee an answer to whether the puzzle has 0, 1, or 2+ solutions.

But, setting Tison's aside, if you have identified a BUG+0 and you want to tell whether there are 0 solutions or 2+ solutions, what *is* very practical is to run strongly connected components. This is simple to implement and it offers the guarantee that there are zero solutions if and only if some component contains a literal and its negation.

Tom

[rjamil]

Hi Tom,

As the sudopedia link discusses, there are lots of possible unavoidable sets/deadly patterns. If it's late in the game and the puzzle is already in a highly reduced form, as in the binary cell example we've been discussing, then maybe there are recognizable circumstances where a handful of deadly pattern checks can be shown to suffice. But I doubt it's feasible to enumerate deadly pattern checks that are guaranteed to identify any multi-solution puzzle at the point when deductive strategies fail and before doing any search.

This is what I am concerned and asking question about whether someone has already been done the same before or not.

I have a strong feeling that there might be some logical way to detect a multi-solution puzzle, after exhausted/advances all/some logical deductive moves and before applying BUG+n and guess/t&e state (instead of checking the original puzzle state and backtracking involvement). An unavoidable sets checking might be feasible at that state. (As, I see BUG+1 move almost always solves the multi-solution puzzles too. Example here.)

I see why experts always insist to rely on brute force/backtracking because they don't try plenty of logical moves and purely rely on checking the bulk puzzles for uniqueness.

… if you have identified a BUG+0 and you want to tell whether there are 0 solutions or 2+ solutions, what *is* very practical is to run strongly connected components. This is simple to implement and it offers the guarantee that there are zero solutions if and only if some component contains a literal and its negation.

Please note that, I have already implemented BUG+0 state checking routine successfully. Also, I am no more interested in detecting the zero solution based puzzles after implemented StrmCkr provided powerful zero state check routine successfully.

Is running strongly connected components procedure also provides all multi-solution puzzles?

Added as on 20190923: Similarly, a quick check on initial state of vanilla sudoku will also revealed that the puzzle is invalid if given clues are less than 17.

If gsf generated all ED vanilla sudoku catalogue then someone must generate all unavoidable sets/deadly patterns catalogue.

R. Jamil