Symmetrical Givens

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

Re: The hardest sudokus (new thread)

Postby eleven » Wed Apr 29, 2015 2:41 pm

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.
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

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

Re: The hardest sudokus (new thread)

Postby Serg » Sat May 02, 2015 3:51 pm

Hi, all!
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
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: The hardest sudokus (new thread)

Postby 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]
Hidden Text: Show
9..5...4..1...3..2.....67..5.....83...........72.....5..34.....8..7...9..6...5..1 # 9.9 1.2 1.2
.4.......8.39......713.6....97.4.8.....8.2.....2.6.31....4.793......17.2.......6. # 9.9 1.2 1.2
..23....7....254..6....9.2.7.....15..6.....4..59.....3.8.1....4..658....3....78.. # 9.9 1.2 1.2
.439.....8.....1..7.1..3.9.9...8.3.....4.6.....7.2...1.1.7..9.3..9.....2.....176. # 9.8 1.2 1.2
.8..4....4..1.5.....5...3...1..2..5.8..6.4..2.5..8..9...7...5.....5.9..6....6..2. # 9.7 1.2 1.2
5..4......1.9.8.......2.7..89.....6...6...4...4.....12..3.8.......2.1.9......6..5 # 9.4 7.2 7.2
.76.2....3..9.....2.1..5....9...75..6.......4..53...1....5..9.8.....1..7....8.43. # 9.4 1.2 1.2
52.36....61.4..........8...78....6..2.......8..4....23...2..........6.94....47.85 # 9.3 9.3 2.6
...9..6.7.9..64......5.2..89.5...42..2.....8..86...5.12..8.5......64..1.3.4..1... # 9.3 1.2 1.2
..682.1.......3...2..4.1..94.8...93.6.......4.71...2.61..9.6..8...7.......9.824.. # 9.3 1.2 1.2
.3.1.....7.6.8.1...2.6.3.9.1.2...3...4.....6...7...8.9.1.7.4.8...9.2.4.3.....9.7. # 9.3 1.2 1.2
.....9.8...72.3..6.3.4......68....31.........97....24......6.7.4..7.83...2.1..... # 9.2 1.2 1.2
.78.3...53...41...4..8.......4....9.78.....23.1....6.......2..6...96...75...7.23. # 9.2 1.2 1.2
.7.8...1.3....74.9.....1.2.4.....97...........31.....6.8.9.....1.63....7.9...2.3. # 9.2 1.2 1.2
..7....6..5679...832...6....3..6.8...9.2.8.1...2.4..7....4...872...1345..4....3.. # 9.2 1.2 1.2
..73..14....9....23....8..979....6.............4....131..2....78....1....69..73.. # 9.2 1.2 1.2
.7.2...9.3.4..9..1.8...7...6.....71...........93.....4...3...2.9..1..6.7.1...8.3. # 9.2 1.2 1.2
.6.8.91..2....7......4....94.8....71.........93....2.61....6......3....8..91.2.4. # 9.2 1.2 1.2
.6.8.19..2....3......4....14.8....39.........17....2.69....6......7....8..19.2.4. # 9.2 1.2 1.2
...5....3..4..2....8941....5.8....4...1...9...6....2.5....9612....8..6..7....5... # 9.2 1.2 1.2
.27..1...6....3...3.15.......5.6..39...2.8...17..4.5.......59.7...7....4...9..38. # 9.2 1.2 1.2
.2.3.....6..9.21......46.9.79....84...8...2...62....13.1.46......98.1..4.....7.8. # 9.2 1.2 1.2
..4.67....5...81..8......9......3.672.......834.7......1......2..92...5....34.6.. # 9.1 9.1 6.6
......2.5.....963......6.84....2381....6.4....9278....62.4......741.....5.8...... # 9.1 9.1 2.6
..89...6....7...584...6.3..93.........2...8.........71..7.4...625...3....4...12.. # 9.1 2.6 2.6
...8..4...9...6.5....1.3..24.1...38...........27...9.68..7.9....5.4...1...6..2... # 9.1 2.0 2.0
9.8.1.......47....4.5..3....8....3..13.....79..7....2....7..5.6....36.......9.2.1 # 9.1 1.2 1.2
9.4.7.......2.5.7.8....9....6....15.3.......7.59....4....1....2.3.5.8.......3.6.1 # 9.1 1.2 1.2
......94..1.8....2..9.25..1.4.1.75....6...4....53.9.6.9..58.1..8....2.9..61...... # 9.1 1.2 1.2
9.3.7..4....34...27....6....7....8..38.....27..2....3....4....38...67....6..3.7.1 # 9.1 1.2 1.2
...9...17..4..3..9.8.......9...2..3....6.4....7..8...1.......2.1..7..6..39...1... # 9.1 1.2 1.2
.8.......4.671.....21..4....3..4.2...1.8.2.9...8.6..7....6..98.....934.6.......2. # 9.1 1.2 1.2
..8...41....4....94...173.2.8..6.7....12.89....3.4..2.8.739...61....6....96...2.. # 9.1 1.2 1.2
.82.3....4..6...5.6..9.8....29...6..7.......3..4...18....2.1..4.5...4..6....7.82. # 9.1 1.2 1.2
..75...8.......1.63....7.9.5...4.7.....8.2.....3.6...5.1.3....74.9.......2...53.. # 9.1 1.2 1.2
.74.....33...29.5.8............4..1..6.8.2.4..9..6............2.5.18...77.....63. # 9.1 1.2 1.2
.7.......35.84.2......95.4..4....5...89...12...5....6..6.51......8.62.57.......3. # 9.1 1.2 1.2
.......6.....139.8...5..31...5.2..3..1.6.4.9..7..8.5...97..5...2.179.....4....... # 9.1 1.2 1.2
...5....7.....81......73.9.5...8.36...34.67...47.2...5.1.73......92.....3....5... # 9.1 1.2 1.2
5.....2.3...8.........15..4.4.96.5....12.89....5.41.6.6..59.........2...7.8.....5 # 9.1 1.2 1.2
.47......8....59..3..9...1...9.6..5....2.8....5..4.1...9...1..7..15....2......36. # 9.1 1.2 1.2
..45...1...7..1..983.......5...8..9....4.6....1..2...5.......721..9..3...9...56.. # 9.1 1.2 1.2
.....429....8.9.71......3.4.4...3.12.........89.7...6.6.7......93.1.2....186..... # 9.1 1.2 1.2
..2.9.6.....4...5.6....17.8.8....9..9.......1..1....2.2.39....4.5...6.....4.1.8.. # 9.1 1.2 1.2
.2.7..4.36.3.......7...9..23...8.1.....4.6.....9.2...78..1...3.......7.47.6..3.8. # 9.1 1.2 1.2
..26....5....2.1..6.57...9.2.3.......6.....4.......7.8.1...35.4..9.8....5....48.. # 9.1 1.2 1.2
1.79..8.......8...3...7.5.69......6...3...7...4......14.5.3...7...2.......2..13.9 # 9.1 1.2 1.2
...3..9...5.8...7.....24..174.1..2....6...4....8..9.639..68.....3...2.5...1..7... # 9.0 9.0 8.9
..864.........2...4.531....2.7....4.8.1...9.2.6....3.8....975.6...8.........642.. # 9.0 9.0 2.6
...4....7.9....8....13.2.6.8.7...4......5......6...3.2.4.8.79....2....1.3....6... # 9.0 2.3 2.3
.....32...96.......2.61.7.4..2.....3..1...9..7.....8..6.3.94.8.......41...87..... # 9.0 2.3 2.3
....9..2....3..9.4....8431..7...32..9.4...6.1..87...3..9762....6.1..7....8..1.... # 9.0 1.2 1.2
...8..9....25...7..6.3....1457.....................3569....7.4..3...58....1..2... # 9.0 1.2 1.2
..8........37.14..47..9..2..3..4..9...98.21...1..6..7..8..1..36..69.37........2.. # 9.0 1.2 1.2
.8.3..49.4....2.31...5....27.5....4...........6....5.38....5...97.8....6.16..7.2. # 9.0 1.2 1.2
...81...3.....917.....34.9.4.....21.1.7...3.9.98.....6.1.67.....391.....7...92... # 9.0 1.2 1.2
.....7.6...75....8.3.816....54...8.7..1...9..3.2...65....492.7.2....53...4.3..... # 9.0 1.2 1.2
.7.6.....3.8.2.....4..31...2....79...67...34...13....8...97..6.....8.2.7.....4.3. # 9.0 1.2 1.2
.74......3....9...8.571......3.6..1...12.89...9..4.7......935.2...1....7......63. # 9.0 1.2 1.2
....6..8..18..9..6.4...3.......2.31.2..6.4..8.97.8.......7...6.4..1..29..2..4.... # 9.0 1.2 1.2
.68..1...2.34..8..47.8.3.6..84...3.9.........1.7...62..4.7.2.36..2..67.8...9..24. # 9.0 1.2 1.2
..67..9......95...2..6....13.2....5..9.....1..5....8.79....4..8...51......1..34.. # 9.0 1.2 1.2
...6.7.9.....3.8.1..5..8.6.2..9..6.7.7.....3.3.4..1..8.4.2..5..9.2.7.....1.3.4... # 9.0 1.2 1.2
..67..1......15...2..6....93.2....5..1.....9..5....8.71....4..8...59......9..34.. # 9.0 1.2 1.2
.......63...24.1.8...1..79..61.......8.....2.......94..13..9...2.9.68...74....... # 9.0 1.2 1.2
...61..8...2..9..6.6.8..7..2.4....1.1.......9.9....6.8..3..2.4.4..1..8...2..94... # 9.0 1.2 1.2
...5.6.9...8.....1.4.1..7..5.1..3..8.........2..7..9.5..3..9.6.9.....2...1.4.5... # 9.0 1.2 1.2
5...6.1.....7..4.....4.8.29.38...6..2.......8..4...27.18.2.6.....6..3.....9.4...5 # 9.0 1.2 1.2
5..49.........297.....8..1.8......4.9.4...6.1.6......2.9..2.....318.........16..5 # 9.0 1.2 1.2
5.4..7.9...74....183........8.92...7...6.4...3...81.2........729....63...1.3..6.5 # 9.0 1.2 1.2
53.6.....7.2..5....6.17....2.1....5...3...7...5....9.8....39.4....5..8.3.....4.75 # 9.0 1.2 1.2
52.3....76..2.........95...76....5....9...1....5....43...51.........8..43....7.85 # 9.0 1.2 1.2
..49......5..1..3.8...37...9...8.7...174.639...3.2...1...37...2.7..9..5......16.. # 9.0 1.2 1.2
.....489....7..231...1...46.31.....2.........8.....97.46...9...978..3....126..... # 9.0 1.2 1.2
.4.......8...716.......5.8.....8.59..3.4.6.7..15.2.....2.5.......493...2.......6. # 9.0 1.2 1.2
.4...12..8...3..........5.4....2...9.7.6.4.3.1...8....6.5..........7...2..89...6. # 9.0 1.2 1.2
..3.8.....94.71...78.6.......2....9.43.....76.1....8.......4.23...93.61.....2.7.. # 9.0 1.2 1.2
.3..86.2.7.63....4.2.9......79.....84.......62.....13......1.8.6....74.3.8.42..7. # 9.0 1.2 1.2
.....361...7..8..9.3......8....8..63...456...74..2....2......7.1..2..3...947..... # 9.0 1.2 1.2
....3..4......78.2..589..6...4....7.7.9...1.3.3....6...4..125..8.23......6..7.... # 9.0 1.2 1.2
...3..28..5..1...6....72..47.....4...13...79...6.....36..83....4...9..5..28..7... # 9.0 1.2 1.2
..2....97....76..16.1..........23.8..3.654.7..2.78..........9.49..43....31....8.. # 9.0 1.2 1.2
..2..91.7...3..2..6......49.7..83..1...4.6...9..72..3.16......4..8..7...3.91..8.. # 9.0 1.2 1.2
.27..3...6....9...3..54.7....5....13..8...2..79....5....3.65..7...1....4...7..38. # 9.0 1.2 1.2
......2.5..6.7.....2.1....4..1.6.....3.2.8.7.....4.9..6....9.8.....3.4..5.8...... # 9.0 1.2 1.2
..2....1.....76.596..9.......9..3.8..3.....7..2.7..1.......1..415.43.....9....8.. # 9.0 1.2 1.2
Attachments
suexDD.c
(6.51 KiB) Downloaded 34 times
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby 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.

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
Code: Select all
123645897456978231789312564897123645231456978564789312645897123978231456312564789
123647895456938271789512364895123647271456938364789512647895123938271456512364789
123564897456897231789231564564123978897456312231789645645978123978312456312645789
138564927754912836629378541597123468813456792246789315965237184472891653381645279
123548967456917832789632541598123674217456398634789215965874123872391456341265789
146937285293865174875214396964123857781456923352789641417698532639542718528371469
126378945497512638835964721759123864318456297642789153983641572274895316561237489
128935467493867152675214398964123875781456923532789641217698534859342716346571289
126574893497368251835912764579123648381456927264789135643891572958247316712635489
138592647752641938649378512587123496923456781416789325895237164271964853364815279
126374895493568271875912364759123648381456927264789153647891532938245716512637489
138564927752918436649372581597123648813456792264789315925837164476291853381645279
123645897496837251785291364864123975279456138531789642647918523958372416312564789
123645897456897231789231564864123975297456318531789642645978123978312456312564789
138297645792645138645831792486123957927456381351789426813972564279564813564318279
136897245792645138845231796684123957927456381351789624413978562279564813568312479
123645897458297631769831524846123975297456318531789462685972143974318256312564789
123645897498237651765891324846123975279456138531789462687912543954378216312564789
123645897496378251785912364879123645231456978564789132647891523958237416312564789
138564927752891436649237581564123798897456312213789645925378164476912853381645279
138564927792831456645297381564123798879456132213789645927318564456972813381645279
123645897458972631769318524897123465231456978546789312685297143974831256312564789
136978245792645138845312796987123654321456987654789321413897562279564813568231479
138564927754291836629837541546123798897456312213789465965372184472918653381645279
123645897498372651765918324879123465231456978546789132687291543954837216312564789
123564897496378251785912364579123648831456972264789135647891523958237416312645789
138645927752891436649237581864123795297456318513789642925378164476912853381564279
138645927792831456645297381864123795279456138513789642927318564456972813381564279
123564897456978231789312564597123648831456972264789315645897123978231456312645789
123564897458972631769318524597123468831456972246789315685297143974831256312645789
136978245792564138845312796957123684381456927624789351413897562279645813568231479
138645927754291836629837541846123795297456318513789462965372184472918653381564279
123564897498372651765918324579123468831456972246789135687291543954837216312645789
138645927752918436649372581897123645213456798564789312925837164476291853381564279
123564897496837251785291364564123978879456132231789645647918523958372416312645789
138297645792564138645831792456123987987456321321789456813972564279645813564318279
136897245792564138845231796654123987987456321321789654413978562279645813568312479
123564897458297631769831524546123978897456312231789465685972143974318256312645789
123564897498237651765891324546123978879456132231789465687912543954378216312645789
138645927754912836629378541897123465213456798546789312965237184472891653381564279
128574693497362851635918742579123468381456927246789135863291574952847316714635289
128635947457291638639847521846123795792456813513789462985362174274918356361574289
134697825758241936269835714846123597927456381315789462693572148471968253582314679
128374695457962831639518742795123468381456927246789513863295174972841356514637289
128374695497562831635918742759123468381456927246789153863291574972845316514637289
128637945457291638639845721846123597792456813315789462983562174274918356561374289
126835947457691238839247561684123795792456813513789624945368172278914356361572489
126837945457691238839245761684123597792456813315789624943568172278914356561372489
123568497498372651765914328579123864831456972642789135287691543954837216316245789
136845927794231856825697341648123795279456138513789264967314582452978613381562479
127368495458972631369514728795123864831456972642789513283695147974831256516247389
123568497458972631769314528597123864831456972642789315285697143974831256316245789
138297645752641938649835712486123597927456381315789426893572164271964853564318279
138295647752641938649837512486123795927456381513789426895372164271964853364518279
127645893496837251385291764864123975279456138531789642643918527958372416712564389
123647895496835271785291364864123957279456138351789642647918523938572416512364789
123847695496235871785691342648123957279456138351789264867914523932578416514362789
123895467498637152765241398684123975972456831531789624217968543859374216346512789
123897465498635172765241398684123957972456831351789624217968543839574216546312789
123845697496237851785691342648123975279456138531789264867914523952378416314562789
138695427752841936649237518864123795927456381513789642295378164471962853386514279
127845693496237851385691742648123975279456138531789264863914527952378416714562389
134568927758912436269374581597123864813456792642789315925637148476891253381245679
123845697456297831789631542648123975297456318531789264865974123972318456314562789
127895463458631972369247518684123795972456831513789624295368147831974256746512389
123897465458631972769245318684123597972456831315789624297568143831974256546312789
123897645496235178785641392648123957972456831351789264817964523239578416564312789
123895647496237158785641392648123975972456831531789264817964523259378416364512789
127564893496378251385912764579123648831456972264789135643891527958237416712645389
127895643496237158385641792648123975972456831531789264813964527259378416764512389
126538947493617258875942361589123674712456893634789125947861532258394716361275489
147265893258934671369817524496123785871456932523789416685392147934671258712548369
126378945457691238839542761785123694392456817614789523943865172278914356561237489
128374695497265831635891742746123958389456127251789463863912574972548316514637289
126378945497615238835942761789123654312456897654789123943861572278594316561237489
147265893258394671369871524476123985893456712521789436685932147934617258712548369
123865497498237651765914328649123875871456932532789164287691543954378216316542789
128637945457912638639548721895123467712456893346789512983265174274891356561374289
126378945493615278875942361789123654312456897654789123947861532238594716561237489
128675943497312658635948721879123465312456897546789132983261574254897316761534289
123867495498235671765914328649123857871456932352789164287691543934578216516342789
128637945497512638635948721859123467712456893346789152983261574274895316561374289
127865943496371258385294761674123895839456172512789634943618527258937416761542389
128937645497265138635814792946123857781456923352789461813692574279548316564371289
127638945456917238389542761895123674712456893634789512943865127278391456561274389
127638945496517238385942761859123674712456893634789152943861527278395416561274389
123867945496531278785294361654123897879456132312789654947618523238975416561342789
123678945456391278789542361875123694392456817614789532947865123238917456561234789
128937645457612938639548712985123467712456893346789521893265174271894356564371289
128395647457261938639874512746123895983456721512789463895632174271948356364517289
136548297794632851825917346589123764271456938643789125467391582952874613318265479
123678945496315278785942361879123654312456897654789132947861523238597416561234789
123865947496371258785294361674123895839456172512789634947618523258937416361542789
126547893497638251835912764589123647271456938364789125643891572958274316712365489
123945867496378152785612394978123645231456978564789231617894523859237416342561789
138672945792541638645398721857123496329456187416789352983217564274965813561834279
127834695456297831389561742645123978798456213231789564863945127972318456514672389
138965427752814936649237518964123785817456392523789641295378164471692853386541279
127945863496378152385612794978123645231456978564789231613894527859237416742561389
123947865496538172785612394958123647271456938364789251617894523839275416542361789
127895463458361972369274518674123895983456721512789634295638147831947256746512389
123647895496538271785912364859123647271456938364789152647891523938275416512364789
127645893496378251385912764879123645231456978564789132643891527958237416712564389
126875943497361258835294761674123895389456127512789634943618572258947316761532489
134967825758214936269835714946123587817456392325789461693572148471698253582341679
128365947457291638639874521746123895893456712512789463985632174274918356361547289
126837945493561278875294361654123897789456123312789654947618532238945716561372489
128547693497632851635918742589123467271456938346789125863291574952874316714365289
126837945497561238835294761654123897789456123312789654943618572278945316561372489
128567943497231658635894721546123897879456132312789465983612574254978316761345289
123678495458392671769541328875123964392456817641789532287965143934817256516234789
127348965496571832385692741758123694239456178614789253963814527872935416541267389
127548963496371852385692741578123694239456178614789235963814527852937416741265389
128937465453618972679542318985123647712456893364789521297865134831294756546371289
128975463453618972679342518987123645312456897564789321295867134831294756746531289
127548963456391872389672541578123694293456718614789235965834127832917456741265389
123548967496371852785692341578123694239456178614789235967814523852937416341265789
128937465493865172675214398964123857781456923352789641217698534839542716546371289
128597463453861972679234518564123897987456321312789645295678134831942756746315289
146937825293548176875612394958123647721456983364789251617894532439265718582371469
134678295796542831285391746857123964329456187641789352463917528972865413518234679
138267945752914638649835721496123587817456392325789416983572164274691853561348279
127348695496572831385691742758123964239456178641789253863914527972835416514267389
127348695456972831389615742798123564231456978645789213863594127972831456514267389
134865927758291436269374581647123895893456712512789364925637148476918253381542679
127548693496372851385691742578123964239456178641789235863914527952837416714265389
127594863496837152385261794564123978978456231231789645613948527859372416742615389
126374895493865271875291364764123958389456127251789643647918532938542716512637489
123548697496372851785691342578123964239456178641789235867914523952837416314265789
123594867496837152785261394564123978978456231231789645617948523859372416342615789
123598467458671932769342518587123694932456871614789325295867143871934256346215789
127394865456871932389265714764123598938456271215789643693548127871932456542617389
127548693456392871389671542578123964293456718641789235865934127932817456714265389
127398645496572138385641792758123964932456871641789253813964527279835416564217389
127598643496372158385641792578123964932456871641789235813964527259837416764215389
127564893496837251385291764564123978879456132231789645643918527958372416712645389
123598647496372158785641392578123964932456871641789235817964523259837416364215789
127364895458972631369518724795123468831456972246789513683295147974831256512647389
126837945457291638839645721648123597792456813315789264983564172274918356561372489
126835947457291638839647521648123795792456813513789264985364172274918356361572489
138647925754291836629835741846123597297456318315789462963572184472918653581364279
123647895498235671765891324846123957279456138351789462687912543934578216512364789
126578943497312658835964721579123864318456297642789135983641572254897316761235489
126378945457912638839564721795123864318456297642789513983645172274891356561237489
126538947457912638839647521598123764712456893643789215985364172274891356361275489
138647925754912836629538741895123467217456398346789512963275184472891653581364279
136895247792364158845271396674123985983456721521789634417938562259647813368512479
126378945457912638839645721798123564312456897645789213983564172274891356561237489
126837945497215638835964721649123857718456293352789164983641572274598316561372489
123647895498532671765918324859123467271456938346789152687291543934875216512364789
123647895458932671769518324895123467271456938346789512687295143934871256512364789
126837945457291638839564721645123897798456213312789564983645172274918356561372489
blue
 
