More Homework !

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

More Homework !

Postby coloin » Tue Jan 25, 2022 8:52 am

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 :?:
Last edited by coloin on Wed Jan 26, 2022 2:33 pm, edited 1 time in total.
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: More Homework !

Postby coloin » Tue Jan 25, 2022 9:03 am

Saved for top answers
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: More Homework !

Postby m_b_metcalf » Tue Jan 25, 2022 3:11 pm

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

Re: More Homework !

Postby JPF » Tue Jan 25, 2022 4:15 pm

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
JPF
2017 Supporter
 
Posts: 5897
Joined: 06 December 2005
Location: Paris, France

Re: More Homework !

Postby Serg » Tue Jan 25, 2022 4:20 pm

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
Serg
2018 Supporter
 
Posts: 785
Joined: 01 June 2010
Location: Russia

Re: More Homework !

Postby m_b_metcalf » Tue Jan 25, 2022 4:32 pm

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

Re: More Homework !

Postby coloin » Tue Jan 25, 2022 4:53 pm

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
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: More Homework !

Postby coloin » Tue Jan 25, 2022 4:58 pm

JPF wrote: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 !! :D
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: More Homework !

Postby m_b_metcalf » Tue Jan 25, 2022 5:16 pm

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

Re: More Homework !

Postby m_b_metcalf » Tue Jan 25, 2022 5:23 pm

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

Re: More Homework !

Postby m_b_metcalf » Tue Jan 25, 2022 7:23 pm

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

Re: More Homework !

Postby coloin » Tue Jan 25, 2022 9:34 pm

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
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Re: More Homework !

Postby m_b_metcalf » Wed Jan 26, 2022 8:58 am

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

Re: More Homework !

Postby marek stefanik » Wed Jan 26, 2022 2:16 pm

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
marek stefanik
 
Posts: 250
Joined: 05 May 2021

Re: More Homework !

Postby coloin » Wed Jan 26, 2022 2:26 pm

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
coloin
 
Posts: 2176
Joined: 05 May 2005
Location: Tenerife

Next

Return to General