## Unique Solution

Everything about Sudoku that doesn't fit in one of the other sections

### Unique Solution

I was wondering why is it that any given sudoku puzzle can be completed to a unique solution?

Thanks
mcarne5252

Posts: 1
Joined: 19 April 2006

Many puzzles actually have more than one solution. These are generally regarded as invalid puzzles.

Tracy
TKiel

Posts: 209
Joined: 05 January 2006

i'd also like to know :|
can someone tell me why the solutions to proper puzzles found in common newspapers are unique ?
nizz

Posts: 3
Joined: 20 April 2006

a single solution will take less space to print..........

tarek

tarek

Posts: 2979
Joined: 05 January 2006

what causes an invalid puzzle?
nizz

Posts: 3
Joined: 20 April 2006

nizz wrote:what causes an invalid puzzle?

Most commonly, too few clues to ensure a unique solution. (I.e. multiple solutions exist.)

Also possible, but rarely seen in print, are puzzles with erroneous clues that will lead to a contradiction (typically making it impossible to fit a certain number in a row, column or box). I.e. no valid solution exists.
vidarino

Posts: 295
Joined: 02 January 2006

one more thing, =p
what is the most number of givens that any invalid puzzle has had?
nizz

Posts: 3
Joined: 20 April 2006

nizz wrote:one more thing, =p
what is the most number of givens that any invalid puzzle has had?

I don't have any statistics for published invalid puzzles, but here's one that has 77 clues (which I made just now);

Code: Select all
`+-------+-------+-------+| . . 3 | 5 9 2 | 6 7 8 | | 2 7 5 | 6 8 1 | 9 3 4 | | 9 8 6 | 3 7 4 | 2 1 5 | +-------+-------+-------+| . . 2 | 7 3 5 | 8 6 9 | | 5 3 8 | 1 6 9 | 4 2 7 | | 7 6 9 | 2 4 8 | 1 5 3 | +-------+-------+-------+| 3 9 1 | 8 5 6 | 7 4 2 | | 6 5 4 | 9 2 7 | 3 8 1 | | 8 2 7 | 4 1 3 | 5 9 6 | +-------+-------+-------+`

So despite having a ton of clues, the 4 remaining cells can each be 1 or 4, leaving two possible solutions. (To make it valid you can set any one of the missing cells to 1 or 4.)
vidarino

Posts: 295
Joined: 02 January 2006

vidarino wrote:
nizz wrote:what causes an invalid puzzle?

Most commonly, too few clues to ensure a unique solution. (I.e. multiple solutions exist.)

Also possible, but rarely seen in print, are puzzles with erroneous clues that will lead to a contradiction (typically making it impossible to fit a certain number in a row, column or box). I.e. no valid solution exists.

Correct on that. also some consider a puzzle invalid if it is asymmectical.
Chessmaster

Posts: 191
Joined: 21 December 2005

mcarne5252 wrote:I was wondering why is it that any given sudoku puzzle can be completed to a unique solution?

The reason that a puzzle gives a unique solution is all to do with the unavoidable sets.

Vidarino's previous post - highlighted this - any valid puzzle from the grid needs to have one of the 4 clues that were absent from his 77 clue puzzle.

The unavoidable set in Vidarino's post can be represented as [11 12 41 42] or [r1c1 r1c2 r4c1 r4c2]

There are three aspects here:
the Final grid
the Given clues
the Generated clues

The Final grid has to be valid before you start.

Take this [different] random complete valid grid [by coincidence it has a 4 set unavoidable in {11 12 41 42}]
Code: Select all
`+---+---+---+|126|347|598||458|169|732||379|285|461|+---+---+---+|213|478|659||584|692|317||697|513|824|+---+---+---+|732|851|946||845|926|173||961|734|285|+---+---+---++---+---+---+|12.|...|...||...|...|...||...|...|...|+---+---+---+|21.|...|...||...|...|...||...|...|...|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+`

all variations of any given glues [taken from this valid completed grid] will therefore not be invalid

