The New Sudoku Players' Forum

[coloin]

As a follow on from the previous thread which is relevant ....

This 24C pattern cannot have puzzles.... it needs at least 3 added clues

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


However with the addition of suitably placed n number of clues it is possible to generate a minimal puzzle.

Q1. What is the observation which assists / makes a search more efficient
Q2. What is the range of values of n
Q3. What values of n have diagonally symmetrical puzzles if any

[coloin]

Saved for top answers

[m_b_metcalf]

This 24C pattern cannot have minimal puzzles....

coloin, to the best of my understanding, that pattern doesn't have any valid puzzles, let alone minimal ones . That aside, to start the ball rolling, here is a rotationally symmetric puzzle with four added clues (n = 4):

Code: Select all

 4 8 7 . . . . . .
 6 . 5 . . . . . .
 9 1 2 . . 8 . . .
 . . 9 7 8 2 . . .
 . . . 1 . 6 . . .
 . . . 3 5 9 1 . .
 . . . 2 . . 7 4 5
 . . . . . . 9 . 1
 . . . . . . 8 6 2

No. of givens =  28

Added: and these are diagonally symmetric, n = 4 (Q. 3):

Code: Select all

 5 8 2 . . . . . .
 6 . 3 . . . . . .
 4 7 1 2 . . 3 . .
 . . 4 1 7 2 . . .
 . . . 4 . 6 . . .
 . . . 3 8 5 . . .
 . . 5 . . . 1 8 3
 . . . . . . 7 . 9
 . . . . . . 4 2 5   ED=4.2/1.0/1.0

 5 8 2 . . . . . .
 6 . 3 . . . . . .
 4 7 1 2 . . 3 . .
 . . 4 1 7 2 . . .
 . . . 4 . 6 . . .
 . . . 3 8 5 . . .
 . . 5 . . . 2 6 4
 . . . . . . 7 . 5
 . . . . . . 1 3 9   ED=7.1/1.0/1.0

[JPF]

Just to give a general picture, there are 237083 B1B5B9 ed-puzzles
B1,B5,B9 having 9 or 8 clues.
The number of solutions varies from 95514 to 283576.

Code: Select all

+---+---+---+
|123|...|...|
|456|...|...|
|789|...|...|
+---+---+---+
|...|124|...|
|...|358|...|
|...|769|...|
+---+---+---+
|...|...|139|
|...|...|487|
|...|...|526|  95514 solutions
+---+---+---+


Code: Select all

+---+---+---+
|123|...|...|
|456|...|...|
|789|...|...|
+---+---+---+
|...|123|...|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|123|
|...|...|456|
|...|...|789|  283576 solutions
+---+---+---+


Here I gave, years ago !, a valid puzzle: B1B5B9 +3 clues:

Code: Select all

+---+---+---+
|123|...|...|
|4.6|...|...|
|789|...|...|
+---+---+---+
|...|194|.7.|
|.9.|2.3|...|
|...|765|...|
+---+---+---+
|...|...|437|
|...|.3.|6.8|
|...|...|125|
+---+---+---+


I recognize that in my answer there is nothing about minimality yet...

JPF

[Serg]

Hi, Mike!
Good job! I confirm minimality of your puzzles.
Starting pattern of course has no valid puzzles.
Answering Q1 - Mauricio proved that this pattern

Code: Select all

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

