The New Sudoku Players' Forum

[chi]

What are the minimum conditions that a given puzzle has one and only one solution? How to prove it mathematically? Brutal force by computer does not count.

[Leren]

1. Check that the puzzle has at least 17 clues. A proof of this was published in 2012 and you can read about it here.

2. Fill the puzzle with a full complement of 9 candidates in each cell, put in the clues and mark off all the candidates in site of a clue. Obviously you can't have 2 cells of the same value in the same row, column or box.

Somewhat less obvious is that you must have at least 8 different values in the clues and no two empty rows in a band or columns in a stack.

It's good idea to apply singles logic at this stage. It's possible that you may get to 81 solved cells, in which case the puzzle has a unique solution, and solves with singles.

3. Check that there is a clue in one of many possible "Uniqueness" patterns. There are many of these, which you can look up. They are published on many sites. If one is missed then the puzzle cannot have a unique solution, so you can stop here. There are also a number of "Impossible" patterns in the candidates, the most common one being an "Oddagon". A solution status with an Oddagon can't have a solution.

4. You can then apply one or more of a whole truckload of constructive candidate elimination/ assignment methods, which I will also not detail here.

5. If you run out of solution methods then you can guess a solution from one of the remaining candidates in a cell and run through any consequent constructive candidate elimination/ assignment methods as before. Best to try a cell with just 2 candidates if one is available. If you then find a cell that has no candidates then you can conclude that your last guess was wrong, so go back to the puzzle status before the last guess and try the next candidate.

If you run through all candidates in the last guessing cell and you still come up with a cell with no candidates then the puzzle has no solutions, so you can stop here.

If you don't find a cell with no candidates repeat steps 3 - 5 iteratively. If you get to 81 solved cells then the puzzle has at least 1 solution.

If you have made some guesses, you have to go back to the last guess solution status and look for a second possible solution. If you have not made any guesses then the puzzle has a unique solution.

In practice you don't have to always try every constructive solving method. In fact guessing and singles logic will probably be the fastest way to go.

All this may sound tedious but that's the way the computers do a 0/1/2 solution count and the really fast programmes only take a few micro-seconds, so a manual go on a given puzzle is well within Human capability.

Leren

<Edit> Made some improvements to improve clarity and cover some cases that I'd missed.

<Edit) Added the requirement for no two clueless rows n a band or columns in a stack following eleven's post. Nicely spotted eleven.

[eleven]

I agree with Leren.
There is no mathematical formula, which can tell you, if a puzzle has a unique solution, basically you have to solve it.
Apart from simple necessary conditions like >= 8 given digits, >= 17 clues, no 2 empty rows in a band (or columns in a stack) it becomes very tricky, just to find impossible patterns, see e.g. Serg's thread here.

[chi]

I don't like step 5. What is the difference between guessing and computer brute force?

[chi]

I don't like step 5, guessing. What is the difference between repeated guessing and computer brute force?

[chi]

If no mathematical proof, then how do you know the condition that the number of clues >= 17 can guarantee a puzzle is soluble? Why not >= 16 or>= 18 ?

[Pat]

If no mathematical proof, then how do you know the condition that the number of clues >= 17 can guarantee a puzzle is soluble? Why not >= 16 or>= 18 ?

>16 does not guarantee.

<17 guarantees the number of answers is NOT 1.

[chi]

Very often, I came to a step where I can fill all empty cells with two numbers but unless I use brute force to do repeated guesses, I cannot solve the puzzle according to logic. It is very frustrating.

[Leren]

Hi Chi.

I think the next step would be for you to give an example of a puzzle you cannot solve without guessing. We may be able to give you a non-guessing solution. In any event we will get a feel for how much you know about Sudoku solving.

Leren

[chi]

Hi Leren,
This forum does not offer me a place to send you any attachment. My email addres
If you can send me an email, I can attach my puzzle to you.

[Leren]

You can send me the puzzle in line format like this ....................1..2345..........4.6..752..........5.264..8..................

The .'s are where there is no clue and obviously the clue numbers are as written. Just include the 81 characters in your post.

Leren

[denis_berthier]

What are the minimum conditions that a given puzzle has one and only one solution? How to prove it mathematically? Brutal force by computer does not count.

What you're asking may be interpreted in different ways.

1) Can one express that a puzzle P has a unique solution in pure logic terms? The answer is trivially positive and there are many ways of doing it.
1a) Given a puzzle P expressed as a conjunction of logical conditions EP for the givens, the following formula expresses that any two solutions are identical:

Code: Select all

EP & ∀r ∀c ∀nrc ∀n’rc [value(nrc, r, c) & value(n’rc, r, c) ⇒ nrc = n’rc ]

For details on the formalism, see my book [HLS1 2007, section III.2.5], available as a pdf on ResearchGate: https://www.researchgate.net/publication/280301600_The_Hidden_Logic_of_Sudoku