Here are 10 randomly generated sudoku puzzles from this grid - and they indeed have at least one clue from this set
Code: Select all
`XX                         XX1..3...98.5........7.2..46......8..9..46..........3.....2.5.....4.9.6.7.96...42....6..7.98..8.6...2.79...4..2..4.8..95..6..3.7....1...............59..1...6.7...8...63...9.45..6...237....4...1.4.............7.975..8.47...5.9....59..1.3.....4..5.26.4.......1.97.........61...4.....58..9..1...7..38.4.32...9..8.........6.73..8..2..........1......792854...1......9..4...31.6.7..38.4.........8..92.1.....734....2.3...98.....9...3....5..1.1...8..9..4..231...75..8.........468.5.......6.7.......63..5.84.....7.2.7..8.4.12..4..6.....692..7......8..73...1.....5......9...34....26.........1.97.....2..4.1...4...5.58.69......7.1.....32.....68.....1...6.7..2.5..6..75...5...9.323...8....2.....6.95....2....9...3..4..........4..2..7..617...85..63....8.58..9.3....2.5...2.....6.......23.769........3.8...4...5..6...9....4.8.`

Code: Select all
`the question of whether it will be solved uniquely is down to whether each "unavoidable set" in the grid has at least one given clue in it.`

Believe it or not - each complete grid has HUNDREDS of of unavoidable sets ! - it is remarkable that some grids can be solved in 17 clues....but almost all grids have a combination of 19 given clues which cover all the sets and define the grid. An average figure of 24 clues [all necessary] can be easily obtained.

