## Minimal Puzzles

Everything about Sudoku that doesn't fit in one of the other sections
gsf wrote: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?

Not sure if I perfectly understand your question, but if one digit is given 9 times, then that digit alone gives at east 6 minimal puzzles. So your correct number would be 1*2*6=12.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

RW wrote:
gsf wrote: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?

Not sure if I perfectly understand your question, but if one digit is given 9 times, then that digit alone gives at east 6 minimal puzzles. So your correct number would be 1*2*6=12.

well, re-reading my post I'm not quite sure now either
unavoidables and other interactions can complicate the count even when only one value is allowed to exeed 6 occurrences in a minimal puzzle
here's an example:
Code: Select all
`.6......84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # original minimal, 1 occurs 6 times.6....1.84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 1 : 1 superfluous 1 clue.6......84.1.6....7..1..5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 2 : 1 superfluous 1 clue.6......84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8.1.4.8.7.9 # 3 : 1 superfluous 1 clue`

and the minimal puzzles w.r.t. to the 3 superfluous puzzles above, along with clue occurrence counts:
Code: Select all
`.6......84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 1 611233343.6....1.84.1.6....7.....5...8.5.6.....5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 1 611233343.6....1.84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2........1.8...4.8.7.9 # 1 611233343.6......84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 2 611233343.6......84.1.6....7..1..5...8.5.6.....5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 2 611233343.6......84.1.6....7..1..5...8.5.6..1..5....9..1.9..3...7...2.1......1.8...4.8.7.9 # 2 611233343.6......84.1.6....7.....5...8.5.6..1..5.1..9....9..3...7...2.1......1.8.1.4.8.7.9 # 3 611233343.6......84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9 # 3 611233343`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

The following pattern is not minimal:
Code: Select all
`+-------+-------+-------+| . . . | x . x | . . . || . . . | x . x | . . . || . . . | x . x | . . . |+-------+-------+-------+| . . . | . . . | . . . || . . . | . . . | . . . || . . . | . . . | . . . |+-------+-------+-------+| . . . | x . x | . . . || . . . | x . x | . . . || . . . | x . x | . . . |+-------+-------+-------+`

Proof: Without loss of generality, let box 2 be like this:
Code: Select all
`+-------+-------+-------+| . . . | 1 . 2 | . . . || . . . | 3 . 4 | . . . || . . . | 5 . 6 | . . . |+-------+-------+-------+| . . . | . . . | . . . || . . . | . . . | . . . || . . . | . . . | . . . |+-------+-------+-------+| . . . | x . x | . . . || . . . | x . x | . . . || . . . | x . x | . . . |+-------+-------+-------+`
then some clue in box 8 marked with an x must be 7, that clue is reduntant.
Last edited by Mauricio on Tue Oct 02, 2007 3:50 am, edited 2 times in total.
Mauricio

Posts: 1174
Joined: 22 March 2006

gsf wrote:does that mean there are at least 1*2*3=6 minimal puzzles?

I think in your example this is the case......but you have included the original puzzle twice more.

its easier to think of ways to put in 3 holes than 6 clues 9*8*7 / 6 = 84 puzzles

possibly that gives ? at least 24 minimal 6-clue combinations ?

Code: Select all
`6*xxoxoxoxx3*xxxxxxooo3*xxoxxoxxo6*xxxxoxoxo6*xoxxxoxox`

......although these will always give a valid puzzle..... I suspect many of the puzzles will not be minimal.

Edit
non-minimal combinations
Code: Select all
`36*xxxxxoxoo`

C
coloin

Posts: 1857
Joined: 05 May 2005

coloin wrote:......although these will always give a valid puzzle..... I suspect many of the puzzles will not be minimal.

If you are talking about single digit templates, those will not always give a valid puzzle. Only the first one with holes only on the diagonal is certain to give a valid puzzle. Which means that if all 9 digits of a template is given, then there's at least 6 minimal puzzles. (Idea of how to find a puzzle with exactly 6: complete the templates of the 17s, then count the minimal puzzles. Start by doing this procedure to those with 4 given of the same digit.)

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

RW wrote:Only the first one with holes only on the diagonal is certain to give a valid puzzle.
You are right
Code: Select all
`xxoxoxoxx`

but the puzzle may not be minimal
the other combinations will not quarentee a unique puzzle........except that gsf's original puzzle has a
Code: Select all
`xooxxxoxx`
pattern for the "1" clues, but is minimal