Posts: 573
Joined: 11 March 2013

Re: The hardest sudokus (new thread)

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

Re: The hardest sudokus (new thread)

Postby 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 ...

    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:
    • 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.

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.
    It turns out if a value that can be placed in one of empty cells without causing a "line of sight" conflict, then its (3) companion cells can also be filled in without conflict.

    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.
    The result was the list of 152 grids.
    They're arranged with grids that have the highest number of (general) automorphisms first.
    The top one is an isomorph of the MC grid.
Using those solution grids in the "puzzle producing" process above, 2,761,053,790 "potential puzzles" were tested, resulting in 2,134,808 valid puzzles, of which 59034 were minimal. That dropped to 50781 after removing isomorphs. The isomorphs were due to 32 of the solution grids having 8 automorphisms that preserve double diagonal shape symmetry, rather than the usual 4 -- grids #1,3,4,12-40.
blue
 
Posts: 573
Joined: 11 March 2013

Re: The hardest sudokus (new thread)

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

Re: The hardest sudokus (new thread)

Postby dobrichev » Sun May 03, 2015 4:04 pm

blue wrote:You can generate all 50781 of them too...

Well done!
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: The hardest sudokus (new thread)

Postby 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?
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: 1564
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby Serg » Sun May 03, 2015 6:33 pm

Hi, eleven!
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
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: The hardest sudokus (new thread)

Postby 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).
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby Serg » Sun May 03, 2015 6:53 pm

Hi, blue!
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
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: The hardest sudokus (new thread)

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

Re: The hardest sudokus (new thread)

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

PreviousNext

Return to General