Symmetrical Givens

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

Re: Symmetrical Givens

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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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: 3569
Joined: 03 June 2012

Re: Symmetrical Givens

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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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: 2075
Joined: 10 February 2008

Re: Symmetrical Givens

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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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: 2075
Joined: 10 February 2008

Re: Symmetrical Givens

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 . 67 . .   . . 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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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 . 77 . . . 9 . . . 55 . 8 . . . . 9 .. 8 . . 5 . . 7 .4 . . . . 3 1 . .. . . 2 . . . . .000001002000200030004050600009000076600090005540000900005060700010008000800300000. . . . . 1 . . 2. . . 2 . . . 3 .. . 4 . 5 . 6 . .. . 9 . . . . 7 66 . . . 9 . . . 55 4 . . . . 9 . .. . 5 . 6 . 7 . .. 1 . . . 8 . . .8 . . 3 . . . . .`
dobrichev
2016 Supporter

Posts: 1707
Joined: 24 May 2010

Re: Symmetrical Givens

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.785523.1.8..4.8.7.95.76..2..14....63...1348.2679...74....69..8..43.51.3.2.6..2.9.785123.9.8..4.8.7.15.76..2..94....47...9342.8671...36....61..8..43.59.3.2.6..2.1.789123.9.8..4.8.7.15.76..2..94....63...9348.2671...74....61..8..43.59.3.2.6..2.1.789523.6.81.4.8.3..5976..1...4....83...8716.4932...72....6...9..4315..7.2.6.92.4.785523.6.81.4.8.3..5976..1...4....27...8714.6932...38....6...9..4315..7.2.6.92.4.785523.1.8..4.8.7.95.76..2..14...16....1348.2679....49...69..8..43.51.3.2.6..2.9.785523.1.8..4.873.9..76..2..14.3..6....1748.2639....4..7.69..8..43..1.732.6..2.9.785523.1.8..4.873.1..76..2..94.3..6....1748.2639....4..7.61..8..43..9.732.6..2.9.78512637.9..4.7.9.6..83..4..217...8....3926.4817....2...398..6..72..4.1.3.6..1.3748913..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..7953..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       2021         25       2122       1678     102023       1372      60424      27594     794325      16127     238926     165920    1699527      64696     256028     445166    1302529     113927     100130     552863     427231      84725      17132     327089      70533      28688       1434     102880       3935       4791        136      17626        137        369        038       1794        039         27        040        166        042          9        0----------------------      1957560    50781`

For quarter turn symmetry:
Code: Select all
`sz  s.minimal  minimal----------------------20         22       1921          7        624      34659    1344525       5104     132028     781678    2133629      62887      70932     838919     146633      32569       1236      76256        637        921        040        665        044          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: 838
Joined: 11 March 2013

Re: Symmetrical Givens

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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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: 838
Joined: 11 March 2013

Re: Symmetrical Givens

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    me24 13445 1335428 21336 2106532  1466  1449`

I'll try to find why
champagne
2017 Supporter

Posts: 6949
Joined: 02 August 2007
Location: France Brittany

Re: Symmetrical Givens

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       1225          3        026        341        327         15        028       5748       2429         58        130      36863        731        200        032     183242       1433        352        034     727399        035        497        036    1632548        137        335        038    2624205        039        162        040    4036914        041         69        042     742102        044    1087702        046       2146        048       3443        0----------------------     11084383       62`

Quarter turn puzzles for champagne - 1466 size 32
r90-32.zip
blue

Posts: 838
Joined: 11 March 2013

PreviousNext