Perhaps the best we can say about these 6-clue template patterns derived from a minimal puzzle with 6 of one clue value is.......

6 patterns always solve the puzzle
36 patterns never give a minimal puzzle
42 patterns have an indeterminate outcome, some of which solve and give a minimal puzzle - as in the 9 minimal puzzles I found in gsf's example using the method outlined by RW
Code: Select all
`.6......84.1.6....7.....5...8.5.6..1..5.1..9....9..3...7...2.1......1.8.1.4.8.7.9.6......84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2.1......1.8...4.8.7.9.6......84.1.6....7..1..5...8.5.6.....5.1..9..1.9..3...7...2.1......1.8...4.8.7.9.6......84.1.6....7..1..5...8.5.6..1..5....9..1.9..3...7...2.1......1.8...4.8.7.9.6....1.84...6....7..1..5...8.5.6.....5.1..9..1.9..3...7...2.1......1.8...4.8.7.9.6....1.84.1.6....7.....5...8.5.6.....5.1..9....9..3...7...2.1......1.8.1.4.8.7.9.6....1.84.1.6....7.....5...8.5.6.....5.1..9..1.9..3...7...2.1......1.8...4.8.7.9.6....1.84.1.6....7.....5...8.5.6..1..5.1..9....9..3...7...2........1.8.1.4.8.7.9.6....1.84.1.6....7.....5...8.5.6..1..5.1..9..1.9..3...7...2........1.8...4.8.7.9`

Perhaps a more simple [but trivial] assertion, in relation to this thread, is that 5 clues with this pattern wont give a minimal puzzle....
Code: Select all
`xxxxooxoo`

C
coloin

Posts: 1857
Joined: 05 May 2005

The following pattern is not minimal, but the only "proof" I have is that I searched exhaustively for all possible subpuzzles with that pattern, and none of them was minimal:
Code: Select all
`+-------+-------+-------+| . . . | x x x | . . . || . x x | . . . | x x . || . x x | . . . | x x . |+-------+-------+-------+| x . . | . . . | . . . || x . . | . . . | . . . || x . . | . . . | . . . |+-------+-------+-------+| . x x | . . . | . . . || . x x | . . . | . . . || . . . | . . . | . . . |+-------+-------+-------+`

For the same reason the following patterns are not minimal:
Code: Select all
`100111000011000110011000100100000000100000000100000000011000000011000000000000000010111000011000110011000100100000000100000000100000000011000000011000000000000000000111000111000110011000100100000000100000000100000000011000000011000000000000000000111000011000111011000100100000000100000000100000000011000000011000000000000000000111000011000110111000100100000000100000000100000000011000000011000000000000000000111000011000110011000101100000000100000000100000000011000000011000000000000000000111000011000110011000100100000000100000000100000000011000000011000000010000000`

