Fully symmetrical puzzles

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

Fully symmetrical puzzles

Postby JPF » Sat Apr 01, 2006 12:14 am

Thanks Gordon for the description of symmetries in puzzles using the Group theory.

In some recent threads (or this one), we saw many fully symmetrical puzzles.
Like this one :
Code: Select all
 . . . | . 7 . | . . .
 . . 5 | . . . | 9 . .
 . 3 . | 5 . 4 | . 2 .
-------+-------+-------
 . . 3 | . 4 . | 1 . .
 4 . . | 3 . 1 | . . 9
 . . 1 | . 5 . | 8 . .
-------+-------+-------
 . 8 . | 7 . 2 | . 5 .
 . . 9 | . . . | 6 . .
 . . . | . 1 . | . . .

with the pattern :
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 . . . .
Lots of them are very nice.

As far as I'm concern, I'm happy with some of my collection...
Here is one :

Code: Select all
 . . . | 3 . 2 | . . .
 . . 2 | 6 . 1 | 7 . .
 . 7 . | . . . | . 4 .
-------+-------+-------
 9 3 . | . . . | . 5 4
 . . . | . 8 . | . . .
 6 8 . | . . . | . 3 9
-------+-------+-------
 . 9 . | . . . | . 1 .
 . . 8 | 5 . 4 | 6 . .
 . . . | 1 . 7 | . . .

or this one :

Code: Select all

 6 . . | 3 1 9 | . . 7
 . . . | 2 . 4 | . . .
 . . . | . . . | . . .
-------+-------+-------
 1 8 . | . . . | . 6 9
 7 . . | . 6 . | . . 1
 2 4 . | . . . | . 7 5
-------+-------+-------
 . . . | . . . | . . .
 . . . | 4 . 8 | . . .
 9 . . | 7 5 3 | . . 6
... even if tarek doesn't like them...:(

but stuck with those 2 patterns, unable to get a valid puzzle (each of those 2 examples has 2 solutions).
Code: Select all
 . . . | 2 8 5 | . . .
 . . 4 | . . . | 2 . .
 . 6 . | . . . | . 3 .
-------+-------+-------
 5 . . | . . . | . . 4
 3 . . | . 7 . | . . 8
 2 . . | . . . | . . 9
-------+-------+-------
 . 1 . | . . . | . 7 .
 . . 9 | . . . | 5 . .
 . . . | 3 1 2 | . . .


Code: Select all
 . . 3 | 8 9 2 | 4 . .
 . 4 . | . . . | . 6 .
 8 . . | . . . | . . 3
-------+-------+-------
 3 . . | . . . | . . 5
 9 . . | . 4 . | . . 7
 2 . . | . . . | . . 4
-------+-------+-------
 7 . . | . . . | . . 8
 . 9 . | . . . | . 1 .
 . . 8 | 2 1 3 | 5 . .



I was wondering how many fully symmetrical patterns have at least one valid puzzle. In that case, I would call it a "fully symmetrical valid pattern"(FSVP).
More precisely, the idea would be to set up a list of all them (where ?), with an example for each one (a minimal puzzle, if possible).

So, my first move was to count the number of fully symmetrical patterns.

It's 2^15=32768, as Gordon recall it, ( the whole dihedral group D_8).

More precisely, let N(c) be the number of patterns with c clues (0<=c<=81).
We have the following relations :

N(81-c)=N(c) ; c = 0,...,81 (1)
N(4k)=N(4k+1) ; k = 0,...,20 (2)
N(4k+2)=N(4k+3)=0 ; k = 0,...,19 (3)

And the distribution of N(c) can be summarized in the table below :

Code: Select all
Number            Number
of clue         of patterns
(c)               N(c)

0                   1
1                   1
4                   8
5                   8
8                  34
9                  34
12                104
13                104
16                253
17                253
20                512
21                512
24                888
25                888
28               1344
29               1344
32               1794
33               1794
36               2128
37               2128
40               2252
41               2252

The remaining values can be calculated by symmetry (!), using the relation (1).

Evidently, each pattern with 4k+1 clues is made of one pattern with 4k clues and an x in R5C5. (2)

Assuming (conjecture A) that the minimum clues number for a valid puzzle is 17 and that there is no symmetrical puzzle with 17 clues (conjecture B), there is no FSVP for n<20.
Assuming (conjecture C) that the maximum clues for a minimal puzzle is... let's say 37 to be "safe" :

we need to look at 2x(512+888+1344+1794+2128)=2x6666=13332 patterns only !:)

