Mike,
there is no diagonal (/) digit symmetry, the 3 is both in the diagonal, and pairs to the 7.
DDS implies 180 degree rotational (digit) symmetry (apply both diagonal reflections to get it).
Maybe the hardest sets are biased to (near) symmetric puzzles. In my own search i never used it, but ok, 1 fully symmetric in 26000 is not representative then.
Symmetrical Givens
Re: The hardest sudokus (new thread)
by eleven » Wed Apr 29, 2015 2:41 pm
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by m_b_metcalf » Thu Apr 30, 2015 9:02 am
eleven wrote:there is no diagonal (/) digit symmetry, the 3 is both in the diagonal, and pairs to the 7.
Thanks, you're right. Back to the drawing-board.
Mike
-
m_b_metcalf - 2017 Supporter
- Posts: 13624
- Joined: 15 May 2006
- Location: Berlin
Re: The hardest sudokus (new thread)
by Serg » Sat May 02, 2015 3:51 pm
Hi, all!
It's not true. Solution grid, having both diagonal and antidiagonal symmetry, was published by ravel on January 15, 2007 (see thread Gurth's Puzzles on this forum). Mauricio published puzzle, having both diagonal and antidiagonal symmetry among its clue values, on January 19, 2007 (see the same thread Gurth's Puzzles).
Serg
Serg wrote:... So, the only possible symmetry type - double diagonal, having both diagonal and antidiagonal symmetry was not presented yet by puzzles (solution grids), having clue value symmetry.
It's not true. Solution grid, having both diagonal and antidiagonal symmetry, was published by ravel on January 15, 2007 (see thread Gurth's Puzzles on this forum). Mauricio published puzzle, having both diagonal and antidiagonal symmetry among its clue values, on January 19, 2007 (see the same thread Gurth's Puzzles).
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: The hardest sudokus (new thread)
by eleven » Sat May 02, 2015 10:12 pm
DDS puzzles with digital (value) symmetry can be generated quickly. One more time I adopted dukusos suexg generator, where instead of one clue in each step i added (up to 4) symmetric clues.
Then in 3 minutes i could generate 10000 puzzles (minimal to symmetric clues), 980 of them were minimal.
More than half of them had an ER above 7, the hardest 9.9.
Below is a list with the 86 ER 9+ puzzles.
[Added: c-code]
Then in 3 minutes i could generate 10000 puzzles (minimal to symmetric clues), 980 of them were minimal.
More than half of them had an ER above 7, the hardest 9.9.
Below is a list with the 86 ER 9+ puzzles.
[Added: c-code]
Hidden Text: Show
- Attachments
-
suexDD.c- (6.51 KiB) Downloaded 169 times
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by blue » Sun May 03, 2015 1:04 am
You can generate all 50781 of them too, in a short time (~7 hrs).
They share only 152 solution grids (below).
Seven of them qualify for champagne's "potential hardest" list.
The largest ones were one each, with sizes 35 and one 36.
35 clues:
36 clues:
The smallest were size 20: ... 20 of them, and 21 at size 21
ED solution grids (152):
They share only 152 solution grids (below).
Seven of them qualify for champagne's "potential hardest" list.
- Code: Select all
.2.6....54....1.3...9......8...23.9....4.6....1.78...2......1...7.9....65....4.8. 10.5/10.5/9.8
.2......54....1.3...96.......81.3.9.....5.....1.7.92.......41...7.9....65......8. 10.5/10.5/9.8
1....4..3.9.8.......5.6.7...6...3..8..8...2..2..7...4...3.4.5.......2.1.7..6....9 10.5/10.5/10.3 (from above)
13.6....57.49......2...8...89..2.4.....4.6.....6.8..12...2...8......16.35....4.79 10.5/10.5/10.5
1....8.....867..3..6..4.5...8......4.32...87.6......2...5.6..4..7..342.....2....9 10.6/10.6/9.2
12.6.....49...7.....5.4....8..12..7...24.68...3..89..2....6.5.....3...16.....4.89 10.6/10.6/9.9
1..3...4..5......8....6.7..7..12......84.62......89..3..3.4....2......5..6...7..9 10.6/10.6/10.6
The largest ones were one each, with sizes 35 and one 36.
35 clues:
- Code: Select all
. . . . . . 2 . .
. . 4 2 6 . 9 3 .
. 2 . . 9 4 . 1 6
. 4 . . 2 . 8 . .
. 8 9 4 5 6 1 2 .
. . 2 . 8 . . 6 .
4 9 . 6 1 . . 8 .
. 7 1 . 4 8 6 . .
. . 8 . . . . . . ED=9.0/1.2/1.2
36 clues:
- Code: Select all
. . 2 9 . . . 6 .
. 9 . 6 4 . . 7 2
4 . . . 7 2 . . .
9 8 . . 2 . 6 . .
. 2 3 4 . 6 7 8 .
. . 4 . 8 . . 2 1
. . . 8 3 . . . 6
8 3 . . 6 4 . 1 .
. 4 . . . 1 8 . . ED=9.2/9.2/9.0
The smallest were size 20: ... 20 of them, and 21 at size 21
- Code: Select all
. . . . . . . . .
. 9 . . . 4 2 3 .
. . 1 . . 8 . 6 .
. . . . . 3 4 8 .
. . . . . . . . .
. 2 6 7 . . . . .
. 4 . 2 . . 9 . .
. 7 8 6 . . . 1 .
. . . . . . . . . ED=9.0/9.0/3.4
ED solution grids (152):
Hidden Text: Show
- blue
- Posts: 1045
- Joined: 11 March 2013
Re: The hardest sudokus (new thread)
by champagne » Sun May 03, 2015 3:10 am
blue wrote:You can generate all 50781 of them too, in a short time (~7 hrs).
They share only 152 solution grids (below).
Seven of them qualify for champagne's "potential hardest" list.
impressive work
I have on my side to go back to several sources of potential hardest to update my data base, what I'll put on the top of my to do list.
Could you tell a little more about the process applied to extract that exhaustive list??
whatever is the process, we all agree that the forced symmetry reduces dramatically the task, but I did not see how to cover all the field except finding all patterns having that symmetry.
- champagne
- 2017 Supporter
- Posts: 7455
- Joined: 02 August 2007
- Location: France Brittany
Re: The hardest sudokus (new thread)
by blue » Sun May 03, 2015 10:38 am
champagne wrote:Could you tell a little more about the process applied to extract that exhaustive list??
2nd part first ...
- To get from one of the 152 solution grids (grids with double diagonal symmetry), to the puzzles with double diagonal shape symmetry that have the grid as the solution ...
- 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 . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .- Sorted a list containing all of the bitmasks, by the size of puzzle that they would produce. The same list is used for each solution grid. Then for each solution grid, I did this ...
- Set up an array of 32M flags ... initially clear; one for each bitmask; indexed by the bitmask value ... "skip me" flags.
- Looped over the sorted array of bitmasks ... smallest to largest puzzle size, skiping the initial part with sizes <= 16, and shapes with the "skip me" flag set, and checking the rest for producing valid minimal puzzles.
- Each time a valid puzzle was found (minimal or not), I made sure that the "skip me" flags for each "superset" shape, got set (if they weren't already) -- since the corresponding puzzles would all be (valid, but) non-minimal.
With this routine, a call to "flag_supsesets(current_mask, 0)", does the job:- Code: Select all
void flag_supsesets(int mask, int bit)
{
for (; bit < 25; bit++)
{
if (mask & (1 << bit))
continue;
int mask2 = mask | (1 << bit);
if (flags[mask2])
continue;
skip[mask2] = true;
--remaining;
flag_supsesets(mask2, bit + 1);
}
}
- That reduced the number of puzzle to be tested, from 32M, to anywhere from 13 to 23 million -- not as much as I had hoped.
- Valid puzzles were checked for being isomorphs of earlier puzzles, and the ED puzzles were output.
Note that there are 2^25 (=32M) different shapes with double diagonal symmetry, and that they can be produced from a 25-bit bitmask representing the clues that are present in the 'x' cells below:
With that, if nothing else, you can produce the 32M double diagonal subgrids, and test each one for being a valid minimal puzzle.
To reduce the number of puzzles needing testing, I did this:
For the first part ... getting list of solution grids to test ... I did this:
- First, worked out that any solution grid with double diagonal symmetry, can be transformed into a superset of one of these 3 "seed" grids, using transformations that don't destroy double diagonal shape symmetry (for associated puzzles):
- Code: Select all
1 . . 5 . . . . 7
. 5 . . . . . 3 .
. . 9 . . . 5 . .
5 . . 1 2 3 . . .
. . . 4 5 6 . . .
. . . 7 8 9 . . 5
. . 5 . . . 1 . .
. 7 . . . . . 5 .
3 . . . . 5 . . 9- Code: Select all
1 . . . . 5 . . 7
. 5 . . . . . 3 .
. . 9 . . . 5 . .
. . . 1 2 3 . . 5
. . . 4 5 6 . . .
5 . . 7 8 9 . . .
. . 5 . . . 1 . .
. 7 . . . . . 5 .
3 . . 5 . . . . 9- Code: Select all
1 . . 5 . . . . 3
. 5 . . . . . 7 .
. . 9 . . . 5 . .
5 . . 1 2 3 . . .
. . . 4 5 6 . . .
. . . 7 8 9 . . 5
. . 5 . . . 1 . .
. 3 . . . . . 5 .
7 . . . . 5 . . 9
For each of those, I generated all of the ways of filling the empty cells, that are compatible with the double diagonal digital symmetry dictated by the values in the center box. The cells fill in (in 14 sets of 4 cells), using these rules:
- 1) across the main diagonal, 2's pair with 4's, 3's with 7's, 6's with 8's, and then 1's and 9's pair with themselves.
2) across the anti-diagonal, 1's pair with 9's, 2's with 6's, 4's with 8's, and then 3's and 7's pair with themselves.
For the 3 seed grids, there were 204 fills in total. To weed out cases that would produce isomorphic puzzle lists, I transformed them to a canonical form that was minlex with respect to transformations that
- 1) map the center square to itself, and preserve double diagnal "shape" symmetry (for puzzles).
2) remap the digits as necessary, to restore the (123)(456)(789) layout in the center box.
They're arranged with grids that have the highest number of (general) automorphisms first.
The top one is an isomorph of the MC grid.
- blue
- Posts: 1045
- Joined: 11 March 2013
Re: The hardest sudokus (new thread)
by champagne » Sun May 03, 2015 3:05 pm
blue wrote:Note that there are 2^25 (=32M) different shapes with double diagonal symmetry, and that they can be produced from a 25-bit bitmask representing the clues that are present in the 'x' cells below:
- 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 . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
With that, if nothing else, you can produce the 32M double diagonal subgrids, and test each one for being a valid minimal puzzle.
To reduce the number of puzzles needing testing, I did this:[list][*]Sorted a list containing all of the bitmasks, by the size of puzzle that they would produce. The same list is used for each solution grid. Then for each solution grid, I did this ...
[*]Set up an array of 32M flags ... initially clear; one for each bitmask; indexed by the bitmask value ... "skip me" flags.
[*]Looped over the sorted array of bitmasks ... smallest to largest puzzle size, skiping the initial part with sizes <= 16, and shapes with the "skip me" flag set, and checking the rest for producing valid minimal puzzles.
[*]Each time a valid puzzle was found (minimal or not), I made sure that the "skip me" flags for each "superset" shape, got set (if they weren't already) -- since the corresponding puzzles would all be (valid, but) non-minimal.
With this routine, a call to "flag_supsesets(current_mask, 0)", does the job:[code]void flag_supsesets(int mask, int bit)
very well done and the way you come to the 152 grids is very interesting.
I have one question about the valid pattern.
Unless I miss something, you can apply vertical symmetry and exchange of rows and columns to reduce the count and I don't see that in your text.
more or less, the vertical symmetry alone should halve the count.
Congratulations anyway.
It would be good to find somewhere the entire file of 50781 puzzles.
- champagne
- 2017 Supporter
- Posts: 7455
- Joined: 02 August 2007
- Location: France Brittany
Re: The hardest sudokus (new thread)
by dobrichev » Sun May 03, 2015 4:04 pm
blue wrote:You can generate all 50781 of them too...
Well done!
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: The hardest sudokus (new thread)
by eleven » Sun May 03, 2015 6:31 pm
blue, congratulation on another nice result.
I did not understand everything, e.g. how did you verify, that this cannot be a superset of a symmetrical solution?
Of course now i ask myself, if also the other 2 symmetries with 4 automorphisms, 90 degree rotational and 180 degree rotational combined with sticks symmetry could be searched exhaustively (but i would not expect high ratings there).
I did not understand everything, e.g. how did you verify, that this cannot be a superset of a symmetrical solution?
- Code: Select all
1 . . . . 5 . . 3
. 5 . . . . . 7 .
. . 9 . . . 5 . .
. . . 1 2 3 . . 5
. . . 4 5 6 . . .
5 . . 7 8 9 . . .
. . 5 . . . 1 . .
. 3 . . . . . 5 .
7 . . 5 . . . . 9
Of course now i ask myself, if also the other 2 symmetries with 4 automorphisms, 90 degree rotational and 180 degree rotational combined with sticks symmetry could be searched exhaustively (but i would not expect high ratings there).
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by Serg » Sun May 03, 2015 6:33 pm
Hi, eleven!
News are coming so soon on this subject ...
Impressive work! Did you use random generator? It is curious that you can generate so many puzzles (10000) during 3 minutes run only. But if you won't stop you generator after 3 minutes run - how many puzzles (minimal to symmetric clues) can it generate during, say, 1 hour (or several hours) running?
Serg
News are coming so soon on this subject ...
eleven wrote:DDS puzzles with digital (value) symmetry can be generated quickly. One more time I adopted dukusos suexg generator, where instead of one clue in each step i added (up to 4) symmetric clues.
Then in 3 minutes i could generate 10000 puzzles (minimal to symmetric clues), 980 of them were minimal.
Impressive work! Did you use random generator? It is curious that you can generate so many puzzles (10000) during 3 minutes run only. But if you won't stop you generator after 3 minutes run - how many puzzles (minimal to symmetric clues) can it generate during, say, 1 hour (or several hours) running?
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: The hardest sudokus (new thread)
by eleven » Sun May 03, 2015 6:47 pm
Serg,
i have attached the c-code (just 150 lines). It includes dukusos self-written random generator (and dancing links solver).
i have attached the c-code (just 150 lines). It includes dukusos self-written random generator (and dancing links solver).
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by Serg » Sun May 03, 2015 6:53 pm
Hi, blue!
Great work! Now we know about sudoku properties a little bit more...
I got aesthetic pleasure while seeing your 35/36/20-clue samples.
Do all 50781 puzzles are minimal in the sense that no clues can be deleted provided that remaining puzzle will have unique solution AND will still have diagonal and antidiagonal symmetries among its clue values? (eleven call such kind of minimality as "minimal to symmetric clues".)
Did you cross-checked your results with eleven's results?
It would be nice to get mathematically calculated number of dd-sym solution grids and dd-sym puzzles, but I have no ideas how to do it.
Anyway, your result is striking my fancy, congratulations!
It would be nice to see all 50781 puzzles list.
Serg
blue wrote:You can generate all 50781 of them too, in a short time (~7 hrs).
They share only 152 solution grids (below).
Great work! Now we know about sudoku properties a little bit more...
I got aesthetic pleasure while seeing your 35/36/20-clue samples.
Do all 50781 puzzles are minimal in the sense that no clues can be deleted provided that remaining puzzle will have unique solution AND will still have diagonal and antidiagonal symmetries among its clue values? (eleven call such kind of minimality as "minimal to symmetric clues".)
Did you cross-checked your results with eleven's results?
It would be nice to get mathematically calculated number of dd-sym solution grids and dd-sym puzzles, but I have no ideas how to do it.
Anyway, your result is striking my fancy, congratulations!
It would be nice to see all 50781 puzzles list.
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: The hardest sudokus (new thread)
by eleven » Sun May 03, 2015 7:53 pm
Serg wrote:Did you cross-checked your results with eleven's results?
I can confirm it in the sense, that i have the same solution grids in my 10000 set, as blue has published.
- eleven
- Posts: 3151
- Joined: 10 February 2008
Re: The hardest sudokus (new thread)
by blue » Sun May 03, 2015 9:34 pm
champagne wrote:It would be good to find somewhere the entire file of 50781 puzzles.
Serg wrote:It would be nice to see all 50781 puzzles list.
blue wrote:Here are the puzzles (I hope).
...
(remainder of post deleted)
Serg has been kind enough to host them for us.
Many many thanks ... much appreciated
Serg (in a later post) wrote:Hi, blue!blue wrote:Here are the puzzles (I hope).
...
Anyone else is welcome to download the files, combine them and share them via some other means.
Thanks for puzzles!
I uploaded them in the file "dd-raw.zip" (all 3 parts are concatenated) on my page: http://sites.google.com/site/sergsudoku/dd-raw.zip.
Serg
Last edited by blue on Mon May 04, 2015 9:18 pm, edited 1 time in total.
- blue
- Posts: 1045
- Joined: 11 March 2013
