Symmetrical Givens

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

Re: Symmetrical Givens

Postby champagne » Tue May 26, 2015 1:34 am

Leren wrote:
12.3.....4....5.7.....4.3..7..1...5...2...8...5...9..3....6.....3.5....6.....7.89 _1
Not sure what you mean here. All 3 puzzles have anti-diagonal symmetry and only the first one is still hard after the symmetry move.

Leren


All these puzzles have a double diagonal symmetry of given, but are not minimal when the double symmetry can be seen.
I did not take care in the selection to choose (if they exist) a minimal form with a missing clue outside the diagonals. I have to revise the selection in that direction.

regarding the first puzzle, as soon as you have seen the anti-diagonal symmetry, you add the missing clue giving evidence of the main diagonal symmetry of given. Then the puzzle is solved easily
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby Leren » Tue May 26, 2015 6:09 am

Hi Champagne, only a small adjustment was required for me to see the second symmetry, which becomes apparent only after the first symmetry is detected.

In general it looks like careful consideration needs to be given to the selection of simple techniques to apply following a first symmetry, to avoid solving the puzzle before a second symmetry is detected.

Leren
Leren
 
Posts: 2897
Joined: 03 June 2012

Re: Symmetrical Givens

Postby champagne » Tue May 26, 2015 3:08 pm

it's not so easy to find hard puzzles leading to a double diagonal symmetry of given.
These 2 if I am right are examples. In both cases, 2 clues are missing in the minimal form of the puzzle

.2.5.....4.7.2.....3...1...5....39...4.....6...17....5...9...7.....8.3.67....5.89
1..2......5..6.........7..84..1..7...8.....2...3..9..62..3......7..4..5...6..8..9
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby eleven » Tue May 26, 2015 4:22 pm

A partial symmetry is of no worth, if assuming non symmetry leads nowhere and proving symmetry is (almost) as hard as solving the puzzle.
eleven
 
Posts: 1561
Joined: 10 February 2008

Re: Symmetrical Givens

Postby champagne » Tue May 26, 2015 5:18 pm

eleven wrote:A partial symmetry is of no worth, if assuming non symmetry leads nowhere and proving symmetry is (almost) as hard as solving the puzzle.


I don't catch the first part of the sentence, but if

proving symmetry is (almost) as hard as solving the puzzle.


I would fully agree
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby eleven » Tue May 26, 2015 9:42 pm

champagne wrote:
eleven wrote:A partial symmetry is of no worth, if assuming non symmetry leads nowhere and proving symmetry is (almost) as hard as solving the puzzle.

I don't catch the first part of the sentence, ...

[Edit:]I thought, i had an example how to eliminate a digit assuming non symmetry in your first example above, but it was wrong.
But at least in theory you can say, either it has a symmetry (with these implications) or not (with that implications), and hope for a common outcome.
eleven
 
Posts: 1561
Joined: 10 February 2008

Re: Symmetrical Givens

Postby champagne » Wed May 27, 2015 6:22 am

eleven wrote:[Edit:]I thought, i had an example how to eliminate a digit assuming non symmetry in your first example above, but it was wrong.
But at least in theory you can say, either it has a symmetry (with these implications) or not (with that implications), and hope for a common outcome.


let me be honest

Code: Select all
. 2 .   5 . .   . . .
4 . 7   . 2 .   . . .
. 3 .   . . 1   . . .

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

. . .   9 . .   . 7 .
. . .   . 8 .   3 . 6
7 . .   . . 5   . 8 9


if I were a manual solver, in that situation, I would use a T&S (try and solve)
If it is a sudoku (only one solution),
and if the solution has a symmetry of given

then you can check it easily adding missing clues
or you'll fail very fast if the solution has not a symmetry of given
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby champagne » Thu May 28, 2015 5:57 am

I searched all rotational 90 puzzles with symmetry of given using a similar process as for the double diagonal symmetry.

I find :

17402 ED minimal puzzles
876520 puzzles with a minimal symmetry of given, but not globally minimal

This should be cross-checked if the count is available from somebody else.

whatever is the right count, the search is very short (less than one hour with that process)

EDIT the count of ED puzzles per clues is the following

20 10
21 2
24 7467
25 886
28 8163
29 370
32 496
33 5
36 3

and the 3 "36 clues"

...1......75..431..12.3765..89.1...3..17.39..7...9.12..5437.89..976..53......9...
...1......17..453..52.3761..89.1...3..17.39..7...9.12..9437.85..756..39......9...
.1..9..7.9.2..61.3.73.2196..27......3.4...6.7......38..4198.73.7.94..8.1.3..1..9.
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby dobrichev » Thu May 28, 2015 4:00 pm

Here are 5 puzzles with 23 givens having backdoor of size 3 in singles and 180 deg rotational symmetry
Code: Select all
000007006003040200700800040001000023000010000450000100030006009005030400800900000

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


000007060004030500070600003001000032000010000450000100500008090003050200080900000

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


000007060004030500080600003001000032000010000450000100500009070003050200090800000

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


000001000002400003050070060090000607700090005508000090080050070400003100000200000

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