It works fine:D if, for a given pattern, a valid puzzle is found quickly , and will be painfull:( if not.

JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Re: Fully symmetrical puzzles

Postby Ocean » Mon Apr 03, 2006 1:38 pm

JPF wrote:I was wondering how many fully symmetrical patterns have at least one valid puzzle. In that case, I would call it a "fully symmetrical valid pattern"(FSVP).
More precisely, the idea would be to set up a list of all them (where ?), with an example for each one (a minimal puzzle, if possible).

JPF


I assume you will end up with a large catalog. Here is a modest start (three minimal puzzles with 24 clues):

Code: Select all
+-------+-------+-------+
| . . . | 1 2 3 | . . . |
| . . 3 | . . . | 4 . . |
| . 2 . | . . . | . 5 . |
+-------+-------+-------+
| 6 . . | . 3 . | . . 5 |
| 7 . . | 8 . 9 | . . 2 |
| 1 . . | . 7 . | . . 9 |
+-------+-------+-------+
| . 9 . | . . . | . 8 . |
| . . 5 | . . . | 2 . . |
| . . . | 2 4 6 | . . . |
+-------+-------+-------+


+-------+-------+-------+
| . . . | 1 . 2 | . . . |
| . . 3 | . . . | 4 . . |
| . 5 . | . 3 . | . 1 . |
+-------+-------+-------+
| 6 . . | . 2 . | . . 1 |
| . . 7 | 8 . 4 | 2 . . |
| 8 . . | . 1 . | . . 5 |
+-------+-------+-------+
| . 4 . | . 8 . | . 5 . |
| . . 8 | . . . | 6 . . |
| . . . | 4 . 7 | . . . |
+-------+-------+-------+


+-------+-------+-------+
| . . 1 | 2 . 3 | 4 . . |
| . 5 . | . . . | . 6 . |
| 7 . . | . . . | . . 8 |
+-------+-------+-------+
| 1 . . | 5 . 8 | . . 6 |
| . . . | . . . | . . . |
| 4 . . | 3 . 2 | . . 9 |
+-------+-------+-------+
| 2 . . | . . . | . . 7 |
| . 8 . | . . . | . 4 . |
| . . 3 | 1 . 6 | 9 . . |
+-------+-------+-------+
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Ruud » Mon Apr 03, 2006 2:14 pm

JPF wrote:we need to look at 2x(512+888+1344+1794+2128)=2x6666=13332 patterns only !

Have you considered that simultaneous permutation of rows 1-3 & 7-9 and columns 1-3 & 7-9 allow you to reduce the number of patterns that you need to find?

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Re: Fully symmetrical puzzles

Postby tarek » Wed Apr 05, 2006 8:51 pm

JPF wrote:even if tarek doesn't like them...:(

I liked them, however they were too tough for the thread however...
this modified one....
Code: Select all
JPF/tarek

 6 . . | 3 1 9 | . . 7 
 . 1 . | 2 . 4 | . 5 . 
 . . . | . . . | . . . 
-------+-------+------
 1 8 . | . . . | . 6 9 
 7 . . | . 2 . | . . 1 
 2 4 . | . . . | . 7 5 
-------+-------+------
 . . . | . . . | . . . 
 . 6 . | 1 . 8 | . 3 . 
 9 . . | 7 5 3 | . . 6
keeps the full symmetry, & is easier & will go on the list with another modification that will lose the full symmetry but keeping the 180 rotational symmetry

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: Fully symmetrical puzzles

Postby Ocean » Sat Apr 08, 2006 2:34 pm

JPF wrote:I was wondering how many fully symmetrical patterns have at least one valid puzzle. In that case, I would call it a "fully symmetrical valid pattern"(FSVP).
More precisely, the idea would be to set up a list of all them (where ?), with an example for each one (a minimal puzzle, if possible).

Two fully symmetrical patterns with 25 clues, illustrated with minimal 25s.
Code: Select all
 . 5 . | . . . | . 9 .
 6 8 . | . . . | . 4 2
 . . . | 7 . 2 | . . .
-------+-------+------
 . . 6 | . 3 . | 5 . .
 . . . | 2 1 4 | . . .
 . . 8 | . 9 . | 4 . .
-------+-------+------
 . . . | 9 . 3 | . . .
 2 1 . | . . . | . 5 8
 . 4 . | . . . | . 6 .

######################

 . . 4 | . . . | 7 . .
 . 1 . | . 4 . | . 6 .
 6 . 7 | . . . | 1 . 9
-------+-------+------
 . . . | 9 . 2 | . . .
 . 6 . | . 3 . | . 9 .
 . . . | 8 . 6 | . . .
-------+-------+------
 1 . 6 | . . . | 8 . 5
 . 5 . | . 2 . | . 7 .
 . . 3 | . . . | 2 . .



Also two patterns with 28 clues, illustrated with minimal 28s.
Code: Select all
 3 . 2 | . . . | 1 . 5
 . . 4 | . . . | 8 . .
 5 7 . | . . . | . 2 9
-------+-------+------
 . . . | 5 1 7 | . . .
 . . . | 8 . 9 | . . .
 . . . | 3 2 6 | . . .
-------+-------+------
 4 9 . | . . . | . 3 2
 . . 5 | . . . | 9 . .
 2 . 8 | . . . | 7 . 1

######################

 8 . . | . 6 . | . . 9
 . 9 . | 1 . 7 | . 8 .
 . . . | 3 . 8 | . . .
-------+-------+------
 . 4 8 | . . . | 3 5 .
 5 . . | . . . | . . 4
 . 1 2 | . . . | 6 7 .
-------+-------+------
 . . . | 6 . 4 | . . .
 . 5 . | 8 . 2 | . 4 .
 3 . . | . 5 . | . . 7


And one pattern with 29 clues, illustrated with a minimal 29.
Code: Select all
 . . . | . . . | . . .
 . 6 . | 1 . 4 | . 7 .
 . . 9 | 7 . 8 | 4 . .
-------+-------+------
 . 9 2 | 4 . 6 | 5 1 .
 . . . | . 5 . | . . .
 . 7 5 | 9 . 1 | 6 2 .
-------+-------+------
 . . 6 | 3 . 9 | 2 . .
 . 8 . | 2 . 7 | . 3 .
 . . . | . . . | . . .
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby JPF » Mon Apr 10, 2006 11:54 pm

A bit busy these days...

Ocean wrote:Here is a modest start (three minimal puzzles with 24 clues)
...
Two fully symmetrical patterns with 25 clues, illustrated with minimal 25s.
...
Also two patterns with 28 clues, illustrated with minimal 28s.
...
And one pattern with 29 clues, illustrated with a minimal 29.

Many thanx for your 8 FS minimal puzzles.
They are really brilliant !
Ruud wrote:Have you considered that simultaneous permutation of rows 1-3 & 7-9 and columns 1-3 & 7-9 allow you to reduce the number of patterns that you need to find?

No, I haven't, but you are right. Thanks.
These permutations reduce the number of patterns to be considered.

In order to list the FS patterns, I'm using the following rule :
One pattern is entirely defined by 15 bits (ie, blank (0) or x (1) in RiCj with 1<=i<=j=5).
Let t(i,j) be the bit in RiCj.( 1<=i<=j=5)
The pattern can be characterized by 5 numbers a,b,c,d,e :

Code: Select all
a=t(1,1)t(1,2)t(1,3)t(1,4)t(1,5)        0<=a<=31
b=t(2,2)t(2,3)t(2,4)t(2,5)              0<=b<=15
c.......................................0<=c<=7
d.......................................0<=d<=3
e=t(5,5)                                0<=e<=1

So, for instance, this Ocean's puzzle
Code: Select all
 . . . | 1 2 3 | . . .
 . . 3 | . . . | 4 . .
 . 2 . | . . . | . 5 .
-------+-------+-------
 6 . . | . 3 . | . . 5
 7 . . | 8 . 9 | . . 2
 1 . . | . 7 . | . . 9
-------+-------+-------
 . 9 . | . . . | . 8 .
 . . 5 | . . . | 2 . .
 . . . | 2 4 6 | . . .

has the mask :
Code: Select all
Row 1 :00011 = 3
Row 2 : 0100 = 4
Row 3 :..000 = 0
Row 4 :...01 = 1
Row 5 : ...0 = 0

and the pattern : 3-4-0-1-0
the puzzle itself :
Code: Select all
000123000003000400020000050600030005700809002100070009090000080005000200000246000
We can add 24 clues, M (for minimal)

Circles.
In a first step, one can consider the patterns delimited by one circle of radius equal to 4, like Ocean's one mentioned above.
These patterns are defined by the following code :

3-b-c-d-e
4<=b<=7; 0<=c<=7; 0<=d<=3; 0<=e<=1

There are 2^8 = 256 possible patterns.
The distribution of the number of clues is :
Code: Select all
Number      Number
of clues      of patterns

20            1
21            1
24            5
25            5
28            12
29            12
32            20
33            20
36            26
37            26
40            26
41            26
44            20
45            20
48            12
49            12
52            5
53            5
56            1
57            1

Here are some examples :

3- 4- 0- 2- 0 ; 24 clues, NSM (not symetrically minimal) :
Code: Select all
 . . . | 2 1 9 | . . .
 . . 6 | . . . | 2 . .
 . 4 . | . . . | . 9 .
-------+-------+-------
 9 . . | 1 . 8 | . . 5
 5 . . | . . . | . . 6
 6 . . | 7 . 2 | . . 3
-------+-------+-------
 . 1 . | . . . | . 6 .
 . . 2 | . . . | 4 . .
 . . . | 9 7 5 | . . .
(The minimum one from Ocean above is a 6- 8- 0- 2- 0 ; 24 clues , M ; Not a real circle)

3- 4- 2- 0- 0 ; 28 clues, NSM :
Code: Select all
 . . . | 1 2 7 | . . .
 . . 4 | . . . | 7 . .
 . 3 . | 8 . 4 | . 2 .
-------+-------+-------
 3 . 7 | . . . | 6 . 9
 5 . . | . . . | . . 3
 4 . 1 | . . . | 2 . 7
-------+-------+-------
 . 2 . | 7 . 8 | . 3 .
 . . 5 | . . . | 9 . .
 . . . | 5 1 6 | . . .

3- 4- 3- 0- 0 ; 32 clues, NSM :
Code: Select all
 . . . | 6 9 8 | . . .
 . . 2 | . . . | 9 . .
 . 9 . | 2 5 3 | . 4 .
-------+-------+-------
 7 . 5 | . . . | 4 . 3
 2 . 6 | . . . | 5 . 7
 3 . 9 | . . . | 1 . 8
-------+-------+-------
 . 7 . | 5 6 4 | . 1 .
 . . 3 | . . . | 6 . .
 . . . | 3 7 2 | . . .

3- 5- 2- 2- 0 ; 36 clues, NSM :
Code: Select all
 . . . | 5 4 2 | . . .
 . . 1 | . 3 . | 2 . .
 . 6 . | 1 . 8 | . 9 .
-------+-------+-------
 2 . 6 | 4 . 1 | 7 . 9
 7 1 . | . . . | . 8 2
 8 . 5 | 2 . 7 | 3 . 4
-------+-------+-------
 . 4 . | 8 . 9 | . 2 .
 . . 8 | . 1 . | 5 . .
 . . . | 6 2 4 | . . .

3- 7- 7- 0- 0 ; 48 clues, NSM :
Code: Select all
 . . . | 9 6 7 | . . .
 . . 6 | 1 2 3 | 9 . .
 . 9 7 | 4 8 5 | 3 6 .
-------+-------+-------
 3 2 9 | . . . | 1 7 5
 8 6 5 | . . . | 4 9 3
 1 7 4 | . . . | 2 8 6
-------+-------+-------
 . 5 8 | 2 3 4 | 7 1 .
 . . 3 | 6 9 1 | 8 . .
 . . . | 5 7 8 | . . .

until the 3- 7- 7- 3- 1 ; 57s clues :
Code: Select all
 . . . | 7 2 8 | . . .
 . . 7 | 4 3 1 | 5 . .
 . 3 8 | 6 9 5 | 2 7 .
-------+-------+-------
 7 5 3 | 8 1 4 | 6 9 2
 9 8 1 | 5 6 2 | 4 3 7
 6 4 2 | 3 7 9 | 8 5 1
-------+-------+-------
 . 7 9 | 2 8 6 | 1 4 .
 . . 4 | 9 5 7 | 3 . .
 . . . | 1 4 3 | . . .


Unfortunately, all my puzzles are not SM, but very easy to solve:)

