The New Sudoku Players' Forum

[gsf]

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.

its what you thought, so maybe I muddied the waters ...
procedurally (not necessarily efficient)
start with a solution grid (all clues, no holes)
generate all possible minimal puzzles from the grid
keep track of the minimal puzzles with the least and most clues
after all have been generated you will end up with
one or more minimal puzzles with the minimum number of clues and
one or more minimal puzzles with the maximum number of clues
for the specific solution grid

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

the 17 (or 16) search is for the "minimum minimal" over all solution grids
and the current discussion is on the "maximum minimal"

[sg]

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.

... for a given grid. The usual problem with a Monte Carlo program is that while it may be very useful on the average case, it is a costly tool to find the extreme cases.

Perhaps a small number of checks with a larger number of starting grids is more efficient for something like a "maximum olympics". I notice from the previous discussion thread of minimum ISD (irreducible Su Doku) that there was quite a bit of variation from one grid to another.

For actually finding the highest (or lowest) branch in the forest of 5,472,730,538 trees/grids one would really have to think of something more efficient. But the Monte Carlo gives an indication of whether the branches grow higher in some part of the woods.

BTW: I started talking of trees earlier while discussing the pruning of grids into irreducible puzzles, but one should not take this literally. We are dealing with digraphs (nodes are states of the puzzle, and two nodes are conected by an arrow if it is possible to go from one to another by erasing the content of a cell; the direction of the arrow goes from more filled to less filled puzzle, say), and two different nodes may lead to a common node by elimination of different boxes. All this is just fancy language for something that you guys know very well, as I can see from your earlier discussions about minimum ISD.

[Ocean]

The usual problem with a Monte Carlo program is that while it may be very useful on the average case, it is a costly tool to find the extreme cases.

True. A pure Monte Carlo process might take years. The algorithms I experiment with are not too effective either, but sometimes they produce results. Finding optimal strategies is a bit difficult. It's also difficult to compare algorithms, as each grid has different characteristics.

Numerical results are hard to interprete. I found that small random modifications of the same puzzle is a terrible waist - or that's what I call it when 95% of the generated puzzles are already found. At the same time such random modifications are also effective in the search for low minimals, because of the strong biasing - the 'low' ones are found over and over again. In the search for high minimals, a pure random process seems to be less effective, and there might be more to gain on complete search through prospective areas. These 'prospective areas' have to be small and carefully selected - as there are zzzillions of valid non-minimal puzzles in the 30-40s.

[tinfoil]

I'm not sure who this post should be directed to, but I think that the 'maximum number of initial clues where all are required to be given to define a unique grid' deserves to be described on the 'Mathematics of Soduku' Wiki page, as it is NOT a trivial exercise.

Obviuosly, the attribution should be THIS thread, and the folks here who made the discoveries (i.e. Ocean et al)

[Red Ed]

I'm not sure who this post should be directed to, but I think that the 'maximum number of initial clues where all are required to be given to define a unique grid' deserves to be described on the 'Mathematics of Soduku' Wiki page, as it is NOT a trivial exercise.

It was my Wiki article originally and I do try to keep it updated from time to time (as do others). I'll wait to see how much more attention this topic gets before considering adding anything to Wikipedia. Don't let my reserve hold you back from contributing, though.

[JPF]

deleted.

[Ocean]

I have one question about 'equivalence'. Would you regard these two sudokus (minimal 33s) as different or equivalent? They have different solution grids. Their solution grids differ only by an 'unavoidable set' of size four. The two sudokus are identical except for the clues belonging to this specific 'unavoidable set', and all four members of the set are clues. This makes the 'empty' part of the two sudokus identical, and solution strategies and other properties are also identical.

Code: Select all

# Two minimal 33s differing by four clues:

 *-----------*
 |.2.|.48|.6.|
 |468|3.1|..5|
 |...|7..|...|
 |---+---+---|
 |914|8..|6..|
 |286|1..|..9|
 |...|...|...|
 |---+---+---|
 |83.|6..|59.|
 |.7.|...|...|
 |6..|285|73.|
 *-----------*

 *-----------*
 |.2.|.48|.6.|
 |468|3.1|..5|
 |...|7..|...|
 |---+---+---|
 |984|1..|6..|
 |216|8..|..9|
 |...|...|...|
 |---+---+---|
 |83.|6..|59.|
 |.7.|...|...|
 |6..|285|73.|
 *-----------*

#

#
Similar pairs:

Pair #2:
020048060468301005000700000914800000286100309000000000800600590070000000649280730
020048060468301005000700000984100000216800309000000000800600590070000000649280730
Pair #3:
020048060468301005000700000914800600286100009000000000800600590070000000640285730
020048060468301005000700000984100600216800009000000000800600590070000000640285730
Pair #4:
020048060468301005000700000914800600286100009000000000800600590070000000649280730
020048060468301005000700000984100600216800009000000000800600590070000000649280730
#

[gsf]

I have one question about 'equivalence'. Would you regard these two sudokus (minimal 33s) as different or equivalent?

different
none of the equivalence transformations, listed at http://www.csse.uwa.edu.au/~gordon/sudokumin.php,
alone or combined, can transform one puzzle to the other

[sg]

Does anyone have a list of "essentially different" grids?

I expect most of these grids will not show any symmetry, but a few will probably have some degree of symmetry. If not, one would expect that (Number of Sudokus)/(Number of essentially different Sudokus) = size of the group. Since this is not true, one expects some grids with symmetry.

It is quite likely that such symmetries would reduce the maximum number of clues in an irreducible Sudoku.

Since I don't have a good implementation of solvers, I'm not likely to finish this in a hurry, so if any one else wants to have a go at it, you're perfectly welcome.

[Red Ed]

The question of symmetries is covered pretty thoroughly here.

I don't have a list of "essentially different" grids, but I can generate grids that are essentially-invariant under any of the 28-or-so classes of cell perms that have such fixed points. For example, here's an essentially-invariant grid of the op that permutes rows and columns 1->4->8->2->5->9->3->6->7 (I picked this op as it's from the class, 23, with the smallest number of fixed grids).

Code: Select all

157|629|834
826|743|591
493|185|267
---+---+---
268|491|375
934|257|618
571|836|942
---+---+---
385|914|726
619|572|483
742|368|159

Perhaps someone could investigate your comment about maximal minimal sudokus on this, presumably somewhat special, grid. Or, if keen, on the whole list of 162 (for fixed B1) ... I can produce these easily if desired.

[sg]

I posted elsewhere some results of an enumeration in the 2X2 toy model, which you might find interesting since it has some relevance to this thread.

[kjellfp]

Does anyone have a list of "essentially different" grids?

I expect most of these grids will not show any symmetry, but a few will probably have some degree of symmetry. If not, one would expect that (Number of Sudokus)/(Number of essentially different Sudokus) = size of the group. Since this is not true, one expects some grids with symmetry.

You might have a look at this which I wrote some time ago. I don't think you want the complete list of all grids, it's too big. But when I did the counting in the link, I visited every equivalence class of grids exactly once.

I did develop a complete list of all grids with non-trivial symmetries, that was at least storable as files.

The number of grids is not the number of essentially different grids times the number of transformations, but it's very close - indicating that the vast majority of the grids has no non-trivial symmetry.