The New Sudoku Players' Forum

[JPF]

Purpose of the thread:

Everything about minimal puzzles and extension of this concept to puzzles with multiple solutions, patterns, etc...

Properties of some patterns.

Special types of minimality for symmetric puzzles.

I keep this first post to give the main usual definitions.

________________________________________________________________________

General definitions :

• grid : a full Sudoku grid (9x9) with a digit in each cell, 9 different digits in each unit.
  
• subpuzzle : a grid in which some digits have been removed.
  
• solution of a subpuzzle : any (full) grid which contains the subpuzzle.
  a subpuzzle may have several solutions.
  
• valid Puzzle : a subpuzzle with a unique solution.
  Depending on the context, puzzle can refer to valid puzzle and puzzle with multiple solutions to subpuzzle.
  

Minimal puzzle

A valid puzzle is minimal when removing any of its clues results in a puzzle that has more than one solution.

Example :

Puzzle P1 : #28 clues, minimal

Code: Select all

 *-----------*
 |..1|.2.|3..|
 |.3.|1.4|.5.|
 |6.4|...|2.1|
 |---+---+---|
 |.1.|...|.7.|
 |8..|...|..9|
 |.2.|...|.6.|
 |---+---+---|
 |3.6|...|7.5|
 |.4.|3.6|.8.|
 |..8|.7.|4..|
 *-----------*

By removing r1c3=1 the puzzle has 5 solutions.
If we do this operation successively for each clue (r1c3, r1c5,...etc) the number of solutions of each resulting puzzle is :
5,6,11,3,10,4,7,13,5,12,14,48,4,14,40,193,26,3,48,24,31,47,3,32,19,67,73,7
So, the puzzle P is minimal.

An other (equivalent) way to define minimality : if one clue can be removed without changing the number of solutions, the puzzle is not minimal.

Using almost the same example, the following puzzle is not minimal :

Code: Select all

 *-----------*
 |..1|.2.|3..|
 |.3.|1.4|.5.|
 |6.4|...|2.1|
 |---+---+---|
 |.1.|...|.7.|
 |8..|.1.|..9|
 |.2.|...|.6.|
 |---+---+---|
 |3.6|...|7.5|
 |.4.|3.6|.8.|
 |..8|.7.|4..|
 *-----------*

This is a valid puzzle, but r5c5=1 can be removed and the resulting puzzle is still valid.

Note that there are many ways to remove clues.
For example, one can remove the 4 cells r1c5,r2c4,r4c2,r7c1 and get this valid puzzle :

Code: Select all

  *-----------*
 |..1|...|3..|
 |.3.|..4|.5.|
 |6.4|...|2.1|
 |---+---+---|
 |...|...|.7.|
 |8..|.1.|..9|
 |.2.|...|.6.|
 |---+---+---|
 |..6|...|7.5|
 |.4.|3.6|.8.|
 |..8|.7.|4..|
 *-----------*

Every valid puzzle contains at least one minimal puzzle :

a) Let P be a puzzle, n(P) the number of clues, N(P) the number of solutions.

If P and Q are two puzzles such that Q is included in P, then N(P)<=N(Q)

The reason is that every (grid)solution of the puzzle P contains the n(Q) clues of Q and therefore is a solution of Q.
The set of solutions of P is included in the set of solutions of Q.
As a consequence : N(P)<=N(Q)

b) Now, let P be a valid puzzle, N(P)=1, with at least one clue (!)

Let's consider this recursive process :
1. If P minimal : end of the process
2. remove one clue c from P => new P
3. go to 1

This process will stop since the serie of the number of solutions n(P) of the successive puzzles is non-decreasing and since one clue-puzzle has more than one solution...


Number of clues of minimal puzzles

The question of the minimum number of clues and the maximum number of clues of a minimal puzzle is very tough and is studied in specific threads :

• minimum number of clues :
  http://forum.enjoysudoku.com/viewtopic.php?t=2312
  http://forum.enjoysudoku.com/viewtopic.php?t=605
  
• maximum number of clues :
  http://forum.enjoysudoku.com/viewtopic.php?t=5469

As of today, here are the known values :

• minimum : 17
• maximum : 39

17 is also the minimum number of clues for a valid puzzle, obviously minimal.


To be continued...


Non minimal patterns

A pattern is a set of cells (without digit) ; an "x" is used to mark the cell in the grid.
A puzzle contains a pattern if all the cells of the pattern are included in the cells of the puzzle.

For instance, Mauricio's initial puzzle contains this pattern

Code: Select all

*-----------*
|..x|.x.|x..|
|.x.|...|.x.|
|x..|...|..x|
|---+---+---|
|...|...|...|
|x..|...|..x|
|...|...|...|
|---+---+---|
|x..|...|..x|
|.x.|...|.x.|
|..x|.x.|x..|
*-----------*

A pattern is called non minimal if there is no minimal valid puzzle containing this pattern.