Here are some of the unavoidable sets in the above grid ! [NB 11 12 41 42 is there !]
Code: Select all
`.........11 12 13 14 16 17 18 19 22 23 24 25 26 27 28 29 31 35 38 3911 12 13 14 16 18 19 22 23 24 25 26 28 29 31 32 35 36 38 3911 12 13 14 15 17 19 21 22 23 24 25 27 29 31 32 34 3711 12 13 14 15 16 17 19 21 23 24 25 29 31 32 34 36 3711 12 14 15 17 19 22 27 31 32 34 35 37 3911 12 14 15 16 17 19 31 32 34 35 36 37 3911 12 13 14 15 16 18 19 21 22 23 24 25 26 28 29 32 3611 12 13 14 15 16 18 19 21 22 23 25 26 28 29 31 32 34 36 3911 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 2911 12 13 14 15 16 17 18 19 21 22 23 25 26 27 28 29 31 34 3911 13 14 15 16 17 18 21 23 24 25 26 27 28 33 35 36 3711 13 14 15 18 21 22 23 24 25 26 27 28 32 33 35 36 3711 15 19 21 25 28 31 35 38 3911 12 14 15 16 18 19 21 22 23 24 25 26 28 29 32 33 35 36 3811 12 14 15 16 18 19 21 24 26 27 28 32 34 35 37 3911 12 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 33 35 3811 12 13 31 33 42 43 61 63 71 72 73 91 9311 13 31 33 41 43 61 63 71 73 91 9311 15 21 24 29 34 37 42 44 53 58 65 68 69 73 78 82 87 93 9711 15 21 24 42 44 53 56 58 65 68 82 85 87 93 96 9711 17 22 24 34 36 39 42 48 51 56 58 64 68 83 87 93 9911 17 22 24 36 39 41 42 48 51 56 64 65 68 73 76 83 85 87 93 9911 17 22 24 36 39 41 42 48 51 56 64 65 68 73 76 85 87 93 97 9911 17 22 24 36 39 42 48 51 58 64 65 73 75 76 85 87 93 97 9911 17 22 24 36 39 42 48 51 56 58 64 65 68 73 76 83 85 87 93 9911 12 13 38 39 42 47 56 58 61 65 68 73 76 79 85 87 92 9711 12 13 25 29 34 38 39 42 47 54 56 58 61 65 73 76 79 85 87 92 9711 13 25 29 34 38 41 42 47 54 56 61 68 73 79 85 86 92 93 9711 13 24 25 29 34 38 41 42 47 54 58 61 65 68 73 79 92 93 9711 13 38 39 42 47 56 58 61 65 68 76 79 85 86 87 92 9311 13 25 29 34 38 39 42 47 54 56 58 61 65 76 79 85 86 87 92 9311 13 25 29 34 38 39 42 47 54 56 58 61 65 73 76 79 85 87 92 93 9711 16 24 27 29 32 39 42 45 56 59 63 65 68 71 73 76 85 88 93 9411 12 19 23 24 35 39 41 46 52 56 58 65 67 74 76 81 87 93 9811 19 23 24 34 35 39 73 74 81 85 87 93 9711 12 41 4211 18 26 29 33 34 39 42 49 56 58 62 65 68 76 77 84 85 87 91 9311 14 15 24 28 31 39 42 44 53 58 65 69 72 76 78 82 89 93 9611 15 21 24 28 31 39 42 44 53 58 65 69 72 76 78 82 89 93 9611 14 22 24 31 36 42 48 51 58 64 6611 14 17 31 36 39 64 66 83 87 93 9911 14 17 22 24 28 42 48 51 57 5811 17 22 24 36 39 42 43 48 51 58 64 65 66 72 75 76 83 87 89 95 9911 17 22 28 31 39 43 48 51 57 72 75 83 87 89 93 95 9911 13 24 25 38 39 42 43 47 54 58 61 65 66 72 79 86 87 89 92 93 9511 13 14 24 25 28 31 38 39 43 47 54 57 58 61 66 72 76 79 86 87 92 9511 14 24 27 28 31 39 87 88 8911 14 24 28 31 39 58 59 88 8911 16 24 27 32 39 42 45 57 59 63 65 71 76 87 89 93 9411 16 24 27 28 32 39 42 45 57 58 59 63 65 71 76 93 9411 14 23 24 31 35 43 46 52 57 58 66 67 72 74 81 87 93 95 9811 14 19 23 24 28 57 58 81 87 89 93 9811 14 24 28 31 39 57 58 87 8911 14 24 26 28 31 33 39 42 43 49 55 57 58 62 65 66 72 77 84 89 91 93 9511 14 18 24 26 28 33 39 43 49 55 57 58 62 66 72 77 84 87 89 91 93 9511 13 15 21 24 25 42 44 47 53 54 58 61 65 69 76 78 79 82 86 87 93 9611 13 15 21 24 25 37 38 42 44 47 61 65 69 78 79 92 9311 13 15 21 24 25 37 39 42 44 47 61 65 69 76 79 86 87 92 9311 15 21 24 37 38 39 44 47 54 58 65 6911 13 24 25 37 38 42 47 54 58 61 65 76 78 82 87 92 93 9611 13 24 25 37 38 39 42 44 53 54 61 65 76 78 79 82 87 93 9611 13 15 21 24 25 38 39 53 54 58 61 65 69 78 7911 15 21 24 37 39 42 44 53 58 65 69 76 78 82 87 93 9611 15 21 24 42 44 49 62 65 6911 15 18 21 24 26 33 37 42 44 53 55 62 65 77 78 82 84 91 9611 17 22 24 25 36 39 42 48 51 54 58 61 65 75 76 83 87 93 9911 13 17 22 24 36 38 39 42 47 48 54 58 61 64 65 75 76 79 83 86 87 92 93 9911 16 17 22 24 27 42 45 48 51 59 63 65 71 76 83 88 93 94 9911 17 22 27 32 39 42 48 51 58 59 83 87 88 93 9911 16 22 24 32 36 42 45 63 64 65 71 75 76 93 9411 16 17 32 36 39 42 45 48 51 58 63 64 71 75 83 87 93 94 9911 17 22 23 24 35 36 39 46 48 51 52 64 65 67 81 87 93 98 9911 17 22 23 24 36 39 46 48 51 52 64 67 74 76 81 87 93 98 9911 17 19 22 24 35 36 39 42 46 48 51 52 58 64 65 67 98 9911 17 19 22 24 36 39 42 46 48 51 52 58 64 67 74 76 98 9911 17 19 23 24 35 39 64 65 74 75 81 83 87 93 9911 17 19 23 24 35 36 39 74 75 76 81 83 87 93 9911 19 22 23 24 35 39 42 46 48 51 58 65 67 74 76 81 83 87 93 9811 19 22 23 24 35 39 42 48 51 58 64 65 74 75 81 8311 19 22 23 24 35 36 39 42 48 51 58 74 75 76 81 8311 17 22 24 36 39 42 48 51 58 64 65 75 76 83 87 93 9911 13 42 47 52 58 61 67 81 87 92 93 9811 13 24 25 52 54 58 61 65 67 81 87 92 93 9811 13 24 25 42 46 52 54 61 65 74 76 92 9311 13 19 23 24 35 39 42 46 47 61 65 67 74 76 92 9311 13 19 23 25 35 38 42 46 47 52 54 58 74 79 81 86 87 93 9811 13 19 23 24 25 35 38 46 47 54 58 65 67 74 79 81 86 87 93 9811 13 19 23 24 25 35 38 42 46 47 61 65 67 74 76 79 81 86 92 93 9811 19 23 24 25 35 38 39 42 46 52 54 61 65 74 76 79 81 86 92 93 9811 19 23 24 35 38 39 46 47 54 58 65 67 74 79 81 86 87 93 9811 19 23 24 35 38 39 42 46 47 61 65 67 74 76 79 81 86 92 93 9811 13 24 25 38 39 42 47 54 58 61 65 76 79 86 87 92 9311 13 18 33 39 42 49 55 58 61 62 65 92 9311 18 24 25 33 38 39 42 47 54 58 61 65 76 79 86 87 91 92 9311 16 24 27 32 39 42 45 58 59 63 65 71 76 87 88 93 9411 16 24 27 32 39 42 49 55 58 59 62 63 65 71 76 87 88 93 9411 18 32 33 39 42 45 49 55 58 63 65 91 9311 19 23 24 35 39 42 46 52 58 65 67 74 76 81 87 93 9811 18 33 39 42 49 55 58 62 65 91 93................`