000001002000200030004050600009000076600090005540000900005060700010008000800300000

. . . . . 1 . . 2
. . . 2 . . . 3 .
. . 4 . 5 . 6 . .
. . 9 . . . . 7 6
6 . . . 9 . . . 5
5 4 . . . . 9 . .
. . 5 . 6 . 7 . .
. 1 . . . 8 . . .
8 . . 3 . . . . .
dobrichev
2016 Supporter
 
Posts: 1315
Joined: 24 May 2010

Re: Symmetrical Givens

Postby blue » Sat May 30, 2015 7:00 pm

champagne wrote:I searched all rotational 90 puzzles with symmetry of given using a similar process as for the double diagonal symmetry.

I find :

17402 ED minimal puzzles
876520 puzzles with a minimal symmetry of given, but not globally minimal

This should be cross-checked if the count is available from somebody else.

I get different results (below).
Here too, eleven reported finding 31263 minimals using 5 hours of random generation.

--

champagne wrote:some results on the DD symmetry.

The minimal count on my side confirms blue's results, 50781 puzzles.

I also collected puzzles having a "minimal symmetry", but not minimal stricto sensu and I found 1 906 799 puzzles.

The highest number of clues for such puzzles was 42 with 12 puzzles

Hidden Text: Show
Code: Select all
523.1.8..4.8.7.95.76..2..14....47...1342.8679...36....69..8..43.51.3.2.6..2.9.785
523.1.8..4.8.7.95.76..2..14....63...1348.2679...74....69..8..43.51.3.2.6..2.9.785
123.9.8..4.8.7.15.76..2..94....47...9342.8671...36....61..8..43.59.3.2.6..2.1.789
123.9.8..4.8.7.15.76..2..94....63...9348.2671...74....61..8..43.59.3.2.6..2.1.789
523.6.81.4.8.3..5976..1...4....83...8716.4932...72....6...9..4315..7.2.6.92.4.785
523.6.81.4.8.3..5976..1...4....27...8714.6932...38....6...9..4315..7.2.6.92.4.785
523.1.8..4.8.7.95.76..2..14...16....1348.2679....49...69..8..43.51.3.2.6..2.9.785
523.1.8..4.873.9..76..2..14.3..6....1748.2639....4..7.69..8..43..1.732.6..2.9.785
523.1.8..4.873.1..76..2..94.3..6....1748.2639....4..7.61..8..43..9.732.6..2.9.785
12637.9..4.7.9.6..83..4..217...8....3926.4817....2...398..6..72..4.1.3.6..1.37489
13..9.24.7.2.6.9.8.4.37..16..7.2....9834.6721....8.3..49..37.6.2.1.4.8.3.68.1..79
53..1.24.7.2.6.1.8.4.73..96..3.2....1874.6329....8.7..41..73.6.2.9.4.8.3.68.9..75

I get slightly different results for DD symmetry too.
BTW: your 12 symmetrically minimal 42's, contain only 9 ED puzzles.

--

I get these results ...

For DD symmetry:
Code: Select all
sz  s.minimal  minimal
----------------------
20         28       20
21         25       21
22       1678     1020
23       1372      604
24      27594     7943
25      16127     2389
26     165920    16995
27      64696     2560
28     445166    13025
29     113927     1001
30     552863     4272
31      84725      171
32     327089      705
33      28688       14
34     102880       39
35       4791        1
36      17626        1
37        369        0
38       1794        0
39         27        0
40        166        0
42          9        0
----------------------
      1957560    50781

For quarter turn symmetry:
Code: Select all
sz  s.minimal  minimal
----------------------
20         22       19
21          7        6
24      34659    13445
25       5104     1320
28     781678    21336
29      62887      709
32     838919     1466
33      32569       12
36      76256        6
37        921        0
40        665        0
44          1        0
----------------------
      1833688    38319

With my latest code, and using dobrichev's 'fsss2' solver, my times have improved:
    ~24 minutes for DD symmetry
    ~9 minutes for quarter turn
The switch to 'fsss2' gave a wonderful improvement. Thanks again, Mladen :!:
blue
 
Posts: 573
Joined: 11 March 2013

Re: Symmetrical Givens

Postby champagne » Sat May 30, 2015 8:46 pm

Hi blue,

I am convinced that you have the right count. Could you post you "R90" list for 20/21 clues to let me see where is the bug(s).

The code for the pi_stick is ready on my side for tests. Did you work on that?

I am not really surprised by your run time. On my side, the R90 search lasted about half an hour. for the DD symmetry, it was close to 3 hours.
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby champagne » Sat May 30, 2015 9:10 pm

blue wrote:BTW: your 12 symmetrically minimal 42's, contain only 9 ED puzzles.


can you tell which ones are morphs of the same ED puzzles, I have to check the canonical process to understand what happened
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby blue » Sat May 30, 2015 11:59 pm

champagne wrote:I am convinced that you have the right count. Could you post you "R90" list for 20/21 clues to let me see where is the bug(s).

