Patterns vs clues

Everything about Sudoku that doesn't fit in one of the other sections

Patterns vs clues

Postby Pupp » Sun Jun 27, 2021 3:36 am

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

What's the difference between that and a minimal clue puzzle?
Pupp
 
Posts: 246
Joined: 18 October 2019

Re: Patterns vs clues

Postby Mathimagics » Sun Jun 27, 2021 4:57 am

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).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Patterns vs clues

Postby Pupp » Sun Jun 27, 2021 11:32 pm

Thanks
Pupp
 
Posts: 246
Joined: 18 October 2019

Re: Patterns vs clues

Postby dxSudoku » Sat Jul 17, 2021 2:00 am

Mathimagics wrote: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?
dxSudoku
 
Posts: 43
Joined: 06 April 2020

Re: Patterns vs clues

Postby Mathimagics » Sat Jul 17, 2021 5:18 am

dxSudoku wrote: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.

dxSudoku wrote: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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Patterns vs clues

Postby Pupp » Thu Aug 26, 2021 2:42 pm

What is Minlex?
Pupp
 
Posts: 246
Joined: 18 October 2019

Re: Patterns vs clues

Postby Mathimagics » Thu Aug 26, 2021 3:41 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1870
Joined: 27 May 2015
Location: Canberra

Re: Patterns vs clues

Postby JPF » Thu Aug 26, 2021 4:57 pm

Mathimagics wrote: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
JPF
2017 Supporter
 
Posts: 5897
Joined: 06 December 2005
Location: Paris, France


Return to General