Several of the above patterns gave me the idea that the following pattern is not minimal, and it is not minimal for the same reason (ie, I don't have a proof now, but I searched exhaustively and found none):
Code: Select all
`+-------+-------+-------+| . x . | . . . | . . . || . x x | . . . | . . . || . x x | . . . | . . . |+-------+-------+-------+| x . . | . . . | . . . || x . . | . . . | . . . || x . . | . . . | . . . |+-------+-------+-------+| . x x | . . . | . . . || . x x | . . . | . . . || . . . | . . . | . . . |+-------+-------+-------+`
Last edited by Mauricio on Wed Oct 03, 2007 4:37 am, edited 1 time in total.
Mauricio

Posts: 1174
Joined: 22 March 2006

Nice findings Mauricio

now the question is:

Are all these patterns "minimal" not minimal ? (i.e. they don't contain a not minimal pattern ?)

JPF

JPF
2017 Supporter

Posts: 3763
Joined: 06 December 2005
Location: Paris, France

JPF wrote:Are all these patterns "minimal" not minimal ? (i.e. they don't contain a not minimal pattern ?

I only know the answer for the first pattern:
Code: Select all
`+-------+-------+-------+| . . . | x x x | . . . || . x x | . . . | x x . || . x x | . . . | x x . |+-------+-------+-------+| x . . | . . . | . . . || x . . | . . . | . . . || x . . | . . . | . . . |+-------+-------+-------+| . x x | . . . | . . . || . x x | . . . | . . . || . . . | . . . | . . . |+-------+-------+-------+ `
ie, I found a minimal subpuzzle for every sub pattern of that pattern.
Mauricio

Posts: 1174
Joined: 22 March 2006

This pattern too is not minimal, I searched exhaustively and found 0 minimal subpuzzles:
Code: Select all
`+-------+-------+-------+| . . x | x x x | x . . || . x x | . . . | x x . || x x . | . . . | . x x |+-------+-------+-------+| x . . | . . . | . . . || x . . | . . . | . . . || x . . | . . . | . . . |+-------+-------+-------+| x x . | . . . | . . . || . x x | . . . | . . . || . . x | . . . | . . . |+-------+-------+-------+`

I have not checked which of its subpatterns are not minimal too, but I found this minimal subpuzzle:
Code: Select all
`+-------+-------+-------+| . . . | 1 2 3 | 4 . . || . 1 4 | . . . | 2 3 . || . 5 . | . . . | . 6 7 |+-------+-------+-------+| 2 . . | . . . | . . . || 5 . . | . . . | . . . || 6 . . | . . . | . . . |+-------+-------+-------+| 8 2 . | . . . | . . . || . 3 6 | . . . | . . . || . . 7 | . . . | . . . |+-------+-------+-------+`
Mauricio

Posts: 1174
Joined: 22 March 2006

In the challenging quest to find a minimal fully symmetric 36 clue puzzle, perhaps the best way to confirm possible valid minimal subpuzzle patterns would be to generate a minimal puzzle with this pattern [for example] plus a few clues in B6B8B9

Code: Select all
`+-------+-------+-------+ | . x x | x . x | x x . | | x . . | . x . | . . x | | x . . | . x . | . . x | +-------+-------+-------+ | x . . | . x . | ? ? ? | | . x x | x . x | ? ? ? | | x . . | . x . | ? ? ? | +-------+-------+-------+ | x . . | ? ? ? | ? ? ? | | x . . | ? ? ? | ? ? ? | | . x x | ? ? ? | ? ? ? | +-------+-------+-------+`

This would be fairly easy and it would be possible to continue to exclude impossible patterns
coloin

Posts: 1857
Joined: 05 May 2005

coloin wrote:In the challenging quest to find a minimal fully symmetric 36 clue puzzle, perhaps the best way to confirm possible valid minimal subpuzzle patterns would be to generate a minimal puzzle with this pattern [for example] plus a few clues in B6B8B9

Code: Select all
`+-------+-------+-------+ | . x x | x . x | x x . | | x . . | . x . | . . x | | x . . | . x . | . . x | +-------+-------+-------+ | x . . | . x . | ? ? ? | | . x x | x . x | ? ? ? | | x . . | . x . | ? ? ? | +-------+-------+-------+ | x . . | ? ? ? | ? ? ? | | x . . | ? ? ? | ? ? ? | | . x x | ? ? ? | ? ? ? | +-------+-------+-------+`

Is this what you meant? This puzzle is minimal.
Code: Select all
` . 5 6 8 . 9 4 7 . 9 . . . 7 . . . 6 7 . . . 4 . . . 8 6 . . . 9 . . . . . 8 2 6 . 7 . 3 . 3 . . . 2 . . . . 4 . . . . . . . . 8 . . . . . . 6 . . 9 3 . . . . . .`

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 10480
Joined: 15 May 2006
Location: Berlin

Yes, thanks.
So possibly the full 36 clue pattern might have a minimal puzzle.
I think Mauricio is looking at this.........
C
coloin

Posts: 1857
Joined: 05 May 2005

At least he is reducing the number of potential patterns step by step
ravel

Posts: 998
Joined: 21 February 2006

I wrote:This pattern too is not minimal, I searched exhaustively and found 0 minimal subpuzzles:
Code: Select all
`+-------+-------+-------+| . . x | x x x | x . . || . x x | . . . | x x . || x x . | . . . | . x x |+-------+-------+-------+| x . . | . . . | . . . || x . . | . . . | . . . || x . . | . . . | . . . |+-------+-------+-------+| x x . | . . . | . . . || . x x | . . . | . . . || . . x | . . . | . . . |+-------+-------+-------+`

I found a potential hole in my logic when searching exhaustively for this pattern, so maybe the result is not true after all, I'll redo the calculations and update it accordingly.
Mauricio

Posts: 1174
Joined: 22 March 2006

PreviousNext