The reason I have printed these sets is that they all refer to clue 11

Take this partial puzzle with these five Given clues
Code: Select all
`+---+---+---+|.2.|...|...||45.|...|...||...|...|..1|+---+---+---+|...|...|...||...|...|...||...|...|...|+---+---+---+|...|...|...||...|...|...||..1|...|...|+---+---+---+ these clues are 12,21,22,39,93.  The clue at position 11 has got to be a 1 and therefore can be Inserted `

But it can be seen that all these unavoidable sets not only have the 11 clue but also at least one of the 12,21,22,39,93 clues -
Code: Select all
`Therefore a generated clue can be inserted when ALL the unavoidable sets with this clue in it already have in them at least one given clue.`

the program "unavoid" in "checker" will print out all the smaller unavoidable sets in any given grid. http://www.maths.nuim.ie/staff/gmg/sudoku/

All the Given clues in a valid minimal puzzle combine to hit EVERYONE of the many unavoidable sets - therefore there are NO unavoidable sets not hit with at least one Given clue.

All the Generated clues are superfluous as they are not needed to ensure every unavoidable set has at least one Given clue in it.

Whether the Given clues can be optimally picked to produce a puzzle with 17,18,19.....or 32,33,34,or 35 is I believe circumstancial.

I believe it is very challenging to write a computor program to incorporate this theory into finding the minimum and maximum hitting sets for a grid - the options are vast - it would be a real feat.

C
coloin

Posts: 1790
Joined: 05 May 2005

coloin wrote:I believe it is very challenging to write a computor program to incorporate this theory into finding the minimum and maximum hitting sets for a grid
Worse than "very challenging", the hitting set problem is NP-complete.
Red Ed

Posts: 633
Joined: 06 June 2005

Thank-you for that. I have to admit that I foolishly turned off when I heard this "NP" phrase in the past.

I have subsequently looked up its meaning......

For non graduate math people like me who didn't know !

From
http://tomclegg.net/npcomplete
Code: Select all
`"NP stands for Nondeterministic Polynomial. Which is concise, if not exactly illuminating. If a problem is NP, that means you can easily verify whether someone has found the right answer. For example, if someone tells you that the combination to their suitcase is 4-5-1, then you can just dial up 4-5-1 and see if it opens. The important thing is that it's easy to verify whether you've got the right answer, but it's not necessarily easy, or even feasible, to come up with the right answer in the first place. So, an example of an NP problem is, "find the combination to this suitcase." If you come up with a way to answer that question, it's easy for me to tell whether you're right......So for practical purposes, NP-complete problems are the ones that we know are hard, even though we can't prove that they're hard.  `

Am I right in saying that it is understatement for its so utterly impossible that nobody should even think about trying to solve it ?

