The New Sudoku Players' Forum

[Pupp]

I see a lengthy thread about the "smallest valid pattern".

What's the difference between that and a minimal clue puzzle?

[Mathimagics]

Puzzles consist of clues, aka givens. Patterns are just templates that indicate the positions of those clues.

For example ..2..4..1 might be the first row of a puzzle, in which case the corresponding pattern would begin with ..X..X..X

A pattern is valid if there exists some choice of clue values that can replace the X's and be a valid puzzle (that is, has 1 solution).

[Pupp]

Thanks

[dxSudoku]

Puzzles consist of clues, aka givens. Patterns are just templates that indicate the positions of those clues.

For example ..2..4..1 might be the first row of a puzzle, in which case the corresponding pattern would begin with ..X..X..X

A pattern is valid if there exists some choice of clue values that can replace the X's and be a valid puzzle (that is, has 1 solution).

I get the part about clues and the number givens. I think I read somewhere the minimum number of givens and still have a solvable puzzle is 17. For the pattern as you described I heard it called a "mask". The number of X's in the pattern would be between 1 and 81-17 or 64. I'm confused with what minimum means with regards to pattern the way you described. A pattern of 64 X's would have the greatest number of X's. So what does minimum pattern mean?

[Mathimagics]

I think I read somewhere the minimum number of givens and still have a solvable puzzle is 17.

A puzzle is solvable if it has at least 1 solution. So an empty grid (0 givens) is solvable.

17 is the minimum number of givens required for a valid puzzle. Again, a valid puzzle has exactly 1 solution.

A 17-clue puzzle has 17 "X"'s in its pattern, not 64.

So what does minimum pattern mean?

No idea, it doesn't really mean anything.

The smallest valid pattern thread is actually about finding the least possible valid pattern in minlex form. Look at the first post in that thread for clear examples of what patterns are, and how they are used

[Pupp]

What is Minlex?

[Mathimagics]

Minlex is an abbreviation of "minimum lexicographical".

For any Sudoku grid, or puzzle, there are 3,359,232 possible ways to permute the grid to obtain an equivalent grid/puzzle. These are called VPT's, or "validity-preserving transformations". See the MoS Wiki page for a list of these.

For a given grid/puzzle, if we generate all of the transformations, normalise them (which means relabelling so that row 1 = 123456789), then list these in one-line format, and then sort this list, then the first entry in the sorted list is the minlex form of the original grid/puzzle.

[JPF]

For a given grid/puzzle, if we generate all of the transformations, normalise them (which means relabelling so that row 1 = 123456789), then list these in one-line format, and then sort this list, then the first entry in the sorted list is the minlex form of the original grid/puzzle.

As it is written above, the normalisation works only for a (solution) grid.

Normalization:
the grid/puzzle can be written: x1...x81 (row by row)
relabel the xi non equal to zero such that (after relabelling) x1...x81 is minimal.

Example:

Code: Select all

puzzle     : ...7......7...5.3.....9.8..1.4...2......6...4.25....1...248.....6.9...7.8....1...
Norm puzzle: ...1......1...2.3.....4.5..6.7...8......9...7.82....6...875.....9.4...1.5....6...

grid       : 946738125278615439513294867194357286387162954625849713752486391461923578839571642
Norm grid  : 123456789846379251975812634712594863564738192389621475498263517237185946651947328


To get the minlex of grid/puzzle apply all the VPTs as mentionned above.

I would also add "then sort this list in increasing order".

JPF