The New Sudoku Players' Forum

[mcarne5252]

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

Thanks

[TKiel]

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

Tracy

[nizz]

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 ?

[tarek]

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

tarek

[nizz]

what causes an invalid puzzle?

[vidarino]

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.

[nizz]

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

[vidarino]

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.)

[Chessmaster]

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.

[coloin]

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

[Red Ed]

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.

[coloin]

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 !

[Papy]

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

[underquark]

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.

[Papy]

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...