Example :
Patterns with a full unit (box, row, column)
This pattern is non minimal :

Code: Select all

*-----------*
|...|...|...|
|...|...|...|
|...|...|...|
|---+---+---|
|...|xxx|...|
|...|xxx|...|
|...|xxx|...|
|---+---+---|
|...|...|...|
|...|...|...|
|...|...|...|
*-----------*

Proof : in every valid puzzle containing the full box B5, we can remove one clue of B5 and still have a valid puzzle.

every pattern containing a non minimal pattern is a non minimal pattern.


Minimal subpuzzles

The concept of minimality can be extended to puzzles with multiple solutions (subpuzzles).
A subpuzzle is minimal when removing any of its clues results in a subpuzzle that has a greater number of solutions.

Example :

Code: Select all

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

This puzzle has 2 solutions.
By removing r1c1=3 the subpuzzle will have 144 solutions...
If we do this operation for each clue successively (r1c1,r1c7,...) the number of solutions of each resulting subpuzzle is : 144,1000*,124,165,34,299,810,371,165,405,299,270,20,1000*,371,92,405,498,20,172.
1000* means more than 1000.

The subpuzzle is therefore minimal.

Here an example of a non minimal subpuzzle :

Code: Select all

 *-----------*
 |761|234|589|
 |..4|...|6..|
 |..3|...|7..|
 |---+---+---|
 |.8.|...|.9.|
 |6..|...|..7|
 |.2.|...|.1.|
 |---+---+---|
 |..2|...|3..|
 |...|5.9|...|
 |...|.8.|...|
 *-----------*

This subpuzzle has 22 solutions.
Remove 4 clues (r1c1289) and you still get a subpuzzle with 22 solutions :

Code: Select all

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

This last one is actually minimal.


Note that a subpuzzle containing a non minimal pattern is not minimal ????.


Every subpuzzle contains at least one minimal subpuzzle :
The proof and the algorithm to find it are the same as for a valid puzzle.


Closure of a subpuzzle

By definition, a subpuzzle P is a puzzle with multiple solutions N(P)>=1

Let S1,S2,...,Sp be the grid-solutions of P.
This set of full grids has some common cells which I call closure of P and note C[P].
Note that C[P] is the intersection of the sets S1,S2,...,Sp ;
C[P]= S1 ∩ S2 ∩ ... ∩ Sp.


Property of the closure C[P]:

• C[P] contains P
  as P ⊆ Sk for every k, then P ⊆ S1 ∩ S2 ∩ ... ∩ Sp
• C[P] is a full grid (81 digits) iff P is a valid puzzle
  

Maximal subpuzzle

a subpuzzle is called maximal if it is equal to its closure P=C[P]

Note that a valid puzzle is maximal iff it's a full grid.

Here is an example of a subpuzzle :

Code: Select all

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

and its closure :

Code: Select all

 *-----------*
 |761|234|589|
 |8.4|...|623|
 |2.3|...|741|
 |---+---+---|
 |18.|..3|.9.|
 |64.|...|.37|
 |32.|...|.1.|
 |---+---+---|
 |972|...|358|
 |438|579|162|
 |516|382|974|
 *-----------*


To be continued...

JPF

[wintder]

Is there an available pattern generator that can be set to output only minimal puzzles?

If it is gsf's, what would be the command line, or bat file text?

Thanks

[Mauricio]

The following patterns are not minimal (in the sense of JPF) (thanks to ravel for pointing out the second pattern, that contains my previous atempts)

Code: Select all

+-------+-------+-------+
| . x x | x x x | x x x |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| x . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+


Code: Select all

+-------+-------+-------+
| . . . | x x x | x x x |
| x . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+


Proof for first pattern (the proof for the second pattern is similar):
Let's assume the pattern minimal and be row 1 like this:

Code: Select all

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


If r4c1=a (a=1,2,3,4,5,6,7,8), then we can remove the clue a from row 1.

Analogously for the second pattern.

For this reason, any minimal puzzle having 8 clues in a row cannot have any clue in the column empty in that row, and neither can have more clues in the box that has the missing clue.

As a corolary to the previous statement (and using the next post), a minimal puzzle cannot have more than 1 row with 8 clues.

A minimal puzzle can have 1 row with 8 clues and 1 column with 8 clues, though:

Code: Select all

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


[Mauricio]

If a minimal puzzle contains the following pattern:

Code: Select all

+-------+-------+-------+
| . x x | x x x | x x x |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+


then the value at r1c1 cannot be the value of any given clue.
Proof: For simplicity, assume the puzzle has the following clues:

Code: Select all

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


If the value 9 is a given clue in column n (n=2,3,4,5,6,7,8,9), then the clue at r1cn can be removed.

[JPF]

Let's assume the pattern minimal and be row 1 like this:

Code: Select all

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


If r2c1=a (a=1,2,3,4,5,6,7,8), then we can remove the clue a from row 1

