The New Sudoku Players' Forum

[gsf]

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

dropping [6,6]=1 makes it minimal

[Moschopulus]

Just to be clear.

The question goes back to 3 September 2005, and this post by giant:

http://forum.enjoysudoku.com/viewtopic.php?p=8380

and the current record holder is 32 by dukuso, also in that thread.

(I know Red Ed pointed this out earlier, just repeating for clarity)

[Ocean]

Just to be clear.

The question goes back to 3 September 2005, and this post by giant:

http://forum.enjoysudoku.com/viewtopic.php?p=8380

and the current record holder is 32 by dukuso, also in that thread.

(I know Red Ed pointed this out earlier, just repeating for clarity)

Here is another minimal 32. It's a difficult one.
#

Code: Select all

*-----------*
 |.2.|.48|..3|
 |468|3.1|.7.|
 |3..|7..|...|
 |---+---+---|
 |.84|1..|6..|
 |216|8..|..9|
 |...|...|...|
 |---+---+---|
 |83.|6..|59.|
 |.7.|...|...|
 |6.9|28.|7..|
 *-----------*

#
And here is a minimal 33. Not too easy to solve.
#

Code: Select all

 *-----------*
 |.2.|.48|.6.|
 |468|3.1|.7.|
 |...|7..|...|
 |---+---+---|
 |914|8..|...|
 |286|1..|3.9|
 |...|...|...|
 |---+---+---|
 |83.|6..|59.|
 |.7.|...|...|
 |6.9|28.|73.|
 *-----------*

#

[coloin]

The 32 puzzle has this 18 ! - and it has 9 common clues !

Code: Select all

+---+---+---+
|.2.|...|...|
|...|...|..5|
|39.|7.6|8..|
+---+---+---+
|...|...|6..|
|.1.|.5.|..9|
|7..|...|...|
+---+---+---+
|8..|...|...|
|...|91.|...|
|6..|...|73.|
+---+---+---+

perhaps goes to show that the a low number of clues is circumstancial - as is the occurrance of a high number of clues.

Are high numbers just as difficult to generate randomly ?

counts of clues in randomly generated minimal
sudokus over sf :

average:24.104503 , 1000000 samples
19 3
20 229
21 6277
22 61494
23 227035
24 352839
25 248868
26 86121
27 15453
28 1589
29 89
30 3

So how suboptimally can we pick clues to hit a clue in every unavoidable set ?

Maybe there will be some advance on 33 !

How about looking in http://forum.enjoysudoku.com/viewtopic.php?t=2524&start=0

Code: Select all

+---+---+---+
|145|726|983|
|837|495|261|
|926|381|574|
+---+---+---+
|293|874|156|
|581|269|347|
|674|153|892|
+---+---+---+
|318|547|629|
|459|632|718|
|762|918|435|
+---+---+---+

This has plenty of unavoidables - MCN 16

[Red Ed]

Had a quick think about this ...

Guenter found an independent set of 32 clues which had the bonus property of being uniquely solvable. Can we do better if we drop the uniquely-solvable aspect, i.e. just aim for independence ...?

... and the answer is that it is counter-productive to drop the unique-solution property: the largest number of independent clues can only exist in a uniquely-solvable grid.

If c_1,...,c_n are independent clues then deleting any c_i causes the number of solutions to increase. So each c_i is in some minimal unavoidable u_i that does not contain any of the other clues. Now suppose c_1,...,c_n does not uniquely define a solution grid: then there's a minimal unavoidable U not touched by any c_i; so we can add any C in U to our clue set whilst maintaining independence --- thus, the original c_1,...,c_n weren't maximal.

So this really is just the maximal minimal single-solution sudoku problem after all.

[Ocean]

The 32 puzzle has this 18 ! - and it has 9 common clues !

- Thanks!

perhaps goes to show that the a low number of clues is circumstancial - as is the occurrance of a high number of clues.
Are high numbers just as difficult to generate randomly ?
...
So how suboptimally can we pick clues to hit a clue in every unavoidable set ?
Maybe there will be some advance on 33 !

Good points!

I found some minimal sudokus with 33 clues earlier today (posted in another thread).

All of them are equally hard to solve! I tested them in 'Simple Sudoku', and they all reach a stage where 'No hint is available'. This happens when there are 34 remaining cells, and the crucial point seems to be identical for all of them.
#

...So this really is just the maximal minimal single-solution sudoku problem after all.

Agrees. And nice explanation!

[sg]

I found some minimal sudokus with 33 clues earlier today (posted in another thread).

Code: Select all

020048060468301005000700000914800000286100309000000000800600590070000000640285730
...


Can you point me towards an explanation of how to read strings such as the one above?

What sort of algorithm are you using:
- Deleting from a completed grid, or putting clues into an empty puzzle?
- Randomized or deterministic enumeration?
- If randomized, then is it known whether the algorithm is "unbiased" in the following technical sense: that if you ran the algorithm for infinitely long, each good Su Doku would appear as often as any other (modulo Poisson fluctuations)? (Such an algorithm has no bias towards producing one or more favourites)

