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 :

- 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

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|...|

|---+---+---|

|...|...|...|

|...|...|...|

|...|...|...|

*-----------*

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|

*-----------*

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.|...|

*-----------*

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