and what about this one ? (3- 4- 0- 0 -1; 21 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 | . . .



JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Re: Fully symmetrical puzzles

Postby Ocean » Fri Apr 14, 2006 8:09 pm

Sudokus with fullsymetric patterns with 20 clues are quite rare, but here is one example.

Code: Select all
20 clues. Minimal. Full symmetry.

 . . . | . . . | . . .
 . . 1 | . 2 . | 3 . .
 . 4 . | 5 . 6 | . 7 .
-------+-------+------
 . . 4 | . . . | 1 . .
 . 7 . | . . . | . 8 .
 . . 2 | . . . | 6 . .
-------+-------+------
 . 8 . | 9 . 7 | . 5 .
 . . 3 | . 6 . | 2 . .
 . . . | . . . | . . .
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby JPF » Mon Apr 17, 2006 10:28 pm

Ocean wrote:Sudokus with fullsymetric patterns with 20 clues are quite rare, but here is one example.

Wonderful !
0-5-2-0-0 ; 20 clues ; M (minimal)
You produce so much splendid grids that I have a great deal of difficulty…
… to classify them.

Ok, let’s try the 20-clues fully symmetrical patterns.
But, unfortunately, I have no contribution at the moment:(

Here is one posted by ab in an other thread :
Code: Select all
 7 9 . | . . . | . 5 4
 5 . . | . . . | . . 7
 . . . | . 1 . | . . .
-------+-------+-------
 . . . | 1 . 2 | . . .
 . . 8 | . . . | 1 . .
 . . . | 5 . 7 | . . .
-------+-------+-------
 . . . | . 9 . | . . .
 6 . . | . . . | . . 3
 2 4 . | . . . | . 7 9


24- 0- 1- 2- 0 ; 20 clues ; SM (symmetric minimal)
Is it possible to make it absolutely minimal ?

JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Tue Apr 18, 2006 3:59 pm

here is a list of minimal full symmetric puzzles generated overnight
sorted and uniq'd by your nomenclature
a neat 28 clue minimal popped out
Code: Select all
2 7 .  . . .  . 9 1
6 . 8  . . .  5 . 7
. 9 .  . . .  . 6 .

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

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

and the list

000000000004030500030106080003709400010000050007804300080201030002070900000000000 # 0-5-2-2-0
000000000008702600010805070037000940000040000025000130050407020001308500000000000 # 0-6-2-0-1
000000000008605900027000350040090060000402000010070080069000520005809400000000000 # 0-6-4-1-0
000000000007803500045000860070050090000346000060020080092000150004905700000000000 # 0-6-4-1-1
000000000001849200092000180020060010030408060080020030014000870008594600000000000 # 0-7-4-1-0
000000000031000960060504030007030600000605000002010700040209010086000340000000000 # 0-12-2-1-0
000000000045000780090308040002040900000819000001060300030401090014000250000000000 # 0-12-2-1-1
000000000039000450010806020006302100000050000003901800090105040042000730000000000 # 0-12-2-2-1
000060000005000900040903060002090300900804001007010200090501080006000700000040000 # 1-4-2-1-0
000090000008000500020408090007905600400000008001806400070601050003000100000030000 # 1-4-2-2-0
000080000002309500060000070090030020500402001070060080040000010003704600000090000 # 1-6-0-1-0
000020000003608700020403080058000670700000001061000820080307010007901500000040000 # 1-6-2-0-0
000708000000591000006000500970000026060000050310000078002000400000236000000107000 # 2-3-4-0-0
000506000001000200050080060800030007002608400900010003080050070007000900000301000 # 2-4-1-1-0
000104000006000400090060070500403007008000100900205004070020010003000500000609000 # 2-4-1-2-0
000105000007000500090408020402000305000000000308000204030209060006000100000503000 # 2-4-2-0-0
000407000001000200070103050102000804000090000409000603040501020006000100000809000 # 2-4-2-0-1
000407000006000100048000950500010006000208000900030002029000840001000700000503000 # 2-4-4-1-0
000307000001000900092000860500609002000000000900704001018000540004000300000502000 # 2-4-4-2-0
000603000001000300078000240200504009000090000900708002037000820006000400000401000 # 2-4-4-2-1
000209000002010500060000010200090006030105070100080004070000090005060800000302000 # 2-5-0-1-0
000201000001080500040000060200307009070000020900506001050000030009010200000403000 # 2-5-0-2-0
000903000002080600030000040100706009050040020900108003080000070005010200000205000 # 2-5-0-2-1
000705000006020100050090030800000007041000320200000001030060040005030200000902000 # 2-5-1-0-0
000304000004060300050010070400000009076090210100000008060050030005020100000709000 # 2-5-1-0-1
000107000004906300030000060910000026000000000850000017040000070007804500000609000 # 2-6-0-0-0
000801000008307200070000030960000057000060000540000061090000040005403700000106000 # 2-6-0-0-1
000907000060000040009080300700030002001509600300070009008060200040000090000103000 # 2-8-5-1-0
000604000050000080001308700407000306000060000905000801008109400070000090000705000 # 2-8-6-0-1
000609000020050040009000800600080007040506020200040005004000900030060010000702000 # 2-9-4-1-0
000209000080060070006000200300501008010000030600902004001000600090040080000807000 # 2-9-4-2-0
000807000060050070001020800600000003092000650700000004003010900020070010000603000 # 2-9-5-0-0
000503000060804020008000600740000052000020000920000046009000300050608010000701000 # 2-10-4-0-1
000107000051000280030000050900060005000209000100070006060000030048000190000402000 # 2-12-0-1-0
000204000073000690020000080800401005000000000900603001080000010061000430000905000 # 2-12-0-2-0
000304000012000950070000020900603008000040000100809004080000060065000340000206000 # 2-12-0-2-1
000906000035708920080000070870000045000000000260000089090000060048107350000805000 # 2-14-0-0-0
000132000002000800050000040700050003400809005500060008070000010003000600000625000 # 3-4-0-1-0
000235000009000800030000010800407002100000004400502006070000050001000600000986000 # 3-4-0-2-0
000914000002060800040000060700000002960050037300000001080000020003090100000725000 # 3-5-0-0-1
000216000070000080009000100900050002400601003300080007005000600010000040000967000 # 3-8-4-1-0
000964000070000090008000500200408005900000007700102008009000100030000040000786000 # 3-8-4-2-0
002000100000060000800507003003020700020803090001090800700208001000030000005000400 # 4-1-2-1-0
004000200000302000900080005080020060003106800070040010800010004000607000002000600 # 4-2-1-1-0
001000700000509000400080003010305020006000500070802010300010007000208000005000900 # 4-2-1-2-0
003000200000204000600903008059000130000000000086000450400809002000107000005000600 # 4-2-2-0-0
003000100000509000600807003058000340000050000021000680100603008000705000006000900 # 4-2-2-0-1
009000600000901000504000807030020080000107000080050040806000102000706000007000900 # 4-2-4-1-0
007000500000105000109000603010020030000798000090050020504000801000806000001000900 # 4-2-4-1-1
004000900000604000203000705070806010000020000020905080605000807000507000008000300 # 4-2-4-2-1
001000900000264000200000005060090070080602090050070010800000004000425000009000100 # 4-3-0-1-0
001000300000967000400000006070040090050293010040050020500000008000638000003000200 # 4-3-0-1-1
003000200000964000100000008050308040080000020010409030600000009000153000008000400 # 4-3-0-2-0
003000800000418000400000007030209070020040030010503080100000004000361000009000600 # 4-3-0-2-1
005000600000894000400010009060000050034050970010000030600070002000639000001000500 # 4-3-1-0-1
008000400003060700240000013000602000080000090000704000790000056001020900004000300 # 4-5-0-2-0
002000900010000040400802007004050600000301000003080200200709001090000030005000400 # 4-8-2-1-0
002000900030000040500207006006701500000000000001502400900306001080000060004000200 # 4-8-2-2-0
002000700080000090600809001007508200000030000008201400900407008050000070004000900 # 4-8-2-2-1
008000300030050080709000506000706000010000040000902000903000407070080090002000800 # 4-9-4-2-0
001000400040507080600010005010000070008000300020000090400060009030401050009000800 # 4-10-1-0-0
001000200045000780370000061000183000000409000000527000680000042013000950007000600 # 4-12-0-3-0
005000600014060890380000042000702000030000050000401000150000024043010780007000300 # 4-13-0-2-0
003060900000708000600000004070080010200406009090010020700000001000305000004090300 # 5-2-0-1-0
001030600000108000700000001090802070400000009020601080800000005000903000006070100 # 5-2-0-2-0
008070200000203000600090003040000070709000508030000090100030007000905000004060800 # 5-2-1-0-0
001060300000203000800050002070000080504030601030000070700020004000105000006090800 # 5-2-1-0-1
006020700000406000500803006053000140400000007029000650200304009000708000008090500 # 5-2-2-0-0
001070900030000050804000102000106000300000008000409000108000407040000020006020800 # 5-8-4-2-0
007030200040906030500000004060000050100000006080000040900000007030502080008060500 # 5-10-0-0-0
002308700000000000700020005600709004004000300900601008800060003000000000001402500 # 6-0-1-2-0
006708300000000000800412006102000903007000800608000705500146009000000000004905600 # 6-0-3-0-0
001908300000000000803000204200030007000802000100070005509000108000000000004501900 # 6-0-4-1-0
007208100000070000300000005800504006060000090100307004700000008000050000005801200 # 6-1-0-2-0
003701600000090000500020007400000002032000410900000006300070005000050000006208300 # 6-1-1-0-0
003201500000040000500306007206000901030000020801000405100402003000060000005803100 # 6-1-2-0-0
001705600000301000800000002730000094000000000260000035400000007000609000005207400 # 6-2-0-0-0
008109300000607000100000008620000017000060000840000026400000005000301000005204100 # 6-2-0-0-1
001504900020000060500000004900080006000201000300070001200000005060000070003807400 # 6-8-0-1-0
008209700060000080300000005500080001000624000800030006600000007050000040002506800 # 6-8-0-1-1
001205300040000070200000006700302008000000000400906005600000002030000040007603900 # 6-8-0-2-0
007802400040000060200000001800407002000090000900508003400000007080000090002603800 # 6-8-0-2-1
010000050400000002000719000007020100004607300006030400000276000700000009030000040 # 8-0-3-1-0
030000050900000006000615000001090800009537600002040300000763000400000008010000090 # 8-0-3-1-1
010000070900000008000587000008401300003000700001703200000894000200000005060000010 # 8-0-3-2-0
070000060300000005001907400008040600000602000009050300007308900800000001030000080 # 8-0-6-1-0
030000070900000006006307400002908100000000000007504300001406200300000005020000080 # 8-0-6-2-0
010000050300050009000807000007010900050203060009070800000604000400030008090000020 # 8-1-2-1-0
030000010900030006000809000007060900020147030004050600000302000800010003060000070 # 8-1-2-1-1
030000050500080007000302000007601400090000060006208700000705000800030001020000090 # 8-1-2-2-0
050000080900702004000090000090040070001609500080070020000010000200306001070000050 # 8-2-1-1-0
050000040600204001000801000026000750000000000075000830000105000400302008010000090 # 8-2-2-0-0
020000030300407008008000400060080020000302000050060010009000100200503006010000070 # 8-2-4-1-0
010000040200407005009000700040010030000862000070050060003000900500103008080000020 # 8-2-4-1-1
070000080205000301060040050000501000007060100000402000010020040608000502050000060 # 8-4-1-2-1
040000020701000308065000710000692000000507000000184000072000480304000107080000060 # 8-4-4-3-0
010000080370000091000407000008040900000908000002050100000603000950000024030000010 # 8-8-2-1-0
060000070820000061000801000004030200000725000005090600000903000570000028090000030 # 8-8-2-1-1
040000070920000061000603000004502900000000000008309700000805000270000043060000010 # 8-8-2-2-0
030000040940000061000509000002104500000080000006705200000401000560000097010000020 # 8-8-2-2-1
010030080500000003000208000005040700300601009006090400000809000900000001070010040 # 9-0-2-1-0
040070050800000002000601000007305600600000009009204300000506000300000004020080070 # 9-0-2-2-0
050070030900000006000304000009103400800060002001209800000701000600000004040090020 # 9-0-2-2-1
010020070400010006000305000001000300320000089004000500000204000600030002090070060 # 9-1-2-0-0
060090050700506001000000000010709060800030005070805040000000000100603004020040030 # 9-2-0-2-1
080040020400107008000050000090000080203060504070000030000070000600203001020010090 # 9-2-1-0-1
030050090460000031007000200000703000900040006000206000005000100670000058040080020 # 9-8-4-2-1
060804050100000007000020000200508009004000700900201004000080000800000002070605010 # 10-0-1-2-0
010603080400000006000208000607000308000000000308000705000309000700000002030405090 # 10-0-2-0-0
070309020300000005000801000503000602000090000106000407000706000800000001010902060 # 10-0-2-0-1
010708050900000007004000600800070001000304000300080004009000700500000008020105060 # 10-0-4-1-0
050209040200000001008000700100020006000685000800030009009000200300000004040708060 # 10-0-4-1-1
020806090500000004009000600300601002000030000800705009005000300200000008040509020 # 10-0-4-2-1
090601020600080005000000000400030009060805070200070003000000000800050004010903050 # 10-1-0-1-0
080106030900502001000000000430000062000020000210000078000000000800701004060405080 # 10-2-0-0-1
070805090380000072000000000200080005000704000800010007000000000640000029050108030 # 10-8-0-1-0
050908070910703048000000000630000084000000000180000063000000000560401037040307010 # 10-10-0-0-0
028000750400060003100000004000502000090000040000401000900000005200030006045000830 # 12-1-0-2-0
400000008000508000000693000048000130009000500051000980000975000000201000700000006 # 16-2-3-0-0
400000006000408000006010200090070080004603900030020010002040100000507000300000008 # 16-2-5-1-0
200000009000402000004301500039000650000000000076000320007906100000503000100000008 # 16-2-6-0-0
300000005000708000008403200015000670000080000079000830001805300000104000200000007 # 16-2-6-0-1
500000004000247000006000900030090010060408030050070040009000500000831000800000001 # 16-3-4-1-0
900000008000468000001000600080609010040000030020305090002000900000281000500000004 # 16-3-4-2-0
100000002008000500090208070005030600000104000004020300030905080006000200400000005 # 16-4-2-1-0
300000008008000900010502060007405100000000000005906400030604010006000500800000003 # 16-4-2-2-0
200000004007000100080903050008201600000030000005609300020805010009000700100000005 # 16-4-2-2-1
600000008008070400070106030005000300040000050009000600050201070007040800900000003 # 16-5-2-0-0
200000003009504200010000040060080020000205000080090070070000010001603500300000004 # 16-6-0-1-0
400000007007206100050000080080020060000967000020080090090000050008309200200000001 # 16-6-0-1-1
400000007006907200020000040040201090000000000080703060090000020001605400300000008 # 16-6-0-2-0
600000001070000080000628000007040600009302100008090300000436000020000050800000009 # 16-8-3-1-0
500000009010000080000457000001060700006732100009010300000985000080000020700000003 # 16-8-3-1-1
300000006020000090001405700007030200000806000003010500004107800070000040500000009 # 16-8-6-1-0
100000005060000090005604100007060900000253000002070400006501800040000010200000003 # 16-8-6-1-1
200000008090030020000104000004060700020307060005040100000503000050090040700000001 # 16-9-2-1-0
100000006080060020000809000005902100010000080003506200000705000070020030900000004 # 16-9-2-2-0
400000001020706040000203000013000650000000000045000980000807000030405060600000002 # 16-10-2-0-0
200000003080501020003000700070010030000209000010040060001000800060107040500000009 # 16-10-4-1-0
800000007030508010007010900080000090003000600050000070002080500040306080100000004 # 16-10-5-0-0
100000004072000390090050070000207000003000800000601000080090010026000580700000009 # 16-12-1-2-0
100090005000305000009000800090030040600802003080070050005000700000706000200010009 # 17-2-4-1-0
900060001000307000007090500010000030604000802090000060002050900000401000100080003 # 17-2-5-0-0
400050003003000400080020050000506000906000108000701000090070080001000300200030005 # 17-4-1-2-0
500030008020000050000509000009040600100603009003010700000401000060000090800070001 # 17-8-2-1-0
600030005090000030000109000001906300700000004003804100000403000020000070500020006 # 17-8-2-2-0
600010009097000530080000070000208000500000004000309000040000010032000740900020008 # 17-12-0-2-0
500609002000010000006502300907000104040000020105000706009203500000090000600408003 # 18-1-6-0-0
100502009000604000005000400960000027000000000570000041008000300000705000600103005 # 18-2-4-0-0
700201008005000600040000090400080001000305000500020003090000060004000100300902005 # 18-4-0-1-0
600109007030000020000080000100706008009000600700803004000050000040000060800907003 # 18-8-1-2-0
900108003020000070007000900500060004000501000700020001003000400010000060200307009 # 18-8-4-1-0
402000608000000000900506003001060400000107000008050300200809004000000000604000705 # 20-0-2-1-0
409000102000607000600000009080010090000806000040050010200000008000304000807000601 # 20-2-0-1-0
509000702000801000100000003020904050000000000040305060300000008000106000804000601 # 20-2-0-2-0
703000209060000070400030001000405000001000700000809000300040002050000090207000508 # 20-8-1-2-0
309000701020040050400000003000509000050000010000701000800000006070080030204000809 # 20-9-0-2-0
206000304040060050800000002000508000020030070000704000600000009010090040903000508 # 20-9-0-2-1
710000068800000009000703000002090800000607000006010500000901000500000001980000024 # 24-0-2-1-0
150000074300000009000408000005040300000516000007090400000209000700000001280000096 # 24-0-2-1-1
390000065700000008000702000005307800000000000003408900000504000100000004470000021 # 24-0-2-2-0
350000049100000002004050300000603000007000600000102000005010400900000007270000095 # 24-0-5-2-0
760000098100050007005000100000102000080000030000903000001000300800060004970000056 # 24-1-4-2-0
340000057500102009000000000020080070000206000010040020000000000800409001650000038 # 24-2-0-1-0
780000034500804006000000000090050070000412000010060050000000000200706008630000015 # 24-2-0-1-1
270000091608000507090000060000315000000209000000648000030000070406000908510000034 # 24-4-0-3-0
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gfroyle » Wed Apr 19, 2006 4:34 am

JPF wrote:24- 0- 1- 2- 0 ; 20 clues ; SM (symmetric minimal)
Is it possible to make it absolutely minimal ?
JPF


Hi JPF

I like the idea of creating a database of fully symmetric puzzles..

But can you explain your terminology of minimality to me...

SM = symmetric minimal means ... I am guessing that you mean it is minimal in the sense that removing any ENTIRE ORBIT (thus preserving the symmetry) makes it no longer valid

AM = absolutely minimal means ... removing any INDIVIDUAL CELL makes it no longer valid.. i.e. minimal in the usual sense.


So the perfect puzzle would be fully symmetric and absolutely minimal..


Is this the right idea...

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby nathanmcmaster » Wed Apr 19, 2006 5:57 pm

i think he has the right idea anyone else
nathanmcmaster
 
Posts: 5
Joined: 19 April 2006

Postby ab » Wed Apr 19, 2006 8:46 pm

Here's a minimal version of the 20 clue square puzzle:
Code: Select all
38.|...|.71
9..|...|..4
...|.2.|...
-----------
...|8.9|...
..4|...|6..
...|1.2|...
-----------
...|.5.|...
8..|...|..7
73.|...|.98

As well as 24-0-1-2-0, it can be thought of as 20-1-0-2-0, or 8-8-1-2-0 or 4-1-4-0-0
or 1-12-0-2-0 or 1-4-4-2-0. Generally every fully symmetric puzzle has 6 ways it can be written
corresponding to swapping rows 1,2 and 3 and columns 1,2 and 3 (as well as rows 7,8 and 9 and columns
7,8 and 9). I suggest you use the lowest number to record it, unless you want to count all 6 puzzles
even though they're esentially the same sudoku puzzle.

some more minimal 20s:
Code: Select all
.3.|...|.4.
6..|...|..3
..7|.2.|9..
-----------
...|3.8|...
..9|...|7..
...|5.6|...
-----------
..2|.1.|4..
5..|...|..6
.9.|...|.7.

from the superior thread. 8-0-5-2-0 but also 4-9-0-2-0 and 17-4-0-2-0. This has only 3 representations because
swapping rows 1 and 2 and columns 1 and 2 (along with rows 8 and 9 and columns 8 and 9) doesn't alter the pattern.
Code: Select all
6..|...|..5
...|4.3|...
..5|.7.|1..
-----------
.2.|...|.7.
..7|...|2..
.8.|...|.3.
-----------
..6|.2.|5..
...|7.8|...
4..|...|..3

16-2-5-0-0
2-8-5-0-0
17-2-4-0-0
16-9-2-0-0
2-9-4-0-0
17-8-2-0-0
Code: Select all
...|7.2|...
..2|.4.|6..
.6.|...|.5.
-----------
4..|...|..9
.1.|...|.3.
3..|...|..7
-----------
.8.|...|.9.
..4|.2.|1..
...|5.3|...

2-5-0-0-0
5-2-0-0-0
9-0-2-0-0
8-1-2-0-0
4-2-1-0-0
2-4-1-0-0

Code: Select all
...|...|...
..2|5.8|1..
.7.|...|.9.
-----------
.5.|.6.|.4.
...|3.2|...
.6.|.9.|.3.
-----------
.9.|...|.7.
..8|2.1|3..
...|...|...

0-4-2-1-0
0-6-0-1-0
4-0-2-1-0
6-0-0-1-0
8-2-0-1-0
10-0-0-1-0

Code: Select all
...|2.5|...
..7|...|4..
.9.|...|.3.
-----------
2..|.7.|..1
...|8.3|...
1..|.9.|..5
-----------
.4.|...|.8.
..8|...|5..
...|7.1|...

2-4-0-1-0
4-2-0-1-0
8-0-2-1-0
ab
 
Posts: 451
Joined: 06 September 2005

Postby JPF » Thu Apr 20, 2006 12:30 am

gsf wrote:here is a list of minimal full symmetric puzzles generated overnight
sorted and uniq'd by your nomenclature...

Thanks gsf.
That’s a lot of work for a night…
Your neat is a beauty.

I’m trying to organize myself to list the puzzles.
Not an easy task.
I noticed 3 “popular” patterns, already posted by Ocean in this thread :
2-4-1-1-0
6-8-0-2-0
8-8-2-1-1
absolutely minimal (M) in each case…

and 3 circles (radius = 4)
3-4-0-1-0
3-4-0-2-0
3-5-0-0-1

One of them :
3- 4- 0- 2- 0 ; 24 clues ; M
Code: Select all
 . . . | 2 3 5 | . . .
 . . 9 | . . . | 8 . .
 . 3 . | . . . | . 1 .
-------+-------+-------
 8 . . | 4 . 7 | . . 2
 1 . . | . . . | . . 4
 4 . . | 5 . 2 | . . 6
-------+-------+-------
 . 7 . | . . . | . 5 .
 . . 1 | . . . | 6 . .
 . . . | 9 8 6 | . . .


No 20-21 clues for the moment …

gfroyle wrote:But can you explain your terminology of minimality to me...

SM = symmetric minimal means ... I am guessing that you mean it is minimal in the sense that removing any ENTIRE ORBIT (thus preserving the symmetry) makes it no longer valid
AM = absolutely minimal means ... removing any INDIVIDUAL CELL makes it no longer valid.. i.e. minimal in the usual sense.

So the perfect puzzle would be fully symmetric and absolutely minimal..
Is this the right idea...
Yes, you are right.

I will try to develop :
A proper puzzle P is minimal if, for every puzzle Q such that Q<P (the set of clues of Q is included in the set of clues of P) ,
then N(Q)>1 ; (number of solutions of Q).

We can extend the definition of minimality to a class of puzzles.

Let s be a symmetry of the square (like you describe them).
A puzzle P is s-symmetric if its pattern P*={A1,…, An}is such that :
if Ai € P* => s(Ai) € P* ; i=1,..., n(P), number of clues of P.
A s-puzzle P will be s-minimal if, for every s-puzzle Q such that Q<P, then N(Q)>1.

And extend again this concept for a set of symmetries : s1, s2,…, sp :

A puzzle P is s1,s2,…,sp-symmetric if its pattern P*={A1,…, An}is such that :
if Ai € P* => sk(Ai) € P* ; i=1,...,n(P) ; k=1,...,p.
A s1,s2,…,sp - puzzle P will be s1,s2,…,sp - minimal if, for every s1,s2,…,sp -puzzle Q such that Q<P, then N(Q)>1.

Here we are considering the puzzles having the dihedral group as symmetries.
The puzzles Q are created by removing at least one orbit from P (i.e. : 1, 4 or 8 clues) to preserve the symmetry.
It’s what we will call symmetric-minimal puzzle(SM).

Obviously, an (absolutely) minimal (M) puzzle is a symmetric-minimal (SM) puzzle.

We can note that all the 20 clues fully symmetric puzzles are SM :
1. Each orbit has at least 4 clues.
2. There is no 16 clues proper puzzle (?)

gfroyle wrote:So the perfect puzzle would be fully symmetric and absolutely minimal..

I agree.

JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Postby kjellfp » Thu Apr 20, 2006 6:50 am

JPF wrote:We can note that all the 20 clues fully symmetric puzzles are SM

Yes. By accepting the conjecture that no symmetrical 17 exists, we can conclude that 20 is the minimum number for a fully symmetric puzzle, and also that a 21 clues fully symmetric is SM as long as removing the centre clue no longer makes it valid.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby JPF » Thu Apr 20, 2006 9:41 pm

Thanks ab for these 30 fully symmetric and minimal 20 clues puzzles.
ab wrote:As well as 24-0-1-2-0, it can be thought of as 20-1-0-2-0, or 8-8-1-2-0 or 4-1-4-0-0
or 1-12-0-2-0 or 1-4-4-2-0. Generally every fully symmetric puzzle has 6 ways it can be written
corresponding to swapping rows 1,2 and 3 and columns 1,2 and 3 (as well as rows 7,8 and 9 and columns
7,8 and 9).

Earlier in this thread, Ruud made the same comment, that I still have in mind :
Ruud wrote:Have you considered that simultaneous permutation of rows 1-3 & 7-9 and columns 1-3 & 7-9 allow you to reduce the number of patterns that you need to find?

To illustrate what you (and Ruud) mentioned, let’s have a look on the different patterns generated with your 20 clue square puzzle :
Code: Select all
24-0-1-2-0

 3 8 . | . . . | . 7 1
 9 . . | . . . | . . 4
 . . . | . 2 . | . . .
-------+-------+-------
 . . . | 8 . 9 | . . .
 . . 4 | . . . | 6 . .
 . . . | 1 . 2 | . . .
-------+-------+-------
 . . . | . 5 . | . . .
 8 . . | . . . | . . 7
 7 3 . | . . . | . 9 8


8-8-1-2-0

 . 9 . | . . . | . 4 .
 8 3 . | . . . | . 1 7
 . . . | . 2 . | . . .
-------+-------+-------
 . . . | 8 . 9 | . . .
 . . 4 | . . . | 6 . .
 . . . | 1 . 2 | . . .
-------+-------+-------
 . . . | . 5 . | . . .
 3 7 . | . . . | . 8 9
 . 8 . | . . . | . 7 .


1-4-4-2-0

 . . . | . 2 . | . . .
 . . 9 | . . . | 4 . .
 . 8 3 | . . . | 1 7 .
-------+-------+-------
 . . . | 8 . 9 | . . .
 4 . . | . . . | . . 6
 . . . | 1 . 2 | . . .
-------+-------+-------
 . 3 7 | . . . | 8 9 .
 . . 8 | . . . | 7 . .
 . . . | . 5 . | . . .


20-1-0-2-0
 
 3 . 8 | . . . | 7 . 1
 . . . | . 2 . | . . .
 9 . . | . . . | . . 4
-------+-------+-------
 . . . | 8 . 9 | . . .
 . 4 . | . . . | . 6 .
 . . . | 1 . 2 | . . .
-------+-------+-------
 8 . . | . . . | . . 7
 . . . | . 5 . | . . .
 7 . 3 | . . . | 9 . 8


4-1-4-2-0

 . . 9 | . . . | 4 . .
 . . . | . 2 . | . . .
 8 . 3 | . . . | 1 . 7
-------+-------+-------
 . . . | 8 . 9 | . . .
 . 4 . | . . . | . 6 .
 . . . | 1 . 2 | . . .
-------+-------+-------
 3 . 7 | . . . | 8 . 9
 . . . | . 5 . | . . .
 . . 8 | . . . | 7 . .


1-12-0-2-0

 . . . | . 2 . | . . .
 . 3 8 | . . . | 7 1 .
 . 9 . | . . . | . 4 .
-------+-------+-------
 . . . | 8 . 9 | . . .
 4 . . | . . . | . . 6
 . . . | 1 . 2 | . . .
-------+-------+-------
 . 8 . | . . . | . 7 .
 . 7 3 | . . . | 9 8 .
 . . . | . 5 . | . . .

That is everything from the square... to the circle !

Let’s say that these puzzles and therefore these patterns, are S-equivalent.

By opening this thread, my initial idea was to list all the FS (fully symmetric) patterns and for each of them to give (if possible) a valid minimal puzzle.
It is true that a FS puzzle (with its clues) gives, in addition, up to 5 new FS puzzles with different patterns.
Obviously, these adequate permutations of rows and columns preserve all type of minimality (and the number of clues !)
ab wrote:I suggest you use the lowest number to record it, unless you want to count all 6 puzzles
even though they're esentially the same sudoku puzzle.

As I don’t know yet how I’m going to list all this examples of valid patterns, I would suggest that we post one of the puzzles, the code of its pattern and if possible, the codes of the S-equivalent patterns.
Exactly as you did ab.

JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Next

Return to General

cron