Since irreducible puzzles are one of the basic elements in the maths of Su Doku, it might be useful to keep track of how many different irreducible puzzles one finds of each size between the maximum and minimum (if using a randomized algorithm, then such a count is useful only if one has an unbiased algorithm or the bias is so accurately characterized that one can correct for it exactly).

Another interesting thing is to figure out the "density" of irreducible Su Dokus inside the set of good Su Dokus. Are there any known results on this, enumerations or randomized counts?

[coloin]

Code: Select all

020048060468301005000700000914800000286100309000000000800600590070000000640285730

020048060
468301005
000700000
914800000
286100309
000000000
800600590
070000000
640285730

+---+---+---+
|.2.|.48|.6.|
|468|3.1|..5|
|...|7..|...|
+---+---+---+
|914|8..|...|
|286|1..|3.9|
|...|...|...|
+---+---+---+
|8..|6..|59.|
|.7.|...|...|
|64.|285|73.|
+---+---+---+


For info
Dukuso's programs to produce random minimal sudokus ARE biased.
suexsf.exe see http://magictour.free.fr/sudoku.htm

suex9- http://magictour.free.fr/suex9-.exe is a program to convert a puzzle [in .txt format as initially above] to a minimal form.

In a very small sample of 7 random grids
http://forum.enjoysudoku.com/viewtopic.php?t=2524&postdays=0&postorder=asc&start=15
1 was reducable to 18
6 were reducable to 19
a very small proportion of all grids are reducable to 17 and 20 !

[tarek]

Just some quick questions guys:

when u reduce a non minimal puzzle to the MINIMAL form:

1. do you take out givens which do not contribute to a unique solution ?

If this is the case then you may have several minimal puzzles, some being larger than others depending on the combination of givens removed.

2. do you build a minimal puzzle from the solution of the puzzle (again several minimal puzzles).

In this case an apparant minimal puzzle, will not be minimal if we generate a smaller valid puzzle from the solution.

Tarek

[Ocean]

Can you point me towards an explanation of how to read strings such as the one above?

What sort of algorithm are you using:
- Deleting from a completed grid, or putting clues into an empty puzzle?
- Randomized or deterministic enumeration?
- If randomized, then is it known whether the algorithm is "unbiased" in the following technical sense: that if you ran the algorithm for infinitely long, each good Su Doku would appear as often as any other (modulo Poisson fluctuations)? (Such an algorithm has no bias towards producing one or more favourites)

Thanks to coloin for explaining the various display formats. The 'line' format is more compact, and suitable when listing several puzzles. The 'box' format is more illustrative, and easier to evaluate (or solve) by humans.


About the algorithms I use:
- Modifying an input grid (which may be empty, complete or partly completed).
- Both deterministic and random strategy, whatever gives a result.
- When looking for minimal sudokus, the search is strongly biased. Some sudokus occur far more often than others. Apart from the minimizing process, the search is not biased, as far as I can see - but I have no proof for it or supporting statistics.

[sg]

Thanks, Coloin and Ocean.

If this is the case then you may have several minimal puzzles, some being larger than others depending on the combination of givens removed.

Wonderful question, Tarek. This cuts to the heart of the open question of counting the number of Su Doku puzzles, rather than Su Doku solutions.

Yes, starting from a solution (filled grid) there are non-equivalent ways of reducing it. This is a backward "garden of forking paths" or a decision tree of what to remove. The root node is the filled grid, the leaf nodes are irreducible Su Doku puzzles. There are many questions which one can ask about these 5,472,730,538 trees: minimum and maximum Su Dokus are only two of these.

[sg]

There are many questions which one can ask about these 5,472,730,538 trees: minimum and maximum Su Dokus are only two of these.

The present record maximum of 33 probably comes from a very small number (1?) of these trees (one per essentially different grid). Is that right?

[gsf]

In this case an apparant minimal puzzle, will not be minimal if we generate a smaller valid puzzle from the solution.

there's a difference between "minimal" and { "minimum" "maximum" }
"minimal" is a local property, "minimum" "maximum" are absolutes

for the selected set of clues this puzzle is minimal
vs
this minimal puzzle has the minimum (maximum) number of clues
out of all minimal puzzles within this solution grid

[Ocean]

The present record maximum of 33 probably comes from a very small number (1?) of these trees (one per essentially different grid). Is that right?

The sixteen minimal 33s I found yesterday belong to two different solution grids (these grids are 'almost identical' but not 'equivalent', I think).

Input to the process was >1 million random generated sudokus/grids. Further an accumulation (and enrichment) of 'high' minimals. The outcome is rather random. Repeating the process would probably result in new different sets of 33s, and repeating it thousands or millions of times would probably find 34s, 35s, etc, until the ultimate 'maximum minimal' is reached.

[tarek]

this minimal puzzle has the minimum (maximum) number of clues out of all minimal puzzles within this solution grid

Thanx gsf, that clears it. Up until now, I thought that Minimum would mean the unique puzzle resulting from removing the largest possible combinations of givens.

To make sure that I understood it..... if you are discussing the "maximum minimum minimal sudokus", it sounds pretty hard to find that.

But if you are talking about "Maximum minimal" then it should be easier.

Tarek