The 20/21 clue list is here (19 + 6):
Hidden Text: Show
.......7.8.35........4...2....8.734...........259.6....4...2........35.6.9.......
.......8.9.5.7......3...24....4.3....8.....6....5.2....24...5......9.3.7.6.......
.......8.9.5.7......3...24....5.4....8.....6....2.3....24...5......9.3.7.6.......
.......8.9.57.......3...24.....3..6....4.2....8..5.....24...5.......93.7.6.......
.....7.8.9.3..........6..2.8...2......73.59......4...6.4..8..........5.7.6.9.....
.....7.8.9.3..5........6.2.827.....................946.4.8........3..5.7.6.9.....
.....8.9.6.....8...95...4..9..4.3...............5.2..7..2...37...6.....8.7.6.....
.....89.....7.....6.5...4..9..4.3.6...........8.5.2..7..2...3.8.....9.....76.....
.....97.......24..85...6...637.....................958...8...36..24.......97.....
....6......72.......5...46.....2..5.7..3.5..9.3..4.....82...3.......49......8....
....6.....37....2....4...6....5.43..7.......9..52.3....8...2....4....95.....8....
....6.8...5.....4.9..3........5.42..7.......9..42.3........5..7.2.....3...6.8....
....7..4.5.8.........8...7....3.27..8.......6..94.5....9...6.........6.3.2..9....
...67..4.5.8.............7....3.2..98.......67..4.5....9.............6.3.2..98...
..3....7.8....5.......9...2.2.7.6.....6...8.....8.9.4.4...7.......3....6.9....5..
..6........3..5.......7..29.2.9.8.....8...6.....6.7.4.74..9.......3..5........8..
..6........3.58..........29.9..8.....2.9.7.4.....6..7.74..........63.5........8..
2.....7.5..4..8...8......3..9..3.......4.2.......5..7..5......6...6..2..3.9.....4
2.....7.5..4..8...8......3..9..5.......2.4.......3..7..5......6...6..2..3.9.....4
.......8.9.5..7.....3...24..8..7.......816.......9..6..24...5.....9..3.7.6.......
.....8.9.65...3.4.....7....94.........8.1.6.........27....9.....2.5...38.7.6.....
.....89...5...3.4.6...9....94.........6.1.8.........27....7...8.2.5...3...76.....
..4....7.8..59............3...8.7.4..6..1..8..2.9.6...5............73..6.9....2..
.13........6.....1...4...92...8.73......1......59.6...47...2...1.....8........51.
2.....8.5..3..9...9......2..6.5.4.......1.......2.3.8..4......7...7..5..3.6.....4

champagne wrote:The code for the pi_stick is ready on my side for tests. Did you work on that?

Yes. It was a "long time" case with very few globally minimal puzzles -- 2320 possible solution grids, but only 62 minimal puzzles. I'm running it again, to count the symmetrically minimal puzzles. It looks like it will take ~11.5 hours to complete, and find 10-12 million ED symmetically minimal puzzles (which I'm discarding, but counting "by size").

champagne wrote:
blue wrote:BTW: your 12 symmetrically minimal 42's, contain only 9 ED puzzles.

can you tell which ones are morphs of the same ED puzzles, I have to check the canonical process to understand what happened

The first 3 pairs are isomorphic ... 1==2, 3==4, 5==6. The isomorphisms all swap r4c4 and r6c6 (1 row and 1 column swap).
blue
 
Posts: 573
Joined: 11 March 2013

Re: Symmetrical Givens

Postby champagne » Sun May 31, 2015 3:30 pm

hi blue,

2 bugs fixed with your help, but I am still missing some puzzles R90

3 clues count with a deviation for a total of 37940 ED puzzles on my side

Code: Select all
     you    me
24 13445 13354
28 21336 21065
32  1466  1449


I'll try to find why
champagne
2017 Supporter
 
Posts: 5678
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

Postby blue » Sun May 31, 2015 9:12 pm

blue wrote:
champagne wrote:The code for the pi_stick is ready on my side for tests. Did you work on that?

Yes. It was a "long time" case with very few globally minimal puzzles -- 2320 possible solution grids, but only 62 minimal puzzles. I'm running it again, to count the symmetrically minimal puzzles. It looks like it will take ~11.5 hours to complete, and find 10-12 million ED symmetically minimal puzzles (which I'm discarding, but counting "by size").

It took 16.4 hours ... much longer than my initial estimate. The results are below.
I'm surprised by the huge number of large symmetrically minimal puzzles.
That the long running time was likely on account of all of thier symmetric subset puzzles being tested.

Code: Select all
sz  s.minimal  minimal
----------------------
24         39       12
25          3        0
26        341        3
27         15        0
28       5748       24
29         58        1
30      36863        7
31        200        0
32     183242       14
33        352        0
34     727399        0
35        497        0
36    1632548        1
37        335        0
38    2624205        0
39        162        0
40    4036914        0
41         69        0
42     742102        0
44    1087702        0
46       2146        0
48       3443        0
----------------------
     11084383       62


Quarter turn puzzles for champagne - 1466 size 32
r90-32.zip
(31.11 KiB) Downloaded 89 times
blue
 
Posts: 573
Joined: 11 March 2013

PreviousNext

Return to General