1b) You can also write a FOL formula with 2x81 variables g1, g81, s1, s81: solution(g1, ... g81, s1, ... s81) which will have the obvious intended meaning.
Uniqueness is expressed as:
∀s1... ∀s81 ∀s'1... ∀s'81 solution(g1, ... g81, s1, ... s81) and solution(g1, ... g81, s'1, ... s'81) ==> s1=s'1 ... s81=s'81

However, as I wrote many times, such formulæ only express that there is only one solution. You can't add then to Sudoku theory to guarantee that a puzzle will have a unique solution. Said otherwise, they allow to check uniqueness, not to guarantee it.


2) Can one express pure logic necessary and sufficient conditions involving only the givens for a puzzle to have a unique solution?
For the necessary part, some conditions are known - some trivial, some less trivial (as mentioned in previous posts).
For the sufficient part, it's an open question, but very unlikely to have a positive answer, let alone a positive answer that would be simpler than solving the puzzle.


3) Barring any brute force procedure, can one prove uniqueness of a solution?
Brute force (i.e. trying all the possible values for each cell) is a very inefficient method. There are at least two much more efficient procedures:
- DFS will find all the solutions (if you only want to check uniqueness, you can stop it as soon as you've found 2; this is how all the generators work).
- T&E(n) will also find all the solutions if n is taken large enough; increasing it progressively ensures all the solutions are found.
DFS and T&E(n) are constructive procedures.

[denis_berthier]

Very often, I came to a step where I can fill all empty cells with two numbers but unless I use brute force to do repeated guesses, I cannot solve the puzzle according to logic. It is very frustrating.

I don't know where you find your puzzles, but if you can always reduce them to at most 2 candidates per cell, it is very likely that they are in no more than T&E(1) and that they can be solved by no more than Subsets and short whips. As Leren said, we need an example.

[eleven]

Just to give an example (this is an originally 15 clue puzzle by coloin with 596 solutions). You are stuck here.

Code: Select all

+----------------------+----------------------+----------------------+
| 5      678    9      | 3      678    1      | 24678  467    24678  |
| 2      678    4      | 678    9      5      | 1      3      678    |
| 1      678    3      | 24     678    24     | 5      9      678    |
+----------------------+----------------------+----------------------+
| 8      9      1      | 5      2      3      | 467    467    467    |
| 3      5      267    | 4678   678    4678   | 9      28     1      |
| 67     4      267    | 9      1      678    | 3      28     5      |
+----------------------+----------------------+----------------------+
| 67     2      678    | 1      4      9      | 678    5      3      |
| 9      1      5      | 2678   3      2678   | 24678  467    24678  |
| 4      3      678    | 2678   5      2678   | 2678   1      9      |
+----------------------+----------------------+----------------------+

There is no logical elimination possible, because any remaining candidate is part of a solution and therefore "valid".
So how could you show, that it is not unique without what you call guessing or brute force (note, that you must not use uniqueness techniques) ? The only way i see is to prove, that the remaining pattern is a MUG. Can you ? This is a big lot harder than recursively guessing digits to find 2 solutions. No one would do it, neither manually nor with programming.

(on the other hand, if a puzzle has a unique solution, there must always be a logical way without "guessing" to solve it - however this can be very complex)

[P.O.]

let's not forget that eliminating incompatible templates gives the solutions, but obviously it's brute force.

Hidden Text: Show

Code: Select all

POMethod TPlimit: 10 cpyVT: T
"PM"

#VT: (1 12 1 12 1 170 170 60 1)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates:NIL NIL NIL NIL NIL NIL NIL NIL NIL
2 3
#VT: (1 12 1 12 1 113 113 42 1)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates:NIL NIL NIL NIL NIL NIL NIL NIL NIL
2 3
#VT: (1 12 1 12 1 111 111 42 1)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates:NIL NIL NIL NIL NIL NIL NIL NIL NIL
2 3 4
#VT: (1 12 1 12 1 108 108 37 1)
Cells: NIL NIL NIL NIL NIL NIL NIL NIL NIL
Candidates:NIL NIL NIL NIL NIL NIL NIL NIL NIL
2 3 4 5 6 7 8 9

TPlimit: 10
Left in pool: (596) 
#VT: (1 12 1 12 1 108 108 37 1)

5      678    9      3      678    1      24678  467    24678           
2      678    4      678    9      5      1      3      678             
1      678    3      24     678    24     5      9      678             
8      9      1      5      2      3      467    467    467             
3      5      267    4678   678    4678   9      28     1               
67     4      267    9      1      678    3      28     5               
67     2      678    1      4      9      678    5      3               
9      1      5      2678   3      2678   24678  467    24678           
4      3      678    2678   5      2678   2678   1      9