Minimal Puzzles

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

Minimal Puzzles

Postby JPF » Sat Sep 29, 2007 10:39 pm

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 :
Mauricio wrote: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 :
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
Last edited by JPF on Thu Oct 04, 2007 3:06 pm, edited 4 times in total.
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby wintder » Sat Sep 29, 2007 10:44 pm

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
wintder
 
Posts: 297
Joined: 24 April 2007

Postby Mauricio » Sat Sep 29, 2007 11:10 pm

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 |
| . . . | . . . | . . . |
+-------+-------+-------+
Last edited by Mauricio on Mon Oct 01, 2007 9:47 am, edited 9 times in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Mauricio » Sat Sep 29, 2007 11:16 pm

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.
Last edited by Mauricio on Sun Sep 30, 2007 7:12 pm, edited 2 times in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby JPF » Sun Sep 30, 2007 10:38 pm

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

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

What do you call a starting clue ?

JPF
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby Mauricio » Sun Sep 30, 2007 11:13 pm

JPF wrote:What do you call a starting clue ?

I changed it to the more standard "given clue".
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby gsf » Sun Sep 30, 2007 11:52 pm

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

what does a pattern generator do?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mauricio » Sun Sep 30, 2007 11:54 pm

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.
Last edited by Mauricio on Tue Oct 02, 2007 12:10 am, edited 3 times in total.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby ravel » Mon Oct 01, 2007 8:37 am

Mauricio wrote:... 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 .
 . . . | . . . | . . .
-----------------------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-----------------------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
ravel
 
Posts: 998
Joined: 21 February 2006

Postby wintder » Mon Oct 01, 2007 8:55 am

gsf wrote:
wintder wrote: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.
Last edited by wintder on Mon Oct 01, 2007 5:23 pm, edited 1 time in total.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby gsf » Mon Oct 01, 2007 2:00 pm

wintder wrote:
gsf wrote:
wintder wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby m_b_metcalf » Mon Oct 01, 2007 7:08 pm

gsf wrote: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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 9209
Joined: 15 May 2006
Location: Berlin

Postby coloin » Mon Oct 01, 2007 8:02 pm

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
coloin
 
Posts: 1733
Joined: 05 May 2005

Postby gsf » Mon Oct 01, 2007 9:38 pm

m_b_metcalf wrote:
gsf wrote: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
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Mon Oct 01, 2007 9:46 pm

coloin wrote: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?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next

Return to General