is non minimal (I'd prefer to use the term "avoidable pattern"). So, any minimal puzzle cannot contain such subpattern in its pattern. Therefore, additional clues being necessary to get minimal puzzle cannot be placed in rows r2, r5, r8 AND columns c2, c5, c8.

Serg

[m_b_metcalf]

More:

Code: Select all

 5 9 6 . . . . . .
 2 . 3 . . . . . .
 4 7 1 5 . . 3 . .
 . . 4 1 7 2 . . .
 . . . 4 . 9 . . .
 . . . 3 8 5 9 . .
 . . 5 . . 7 1 3 8
 . . . . . . 7 . 9
 . . . . . . 4 2 5   ED=4.2/1.0/1.0, n = 6, main diagonal, anti-diagonal and rotational symmetry.

 5 9 6 . . . . . .
 2 . 3 . . . . . .
 4 7 1 5 . . 3 . .
 . . 4 2 7 1 . . .
 . . . 4 . 9 . . .
 . . . 3 8 5 9 . .
 . . . . . 7 1 3 8
 . . . . . . 7 . 9
 . . . . . . 4 2 5   ED=4.2/1.0/1.0, n = 5,  anti-diagonal symmetry.

 5 9 3 . . . . . .
 2 . 6 . . . . . .
 4 7 1 2 . . . . .
 . . 4 1 7 2 . . .
 . . . 4 . 9 . . .
 . . . 3 8 5 9 . .
 . . 2 . . 7 1 3 8
 . . . . . . 7 . 9
 . . . . . . 4 2 5   ED=2.5/1.0/1.0, n = 5,  anti-diagonal symmetry.

[coloin]

A1. @ serg Well answered
A2. @m_b_metcalf Extra points for rotationally symmetric puzzles I would say .... so n=4.....
A3. @JPF I havn't explored the minimality of the n=3 puzzles .....but that was a good find in those days !!

The remaining question is how high can you go !!! [I have explored this !!!]

[coloin]

Just to give a general picture, there are 237083 B1B5B9 ed-puzzles

and quite a lot more 8*8*8 B1B5B9 for you to chose from !!

[m_b_metcalf]

The remaining question is how high can you go !!! [I have explored this !!!]

Code: Select all

 5 8 9 . . . . . .
 2 . 3 . . . . . .
 4 6 7 5 . . 3 . .
 . . 4 1 7 2 . . .
 . . . 4 . 9 . . .
 . . . 3 8 5 9 . .
 . . 5 . . 7 1 3 8
 . . . . . . 7 . 9
 7 . . . . . 4 2 5  n = 7, anti-diagonal symmetry

Regards,

Mike

[m_b_metcalf]

Code: Select all

 1 2 5 . . . . . 4
 4 . 3 . . . . . .
 7 6 9 4 . . 5 . .
 . . 7 8 3 4 . . .
 . . . 9 . 1 . . .
 . . . 5 7 2 3 . .
 . . 4 . . 5 1 6 3
 . . . . . . 7 . 5
 5 . . . . . 4 8 9   n = 8, all three symmetries, again!

M

[m_b_metcalf]

For good measure, these n = 8 puzzles with threefold symmetry also have rotational symmetry of values of givens:

Code: Select all

 1 2 3 . . . . . 4
 4 . 8 . . . . . .
 7 6 9 1 . . 3 . .
 . . 6 2 3 1 . . .
 . . . 4 . 6 . . .
 . . . 9 7 8 4 . .
 . . 7 . . 9 1 4 3
 . . . . . . 2 . 6
 6 . . . . . 7 8 9   ED=2.0/1.0/1.0

 1 2 3 . . . . . 4
 5 . 7 . . . . . .
 8 6 4 3 . . 2 . .
 . . 6 4 7 9 . . .
 . . . 8 . 2 . . .
 . . . 1 3 6 4 . .
 . . 8 . . 7 6 4 2
 . . . . . . 3 . 5
 6 . . . . . 7 8 9   ED=7.3/1.0/1.0

 1 2 3 . . . . . 4
 7 . 4 . . . . . .
 8 6 9 1 . . 2 . .
 . . 6 4 2 3 . . .
 . . . 9 . 1 . . .
 . . . 7 8 6 4 . .
 . . 8 . . 9 1 4 2
 . . . . . . 6 . 3
 6 . . . . . 7 8 9   ED=8.4/1.0/1.0

[coloin]

Those are great puzzles at n=8 ....... and very elegant ......
I don't expect SE to be much over 9.0 .... but I do know that there is some way to go with n

[m_b_metcalf]

Those are great puzzles at n=8 ....... and very elegant ......
I don't expect SE to be much over 9.0 .... but I do know that there is some way to go with n

Thanks. But I think I'll call it a day now, and look forward to seeing the answer soon.

Mike

[marek stefanik]

Interesting questions.

I have another observation for Q1:

Code: Select all

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

This pattern is not minimal.
Proof: Let a be the digit not given in b5. Two cases must be covered, that is whether or not a is given in b2.
Suppose a is given in b2, WLOG in c4. Then any given at the intersection of c4 and b5 is redundant (can be solved as a NS, using the a in b2 and other givens in b5).
Suppose a is not given in b2. Then with HS ab5 (using the givens in b5) and PC ab2\r2 (using the previous step and givens in b2), a in b1 is forced into r13, where it must be a given.
Then it can be solved as a HS (ab1 using previous steps and other givens in b1), hence it is redundant.

Marek

[coloin]

Yes I noticed that there was always a maximum of 3 clues in any of B2B3B4B6B7B8
Thanks for proving that

I think there maybe a limitation of 3 on the rows/columns as well

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 x x|
+-----+-----+-----+

presumably a pattern to avoid for minimal puzzle generation

minimal, n=8, no symmetry, with 3 clues in row, and 3 clues in a box

Code: Select all

1436.9..22.6......789.....6...231......4.6...4..978...6.....321......8.48.4...967