Nice statement.
you probably mean (a=3,4,5,6,7,8) ?
a=1,2,9 creates a non valid puzzle.

then the value at r1c1 cannot be the value of any given starting clue.

What do you call a starting clue ?

JPF

[Mauricio]

What do you call a starting clue ?

I changed it to the more standard "given clue".

[gsf]

Is there an available pattern generator that can be set to output only minimal puzzles?

what does a pattern generator do?

[Mauricio]

The following pattern is not minimal:

Code: Select all

 . . . | . . . | . . .
 . . . | . x . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | x . x | . . .
 . . . | x . x | . . .
 . . . | x . x | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .

Proof: Withoute loss of generality let's suppose box 5 is arranged this way

Code: Select all

 . . . | . . . | . . .
 . . . | . x . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | 1 . 2 | . . .
 . . . | 3 . 4 | . . .
 . . . | 5 . 6 | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .

Then r2c5=1,2,3,4,5,6. If r2c5=a, then the value a in box 5 can be removed.

[ravel]

... in fact it is the following pattern that is not minimal:

Code: Select all

 . . . | . . . | . . .
 . . . | . x . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | x . x | . . .
 . . . | x . x | . . .
 . . . | x . x | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .

.

Yes, and this one:

Code: Select all

 x x x | x x x | . . .
 . . . | . . . | . x .
 . . . | . . . | . . .
-----------------------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-----------------------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .


[wintder]

Is there an available pattern generator that can be set to output only minimal puzzles?

what does a pattern generator do?

What I meant was a sudoku puzzle generator that can be set to output puzzles based on a user specified pattern of clue placements.


Edited to add: Thank you gsf, just what I wanted, as you answered below.

[gsf]

Is there an available pattern generator that can be set to output only minimal puzzles?

what does a pattern generator do?

What I meant was a sudoku puzzle generator that can be set to output puzzles based on a user specified pattern of clue placements.

ok, that's the -gt option in my solver

Code: Select all

sudoku -gt template.txt

place the template grid in template.txt
add -v to trace generator progress
add -e minimal==1 to filter out minimal puzzles
--man lists the template details in the -g option description

the algorithm generates a solution grid and projects it onto the template and checks for unique solution
if that fails it permutes the grid N (default 100000, settable by -gtN) times and rechecks
if that fails it starts over with a new grid
the process would do better if it used unavoidable sets

[m_b_metcalf]

the algorithm generates a solution grid and projects it onto the template and checks for unique solution
if that fails it permutes the grid N (default 100000, settable by -gtN) times and rechecks
if that fails it starts over with a new grid
the process would do better if it used unavoidable sets

In a distant place, I posted:

1) generate a grid, overlay the template, check that the clues yield only one solution.

2) from the template generate a set of sudoku-compatible values for the clues; check that the clues yield one and only one solution.

In my experience, method 2 has a higher yield than method 1 [edit: I don't know why].

You can, of course, add various refinements, such as demanding in method 2 that all values in a house are distinct.

I still don't kmow why.

Regards,

Mike Metcalf

[coloin]

Excellent thread.

Can I for completeness mention that you cant have more than 6 of one clue value.

If you have 7 clues you cant avoid 3 horizontal and vertical shutes with clues. Therefore the clue in the intersecting box [box 1] is superfluous.

Code: Select all

+---+---+---+
|1..|...|...|
|...|1..|...|
|...|...|1..|
+---+---+---+
|.1.|...|...|
|...|.1.|...|
|...|...|.1.|
+---+---+---+
|..1|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  r1c1 may be removed

This extends to you cant have 5 similar clue values in an intersecting box [B1B2B3B4B7 in this case]

C

[gsf]

the algorithm generates a solution grid and projects it onto the template and checks for unique solution
if that fails it permutes the grid N (default 100000, settable by -gtN) times and rechecks
if that fails it starts over with a new grid
the process would do better if it used unavoidable sets

In a distant place, I posted:

1) generate a grid, overlay the template, check that the clues yield only one solution.

2) from the template generate a set of sudoku-compatible values for the clues; check that the clues yield one and only one solution.

In my experience, method 2 has a higher yield than method 1 [edit: I don't know why].

You can, of course, add various refinements, such as demanding in method 2 that all values in a house are distinct.

I still don't kmow why.

my guess is that (1) would take more time per trial and (2) less
so in the same time period you would get more trials with (2) and more chance of getting lucky

I amortized the expense of (1) by checking permutations too
generating permutations of a solution grid is quicker than generating a new solution grid

[gsf]

Can I for completeness mention that you cant have more than 6 of one clue value.

aha
let x(v) be the number of extra clues for each value 1<=v<=9
does that mean that there are at least product x(v) for x(v)!=0 (possibly equivalent) minimal puzzles?
e.g., if all clues are represented 6 times except 1/7-times, 2/8-times, 3/9-times,
does that mean there are at least 1*2*3=6 minimal puzzles?