The New Sudoku Players' Forum

[Red Ed]

Can you, as the puzzle stands, replace these numbers with the information available before attempting to solve the puzzle?

If you cannot, then these clues are not derivable from the information available and, as such, are independent clues.

I suspect this is at the heart of the confusion surrounding Gupta's grid: what do we mean by derivable?

I've been taking the view, as have gsf and Moschopulus (apparently), that a clue is derivable iff you can delete it without affecting the number of solutions. Perhaps your definition of derivable is limited to techniques that a human solver might be expected to use ...?

I think that "independent" has been ill-defined to this point

Really? What was wrong with my "independence ... should just be that the number of solutions increases with the removal of any single clue" ?

[gsf]

I think that "independent" has been ill-defined to this point

Really? What was wrong with my "independence ... should just be that the number of solutions increases with the removal of any single clue" ?

sorry, that's fine, and it fits nicely with minmal puzzles

[coloin]

In a minimal puzzle from a valid grid there are two sorts of clues

"Given" clues and "Inserted" clues

"Given" clues are the original clues

"Inserted" clues are derived by logic from the "Given" clues.

What makes a clue Insertable ?

Well its all to do with the unavoidable sets......[Just as whether a puzzle can be reduced to 17,18,19 or 20 given clues ].......

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 is a 1 - and can be Inserted

And here is a randomly filled valid grid

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

Using unav27 program these are a few of the unavoidable sets which include the clue at position 11..............

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

It can be shown that all these unavoidable sets have at least one of the 12,21,22,39,93 clues

therefore the 1 at position 11 is Insertable.

When you insert a clue it means there is no unavoidable sets with this clue. Those sets have all been hit by the Given clues.

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 a Given clue.

Whether the Given clues can be optimally picked to produce a puzzle with 17,18,19 or 20 clues is circumstancial.

Of course the 32 clues are picked maximally suboptimally !

[Moschopulus]

I've been taking the view, as have gsf and Moschopulus (apparently), that a clue is derivable iff you can delete it without affecting the number of solutions. Perhaps your definition of derivable is limited to techniques that a human solver might be expected to use ...?

Agreed. I was actually only thinking about sudoku puzzles, which by definition have exactly one completion.

I would define a clue D (=digit & cell) to be derivable from a set of clues S if every completion of S contains D.

This agrees with your definition. (I think)

After all that, I don't like using the word "derivable". Its common English usage suggests that some process of logical deduction is going on, and we want to avoid that sort of thing.

[Red Ed]

After all that, I don't like using the word "derivable". Its common English usage suggests that some process of logical deduction is going on, and we want to avoid that sort of thing.

Seconded! Coloin's "inserted clues ... derived by logic" should be banned, too.

[coloin]

I know you are discussing whether a puzzle is minimal.........but why is the use of the word logic incorrect in this context ?

Normally whether a puzzle is minimal or not - this is performed by computor - if removing a clue gives multiple grid completions then this clue is essential. I agree it is impossible for human solvers to be certain that a clue is essential.

In solving puzzles most clues are inserted by logic in my experience.

[Red Ed]

I know you are discussing whether a puzzle is minimal.........but why is the use of the word logic incorrect in this context ?

I have already asserted that I was dealing with a minimal puzzle.......the inserting of the remaining clues is usually performed [not by me of course] by logic of one form or another.

"Logic" is probably the single most controversial word on this forum. I don't want to read arguments about the semantics of whether or not a clue is logically derivable. It would be better to use neutral language such as "deleting the clue increases the number of solutions", rather than talk in terms that may suggest we're talking about pencil-and-paper solving techniques.

btw, further to your note on unavoidables, I can search those in 'sf-big.txt' to find what looks like (need to check ...) an independent 31 on the SF grid. This seems like a reasonable alternative method to random clue deletion.

[coloin]

Sorry.
My post was slightly out of context to your discussion on minimal puzzles.

Except to say that a given valid puzzle has given clues which hit a clue in every unavoidable set - and the relevance might be that a minimal valid puzzle has given clues which the removal of any one of these clues reveals one or more uncovered unavoidable sets from the original grid.


Yes a check on the large number of unavoidables would be a reasonable step.

Interestingly when you are inserting "Given" clues to make a puzzle using a valid grid - a high percentage of the [small,relevant] unavoidables get covered with the first 12 clues - it is the last 20 or so unavoidables which have to be covered in 5 clues to make a 17 [very rarely do they coincide] or in 7 or 8 clues to make a 19 or 20. [very common]

[deam3r]

vidarino



Joined: 02 Jan 2006
Posts: 78
Location: Haugesund, Norway
Posted: Sat Feb 11, 2006 8:10 am Post subject:

--------------------------------------------------------------------------------

Yep, 77 it is. Here's a 77-clue grid that needs one more to have a unique solution;

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

---
|||GOOD|||CALL|||

[sg]

I've mailed him, seeking clarification.

Thanks for the mail. Glad to be of help.

Clarification in reponse to Gordon's post on Feb 11: I'm afraid the following sounds extremely pedantic, but if I put it down like this, I think I won't make a mistake.