I think trying to find the maximum number of clues is "NP/NP-complete"......
.....You are never going to know whether it is impossible to go one better.....unless someone comes up with a proof that is !
coloin

Posts: 1790
Joined: 05 May 2005

### Unique solution

The problem of a the unique solution is easy to understand

To be a Sudoku a Latin square MUST have a unique solution.
If you have multiply solution it's not a Sudoku.
tio make a Sudoko you begin with a Latin suqre and you hides clues until you have a uniq solution so ALL the Sudoku have a unique solution!

Papy
Papy

Posts: 131
Joined: 15 August 2006

Having a sudoku with multiple solutions is a bit like having a crossword with multiple solutions. Such things exist but they are not crosswords in the original sense.
underquark

Posts: 299
Joined: 06 September 2005

### Other theory

Hi,

All the Valid Sudoku grids are equal:
Number of row, of each digit, row sum, ...
So every grid can receive 17 clues puzzle
BEWARE:
When I said a puzzle, the clue are not necessary symmetric

Symmetric are only particular Puzzle not special puzzle
That I want to say is you do 17 clues, puzzle and some time you have symmetric. You can choose to remember only symmetrics but it's only a selection.
A Sudoku program is 'grid independent’: demonstration is you change numbers by letters or other symbols it's always a Sudoku!
So the grid have no incidence on the dispositions of the clues!

Yes but what?
In fact when you have to place a value you analyse FOUR conditions
Those four conditions are also available to dispose tha clue
What are those 4 conditions?
1- Is this number is row compatible (i/e it is authorized or no?)
2- The number is colon compatible?
3- The number is box compatible
4- The number is number compatible.

What is this strange 4?
In fact in a grid we never take care that each digit (1-9) must be present at 9 times. It's automatic. If we apply the three firsts conditions we automatically have each digit 9 times.

Nobody find how to use this 'specification' to solve the grids so we never
take care of that.

But when you make a puzzle you must consider this problem and study the digits
But I say that the digit have no influence on the grid!
It's true. In fact the important is the number of each value

1..3...98
.5.......
.7.2..46.
.....8..9
..46.....
.....3...
..2.5....
.4.9.6.7.
96...42..

Now compute the frequency of each digit
1 1 time,2 3 times,3 2 times,4 4 timess,5 2 timess,6 4 timess,7 2 times;8 2 times,9 4 times
Sort this list
You can permute all the digit for example permute the one and the 9 youy always have the same repartition

1,2,2,2,2,3,4,4,4

Now more classic compute the repartition
by row and by colon
4,1,4,2,2,1,2,4,4
2,4,2,4,1,4,2,3,2

sort

1,1,2,2,2,4,4,4,4
1,2,2,2,2,3,4,4,4
Don't forget the box
3,2,4,1,3,1,4,4,2
sorted
1,1,2,2,3,3,4,4,4

Finally you get:

Digits: 1,2,2,2,2,3,4,4,4
Rows: 1,1,2,2,2,4,4,4,4
Cols: 1,2,2,2,2,3,4,4,4
Box: 1,1,2,2,3,3,4,4,4

You can compute those serial for each grid. If you have the same for two grids the girds are the same in fact only checked!

Now if we want to make a new Sudoku we don’ use a Latin square we only have to use this serial and the problem will necessary be good, one solution
Using this technique you can find that in the Gordon File(Thanks to him)
you only have 1000 set of serials 35000 are mixed!

To build a new problem it's know very easy we just have to respect the numbers

Digit;
1,2,2,2,2,3,4,4,4 => 988772255444333311116666

Rows

1,1,2,2,2,4,4,4,4 => R4 1 R8 1? R2 2 R9 2 R7 2 R3 4 R4 4 R5 4 R6 4

That is my theory and I don't found situation impossible where it's was false but I not objectif: I'm the father so I give it to you to find default (or confirmation)

I think that is the generic generator using a Database to be generate:
Analysing the serial we can surely find the connexions of the serials and after generate all the serials or write a universal generator
Sudoku is not a PN

Only those who are enough creasy to think that they can change the word change it!!!!
Einstein

PS I have a genetic malady so sometimes my messages are not lisible
Excuse me...
Papy

Posts: 131
Joined: 15 August 2006