Minimal Puzzles

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

Postby RW » Tue Oct 02, 2007 3:42 am

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

Postby gsf » Tue Oct 02, 2007 4:58 am

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

Postby Mauricio » Tue Oct 02, 2007 7:10 am

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

Postby coloin » Tue Oct 02, 2007 7:31 am

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*
xxo
xox
oxx

3*
xxx
xxx
ooo

3*
xxo
xxo
xxo

6*
xxx
xox
oxo

6*
xox
xxo
xox

......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*
xxx
xxo
xoo


C
coloin
 
Posts: 1715
Joined: 05 May 2005

Postby RW » Tue Oct 02, 2007 1:25 pm

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

Postby coloin » Tue Oct 02, 2007 6:46 pm

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
xxo
xox
oxx

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
xoo
xxx
oxx
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
xxx
xoo
xoo

C
coloin
 
Posts: 1715
Joined: 05 May 2005

Postby Mauricio » Wed Oct 03, 2007 7:04 am

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
100111000011000110011000100100000000100000000100000000011000000011000000000000000
010111000011000110011000100100000000100000000100000000011000000011000000000000000
000111000111000110011000100100000000100000000100000000011000000011000000000000000
000111000011000111011000100100000000100000000100000000011000000011000000000000000
000111000011000110111000100100000000100000000100000000011000000011000000000000000
000111000011000110011000101100000000100000000100000000011000000011000000000000000
000111000011000110011000100100000000100000000100000000011000000011000000010000000


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

Postby JPF » Wed Oct 03, 2007 8:12 am

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

[edit] you just edited your post before my answer...
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby Mauricio » Wed Oct 03, 2007 8:35 am

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

Postby Mauricio » Wed Oct 03, 2007 10:57 am

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

Postby coloin » Wed Oct 03, 2007 12:45 pm

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: 1715
Joined: 05 May 2005

Postby m_b_metcalf » Wed Oct 03, 2007 4:22 pm

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

Postby coloin » Thu Oct 04, 2007 11:59 pm

Yes, thanks.
So possibly the full 36 clue pattern might have a minimal puzzle.
I think Mauricio is looking at this.........
C
coloin
 
Posts: 1715
Joined: 05 May 2005

Postby ravel » Fri Oct 05, 2007 8:16 pm

At least he is reducing the number of potential patterns step by step:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Mauricio » Thu Oct 11, 2007 7:59 pm

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

Return to General