The following definitions are made for any fixed puzzle (ie, a puzzle with given clues)
1) Elementary propositions in Su Doku are "B contains {N}" or "B does not contain {N}" (where B is a box and N is a number). Compound propositions, which are unions of simple propositions such "B contains one of {N1,N2,...} and none of {M1,M2,...}" are less interesting for this definition.
2) In a proper Su Doku, all elementary propositions are provably true or false, given the clues. (This defines proper Su Doku).
3) In a good Su Doku exactly one of the 9 elementary propositions of the form "B contains {N}" is true for each B, given the clues. (This is a definition of "good Su Doku").
4) Some elementary propositions are true or false because the box they refer to contain a clue. Such statements are "trivial propositions" (either trivially true or trivially false).

Now the definition of a maximum Su Doku:
5) If a good Su Doku remains a good Su Doku after removal of a clue, then that clue is called a derivable clue.
6) Removal of all derivable clues from a good Su Doku leads to an irreducible Su Doku. (Any irreducible Su Doku is a good Su Doku, by this definition)
7) The set of irreducible Su Dokus with maximum number of clues is called a maximum Su Doku.
8) The set of irreducible Su Sokus with minimum number of clues is called a minimum Su Doku.

In other words, I agree with Moschopulus, provided that the definition of minimum on the forum is the same as my definition of irreducible above. I would prefer to call a puzzle irreducible (or good but reducible), and reserve the words minimum and maximum for counts of the number of clues.

MCC's post of Feb 11 contains a good example of what I mean by an elementary proposition in (1) above and proceeds to give an example of what I call a proof or derivation in (2) above.

The maximum Su Doku example in http://theory.tifr.res.in/~sgupta/sudoku/expert.html is an impostor for the two reasons already noticed on the forum: it is not a good Su Doku (as pointed out on Feb 12: 6 does not fit into the center 3X3 box) and the Su Doku is not irreducible, Thanks for checking this; I'll modify the figure on the web page with acknowledgements to this thread.

The best that I can dash off quickly is the 29 clue irreducible Su Doku:

..3|..6|78.
.56|.8.|12.
78.|.2.|.5.
---+---+---
.7.|34.|...
364|8..|...
...|2.1|...
---+---+---
6.2|.14|...
81.|...|...
...|5..|...

This has more clues than the example MCC gives in his post of Feb 11 (or in the three irreducible versions of that problem which are given by gsf, although I haven't checked their irreducibility myself).

[gsf]

The best that I can dash off quickly is the 29 clue irreducible Su Doku:

Code: Select all

  ..3|..6|78.
  .56|.8.|12.
  78.|.2.|.5.
  ---+---+---
  .7.|34.|...
  364|8..|...
  ...|2.1|...
  ---+---+---
  6.2|.14|...
  81.|...|...
  ...|5..|...


this puzzle is not minimal (irreducable)

Code: Select all

[6,6]=1

is superfluous

[sg]

The best that I can dash off quickly is the 29 clue irreducible Su Doku:

Code: Select all

  ..3|..6|78.
  .56|.8.|12.
  78.|.2.|.5.
  ---+---+---
  .7.|34.|...
  364|8..|...
  ...|2.1|...
  ---+---+---
  6.2|.14|...
  81.|...|...
  ...|5..|...


this puzzle is not minimal (irreducable)

Code: Select all

[6,6]=1

is superfluous

If you remove this 1 and try to solve the puzzle, then you have a choice of 7 or 1 here, and each of these choices leads eventually to a solution. So removal of the 1 from [6,6] makes it improper: in other words it is needed.

[vidarino]

If you remove this 1 and try to solve the puzzle, then you have a choice of 7 or 1 here, and each of these choices leads eventually to a solution. So removal of the 1 from [6,6] makes it improper: in other words it is needed.

No, gsf is right. The 1 is superfluous. The puzzle is still solvable and unique without it. And replacing it with a 7 leads to a contradiction later:

Vidar

[sg]

No, gsf is right. The 1 is superfluous. The puzzle is still solvable and unique without it. And replacing it with a 7 leads to a contradiction later:

Yes, gsf and vidar are correct about the example; it is good but reducible and hence cant be an example of maximum Su Doku (perhaps removing the 1 does it, or not...)

In any case, the challenge is to
1) Exhibit the maximum irreducible Su Doku
2) Prove that a larger irreducible example is impossible

Given the state of affairs for the minimum irreducible Su Doku, I guess step (2) will take some time. I will continue to watch this thread for the current contender for step (1).

[vidarino]

I actually had a 31-clue minimal puzzle in my database.

Code: Select all

+-------+-------+-------+
| . . 2 | 9 . 1 | . . 7 |
| . . 6 | . 2 . | . . . |
| . . . | . 7 6 | 2 . 1 |
+-------+-------+-------+
| . 7 1 | . 9 . | 3 . . |
| . 8 3 | . . . | . . 2 |
| . 2 9 | . . 5 | 7 1 8 |
+-------+-------+-------+
| . . . | . 5 . | . . 4 |
| . . . | . 8 . | . 6 . |
| . . . | 4 . 9 | . 7 3 |
+-------+-------+-------+