Unique Solution

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

Unique Solution

Postby mcarne5252 » Wed Apr 19, 2006 11:34 pm

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

Postby TKiel » Thu Apr 20, 2006 12:00 am

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

Tracy
TKiel
 
Posts: 209
Joined: 05 January 2006

Postby nizz » Thu Apr 20, 2006 10:04 pm

i'd also like to know :|
how about this question,
can someone tell me why the solutions to proper puzzles found in common newspapers are unique ?
nizz
 
Posts: 3
Joined: 20 April 2006

Postby tarek » Thu Apr 20, 2006 10:08 pm

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

tarek
User avatar
tarek
 
Posts: 2607
Joined: 05 January 2006

Postby nizz » Thu Apr 20, 2006 10:35 pm

what causes an invalid puzzle?
nizz
 
Posts: 3
Joined: 20 April 2006

Postby vidarino » Thu Apr 20, 2006 10:43 pm

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

Postby nizz » Thu Apr 20, 2006 11:03 pm

one more thing, =p
what is the most number of givens that any invalid puzzle has had?
nizz
 
Posts: 3
Joined: 20 April 2006

Postby vidarino » Thu Apr 20, 2006 11:08 pm

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

Postby Chessmaster » Fri Apr 21, 2006 8:28 pm

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

Postby coloin » Sat Apr 22, 2006 8:15 pm

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                         XX
1..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 39
11 12 13 14 16 18 19 22 23 24 25 26 28 29 31 32 35 36 38 39
11 12 13 14 15 17 19 21 22 23 24 25 27 29 31 32 34 37
11 12 13 14 15 16 17 19 21 23 24 25 29 31 32 34 36 37
11 12 14 15 17 19 22 27 31 32 34 35 37 39
11 12 14 15 16 17 19 31 32 34 35 36 37 39
11 12 13 14 15 16 18 19 21 22 23 24 25 26 28 29 32 36
11 12 13 14 15 16 18 19 21 22 23 25 26 28 29 31 32 34 36 39
11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29
11 12 13 14 15 16 17 18 19 21 22 23 25 26 27 28 29 31 34 39
11 13 14 15 16 17 18 21 23 24 25 26 27 28 33 35 36 37
11 13 14 15 18 21 22 23 24 25 26 27 28 32 33 35 36 37
11 15 19 21 25 28 31 35 38 39
11 12 14 15 16 18 19 21 22 23 24 25 26 28 29 32 33 35 36 38
11 12 14 15 16 18 19 21 24 26 27 28 32 34 35 37 39
11 12 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29 33 35 38
11 12 13 31 33 42 43 61 63 71 72 73 91 93
11 13 31 33 41 43 61 63 71 73 91 93
11 15 21 24 29 34 37 42 44 53 58 65 68 69 73 78 82 87 93 97
11 15 21 24 42 44 53 56 58 65 68 82 85 87 93 96 97
11 17 22 24 34 36 39 42 48 51 56 58 64 68 83 87 93 99
11 17 22 24 36 39 41 42 48 51 56 64 65 68 73 76 83 85 87 93 99
11 17 22 24 36 39 41 42 48 51 56 64 65 68 73 76 85 87 93 97 99
11 17 22 24 36 39 42 48 51 58 64 65 73 75 76 85 87 93 97 99
11 17 22 24 36 39 42 48 51 56 58 64 65 68 73 76 83 85 87 93 99
11 12 13 38 39 42 47 56 58 61 65 68 73 76 79 85 87 92 97
11 12 13 25 29 34 38 39 42 47 54 56 58 61 65 73 76 79 85 87 92 97
11 13 25 29 34 38 41 42 47 54 56 61 68 73 79 85 86 92 93 97
11 13 24 25 29 34 38 41 42 47 54 58 61 65 68 73 79 92 93 97
11 13 38 39 42 47 56 58 61 65 68 76 79 85 86 87 92 93
11 13 25 29 34 38 39 42 47 54 56 58 61 65 76 79 85 86 87 92 93
11 13 25 29 34 38 39 42 47 54 56 58 61 65 73 76 79 85 87 92 93 97
11 16 24 27 29 32 39 42 45 56 59 63 65 68 71 73 76 85 88 93 94
11 12 19 23 24 35 39 41 46 52 56 58 65 67 74 76 81 87 93 98
11 19 23 24 34 35 39 73 74 81 85 87 93 97
11 12 41 42
11 18 26 29 33 34 39 42 49 56 58 62 65 68 76 77 84 85 87 91 93
11 14 15 24 28 31 39 42 44 53 58 65 69 72 76 78 82 89 93 96
11 15 21 24 28 31 39 42 44 53 58 65 69 72 76 78 82 89 93 96
11 14 22 24 31 36 42 48 51 58 64 66
11 14 17 31 36 39 64 66 83 87 93 99
11 14 17 22 24 28 42 48 51 57 58
11 17 22 24 36 39 42 43 48 51 58 64 65 66 72 75 76 83 87 89 95 99
11 17 22 28 31 39 43 48 51 57 72 75 83 87 89 93 95 99
11 13 24 25 38 39 42 43 47 54 58 61 65 66 72 79 86 87 89 92 93 95
11 13 14 24 25 28 31 38 39 43 47 54 57 58 61 66 72 76 79 86 87 92 95
11 14 24 27 28 31 39 87 88 89
11 14 24 28 31 39 58 59 88 89
11 16 24 27 32 39 42 45 57 59 63 65 71 76 87 89 93 94
11 16 24 27 28 32 39 42 45 57 58 59 63 65 71 76 93 94
11 14 23 24 31 35 43 46 52 57 58 66 67 72 74 81 87 93 95 98
11 14 19 23 24 28 57 58 81 87 89 93 98
11 14 24 28 31 39 57 58 87 89
11 14 24 26 28 31 33 39 42 43 49 55 57 58 62 65 66 72 77 84 89 91 93 95
11 14 18 24 26 28 33 39 43 49 55 57 58 62 66 72 77 84 87 89 91 93 95
11 13 15 21 24 25 42 44 47 53 54 58 61 65 69 76 78 79 82 86 87 93 96
11 13 15 21 24 25 37 38 42 44 47 61 65 69 78 79 92 93
11 13 15 21 24 25 37 39 42 44 47 61 65 69 76 79 86 87 92 93
11 15 21 24 37 38 39 44 47 54 58 65 69
11 13 24 25 37 38 42 47 54 58 61 65 76 78 82 87 92 93 96
11 13 24 25 37 38 39 42 44 53 54 61 65 76 78 79 82 87 93 96
11 13 15 21 24 25 38 39 53 54 58 61 65 69 78 79
11 15 21 24 37 39 42 44 53 58 65 69 76 78 82 87 93 96
11 15 21 24 42 44 49 62 65 69
11 15 18 21 24 26 33 37 42 44 53 55 62 65 77 78 82 84 91 96
11 17 22 24 25 36 39 42 48 51 54 58 61 65 75 76 83 87 93 99
11 13 17 22 24 36 38 39 42 47 48 54 58 61 64 65 75 76 79 83 86 87 92 93 99
11 16 17 22 24 27 42 45 48 51 59 63 65 71 76 83 88 93 94 99
11 17 22 27 32 39 42 48 51 58 59 83 87 88 93 99
11 16 22 24 32 36 42 45 63 64 65 71 75 76 93 94
11 16 17 32 36 39 42 45 48 51 58 63 64 71 75 83 87 93 94 99
11 17 22 23 24 35 36 39 46 48 51 52 64 65 67 81 87 93 98 99
11 17 22 23 24 36 39 46 48 51 52 64 67 74 76 81 87 93 98 99
11 17 19 22 24 35 36 39 42 46 48 51 52 58 64 65 67 98 99
11 17 19 22 24 36 39 42 46 48 51 52 58 64 67 74 76 98 99
11 17 19 23 24 35 39 64 65 74 75 81 83 87 93 99
11 17 19 23 24 35 36 39 74 75 76 81 83 87 93 99
11 19 22 23 24 35 39 42 46 48 51 58 65 67 74 76 81 83 87 93 98
11 19 22 23 24 35 39 42 48 51 58 64 65 74 75 81 83
11 19 22 23 24 35 36 39 42 48 51 58 74 75 76 81 83
11 17 22 24 36 39 42 48 51 58 64 65 75 76 83 87 93 99
11 13 42 47 52 58 61 67 81 87 92 93 98
11 13 24 25 52 54 58 61 65 67 81 87 92 93 98
11 13 24 25 42 46 52 54 61 65 74 76 92 93
11 13 19 23 24 35 39 42 46 47 61 65 67 74 76 92 93
11 13 19 23 25 35 38 42 46 47 52 54 58 74 79 81 86 87 93 98
11 13 19 23 24 25 35 38 46 47 54 58 65 67 74 79 81 86 87 93 98
11 13 19 23 24 25 35 38 42 46 47 61 65 67 74 76 79 81 86 92 93 98
11 19 23 24 25 35 38 39 42 46 52 54 61 65 74 76 79 81 86 92 93 98
11 19 23 24 35 38 39 46 47 54 58 65 67 74 79 81 86 87 93 98
11 19 23 24 35 38 39 42 46 47 61 65 67 74 76 79 81 86 92 93 98
11 13 24 25 38 39 42 47 54 58 61 65 76 79 86 87 92 93
11 13 18 33 39 42 49 55 58 61 62 65 92 93
11 18 24 25 33 38 39 42 47 54 58 61 65 76 79 86 87 91 92 93
11 16 24 27 32 39 42 45 58 59 63 65 71 76 87 88 93 94
11 16 24 27 32 39 42 49 55 58 59 62 63 65 71 76 87 88 93 94
11 18 32 33 39 42 45 49 55 58 63 65 91 93
11 19 23 24 35 39 42 46 52 58 65 67 74 76 81 87 93 98
11 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: 1629
Joined: 05 May 2005

Postby Red Ed » Sat Apr 22, 2006 9:32 pm

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

Postby coloin » Wed Apr 26, 2006 8:28 pm

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: 1629
Joined: 05 May 2005

Unique solution

Postby Papy » Fri Aug 18, 2006 7:01 pm

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

Postby underquark » Fri Aug 18, 2006 11:16 pm

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

Postby Papy » Sat Aug 19, 2006 11:00 am

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


Return to General