The New Sudoku Players' Forum

[ronk]

this

Code: Select all

1.3..6789..7..9..6.......1.2.196..75..85.19.2..5.28.613.28.56975..6.....7...92.5.

tends to spoil the puzzle for people wishing to solve it (notice row 1)

prefer this --

Code: Select all

12345.6..56.7.142...46..5..21786.3...3.1..862.........35.....4.7.154.23..42...7.5

This looks like the method used by eleven. Where is this method defined?

[RW]

this

Code: Select all

1.3..6789..7..9..6.......1.2.196..75..85.19.2..5.28.613.28.56975..6.....7...92.5.

tends to spoil the puzzle for people wishing to solve it (notice row 1)

prefer this --

Code: Select all

12345.6..56.7.142...46..5..21786.3...3.1..862.........35.....4.7.154.23..42...7.5

This looks like the method used by eleven. Where is this method defined?

If I recall correctly it was Ocean who started using this method in the original hardest thread. Already his first puzzles in that thread (on page 2) are sorted like this. I think he mentioned some more specific details about his system somewhere in the thread, but it is too long for me to search for that post now.

RW

[daj95376]

this

Code: Select all

1.3..6789..7..9..6.......1.2.196..75..85.19.2..5.28.613.28.56975..6.....7...92.5.

tends to spoil the puzzle for people wishing to solve it (notice row 1)

prefer this --

Code: Select all

12345.6..56.7.142...46..5..21786.3...3.1..862.........35.....4.7.154.23..42...7.5

This looks like the method used by eleven. Where is this method defined?

This probably has nothing to do with what you want, but I found it interesting that it appeared so soon after your query.

... it is excedingly quick to minlex a puzzle to its minimum template and then to its minimum relabelled clues.

http://www.setbb.com/sudoku/viewtopic.php?p=13281

Regards, Danny

[coloin]

Although I think eleven is maxlexing the pattern but minlexing the numbers.

Making it easier to collate the increasing number of 39 puzzles.

Congrats on dobrichev in making/finding these furthur four

A newer method ?

C

[dobrichev]

Here are new 23 minimal 39s.

Code: Select all

...5...3.5....18.7.837.4.153684.7.2....2.6783..........32..51..8.16...5265.1.2378
.4.25.931.........39514.....3..8....5.97...8.87.52.3.9..78..4.348..1.79.95347..18
.25..9.87..9.5.....7.2....95..1.2.93.31......298.35.41..2.73.1..1352..7875.8.1.3.
43.6.298...7...6.4.8647.23..69.4...874...63..3.82..4.6.9.72.8.3.........8739..1.2
9.14..6.323...69...67.3...1..2...3.631.6.479..9632.41..........1297..8.4.7.24.1.9
..41.5..86...78.5.5.846.9..4.6..719.9..6417............675.48.98.5.1....349.8651.
645.8.72.7.1.256.8.82.......67.345....3.5...7.5.....6.3.6..28.4.7...823..28.43.76
......52...52.17347.2.548.16.341.25.2...351.65..6.2.4.3.6..741....1...7...7.4.6..
4.927.1.318.39..42....14.8...4.3.8.1.1...2.749...41326.........7....923889..23..7
4...5...1..5...8..1.834..5.84.7...636.743.198..16..47.583.6.71.7.6.......1.57..86
12.65483.8..1.36..3...28.51.7..6..1.21...756....5..7..73..86..5.8.3.5276......38.
....8..6.8.436.5.25.64...83..5.43.98.4819..359.........5.91...66.9..4..14.163..59
.4.2.7..5.2..6.74..764.528..126...58.....2....6815.42..817.65..69.5.187...7....1.
73.8.9.56..6....8.89.5.63..2.395..78.8......29.72.8.3.6...95.233791.2.65...6.....
5.32.197.........591.7.5.2..9.3...563.56..7..1.65.7.396.147..922....6.....91.2.67
.674.915...5.1746..1..6..........8..75..84.1..82.71.45.26..8..45....268..78.4652.
.429..3..9...4..5.53....49.17..9..23.257..91.3.921.57...........5316.74...642.135
84..72.939...81427..........37.6.91.6.9.13.7441...7.36..6.2..4..94....6212...6..9
....74.3..6.83.24.34.6.28.747.96..28.9628.47.............3.....91.7.638.63..1879.
.729.3.5.3.5.12.9791.7......5312..89.283.951..........26.8.1.755.12.7.68..7......
.2654397...57...6.97..263......8....25..3489..982.5.3..62....8.589.6.7.37...5.6..
192.6785...8.2.6..76.5.8.1.6..254.81....764..2..8...6.91.7.254.4.........27.451..
...8.4.2.2.4.9786.98..2....4.9.7538.3.59.8...87..435..6.37.92..79.45263..........


My list of known 39-s consists of

• 2 puzzles by Havard published here (referenced in the initial post of this thread)
• 80 puzzles by Eleven published here (at the beginning of this thread, as of September, 14 2010)
• 4 puzzles by Dobrichev published here (above in this thread)
• 23 puzzles by Dobrichev (in this post)

Total: 109 known 39s

Are there more published 39s?
If there are, some or all of the new 4+23 39s could be duplicates.

MD

[dobrichev]

A newer method ?

A new method based on old discoveries.

Read this eleven's post which is referencing RW.

So, what I did took 30 minutes coding, 1 second execution, and several hours verification.
1) get a valid puzzle.
2) find its unique solution.
3) create a complementary puzzle by reverting the givens, i.e. in the solution grid erase all givens and leave all non-givens.
4) solve the complementary puzzle and store all solutions.
5) for each solution replace the given values in the original puzzle with the respective values from the solution.
6) repeat for all known puzzles in the family.
7) remove duplicates.

In other words, find the puzzles isomorphic to the existing ones by permuting the values in the unavoidable sets which lie entirely in the puzzle givens.

Reconsidering the "essentially different puzzle" definition would cut off 69 of the first 82 39s + all mines, resulting in only 13 "different" 39s.

For 17s collection there are 96 isomorphs in this sense, all in the Gordon's list. Seems this processing has been done before (and therefore this is not a new method). It took 10 seconds.

Nevertheless this check will speed up the new 39s discovering process - at least by enlarging (or truncating) the seed collections of 37s and 38s.
I kept eleven's collection of 38s published just before the old forum crash. It has 31348 38s. A pass checking for UA isomorphs found 11054 "new" puzzles (320"), and 16286 isomorphs within existing 38s.

MD

[Pat]

I kept eleven's collection of 38s
published just before the old forum crash.
It has 31,348 38s---

eleven's update (2010.May.23)
has 41,261 38s

(can be found on my Multiply)[ edit: no, sorry, service discontinued!! ]

[coloin]

.......In other words, find the puzzles isomorphic to the existing ones by permuting the values in the unavoidable sets which lie entirely in the puzzle givens.

I see now - so if the complementary puzzle has > 1 sol - there is a complete unavoidable set amonst the givens

[and 17s are unlikely to have a complete unavoidable within the 17 given clues.]

As i am sure everybody knows - minimality is the inherent promblem with 39s. [As opposed to a requirement for a unique solution with 17s]

Analysing the "search for a 39/40" as an "unavoidable set problem"

taking a single solution grid -
one can ignore all unavoidable sets with over 41 clues [these will always be covered]
finding unavoidable sets [of sise 4- ? 36]
each unavoidable has a single clue from each given clue plus a variable number of clues only from the non-givens

but we dont as yet have any good way of finding for definite the maximum size puzzle in any one grid [ as in the 17s]

perhaps take a 36 clue unavoidable from a solution grid
take 1 clue from each clue in the unavoidable
add this to the converse of the unavoidable set
you will have 36 different puzzles with 46s clue each

analying these puzzles for essential clues ? , or average minimal puzzle puzzle size [what i used to do] - or something more clever ?

C

[coloin]

Code: Select all

+---+---+---+
|...|8.4|.2.|
|2.4|.97|86.|
|98.|.2.|...|
+---+---+---+
|4.9|.75|38.|
|3.5|9.8|...|
|87.|.43|5..|
+---+---+---+
|6.3|7.9|2..|
|79.|452|63.|
|...|...|...|
+---+---+---+  39 puzzle from dobrichev [above]

...8.4.2.2.4.9786.98..2....4.9.7538.3.59.8...87..435..6.37.92..79.45263..........  39-puzzle ****
156834927234197865987526143419275386365918472872643519643789251791452638528361794  solution

156.3.9.7.3.1....5..75.6143.1.2....6......47...26...19.......51..14....8528361794   38 clue unavoidable set 

Heres a set of puzzles with 44 clues
With the 38 clue unavoidable set - one clue from the set completes the puzzle

no - number of obligatory clues in puzzle
average - average puzzle size generated by random removal [we know this is skewed to pick smaller puzzles]
number of 34+s per 5000
number of 35+s per 20000

Code: Select all

                                                                                 # no # avege #34s#35s#
1..8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 11 # 26.93 #  1#   
.5.8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 12 # 27.64 #  1#   
..68.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 06 # 27.95 #  1#   
...834.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 07 # 27.16 #  0#   
...8.492.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 10 # 27.45 #  1#   
...8.4.272.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 06 # 27.39 #  1#   
...8.4.2.234.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 11 # 28.23 #  5#   
...8.4.2.2.419786.98..2....4.9.7538.365918..287..435..6437892..79..5263..........# 07 # 27.51 #  0#   
...8.4.2.2.4.9786598..2....4.9.7538.365918..287..435..6437892..79..5263..........# 08 # 27.29 #  0#   
...8.4.2.2.4.9786.987.2....4.9.7538.365918..287..435..6437892..79..5263..........# 06 # 27.50 #  4#   
...8.4.2.2.4.9786.98.52....4.9.7538.365918..287..435..6437892..79..5263..........# 11 # 27.37 #  3#   
...8.4.2.2.4.9786.98..26...4.9.7538.365918..287..435..6437892..79..5263..........# 06 # 27.67 #  0#   
...8.4.2.2.4.9786.98..2.1..4.9.7538.365918..287..435..6437892..79..5263..........# 07 # 26.54 #  0#   
...8.4.2.2.4.9786.98..2..4.4.9.7538.365918..287..435..6437892..79..5263..........# 10 # 26.57 #  4#   
...8.4.2.2.4.9786.98..2...34.9.7538.365918..287..435..6437892..79..5263..........# 10 # 27.96 #  2#   
...8.4.2.2.4.9786.98..2....419.7538.365918..287..435..6437892..79..5263..........# 12 # 27.00 #  0#       
...8.4.2.2.4.9786.98..2....4.927538.365918..287..435..6437892..79..5263..........# 11 # 27.11 #  0#       
...8.4.2.2.4.9786.98..2....4.9.75386365918..287..435..6437892..79..5263..........# 11 # 27.00 #  0#       
...8.4.2.2.4.9786.98..2....4.9.7538.3659184.287..435..6437892..79..5263..........# 14 # 28.83 #  8#  9#       
...8.4.2.2.4.9786.98..2....4.9.7538.365918.7287..435..6437892..79..5263..........# 14 # 29.04 #  1#  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..2872.435..6437892..79..5263..........# 11 # 27.25 #  0#       
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287.6435..6437892..79..5263..........# 10 # 26.72 #  0#       
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..4351.6437892..79..5263..........# 10 # 26.45 #  0#       
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435.96437892..79..5263..........# 10 # 26.58 #  2#       
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..64378925.79..5263..........# 11 # 28.20 # 10#  7#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892.179..5263..........# 09 # 26.53 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..791.5263..........# 12 # 26.13 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79.45263..........# 11 # 28.38 # 10# 10# ***** 39 in this one   
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..52638.........# 12 # 27.65 #  2#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263.5........# 12 # 27.88 #  2#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263..2.......# 11 # 26.45 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263...8......# 10 # 26.55 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263....3.....# 06 # 27.61 #  1#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263.....6....# 07 # 27.45 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263......1...# 07 # 27.39 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263.......7..# 08 # 26.99 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263........9.# 10 # 25.92 #  0#     
...8.4.2.2.4.9786.98..2....4.9.7538.365918..287..435..6437892..79..5263.........4# 10 # 27.39 #  0#

So not very helpful

Maybe a 39 clue unavoidable would be better ?

C

[dobrichev]

I kept eleven's collection of 38s
published just before the old forum crash.
It has 31,348 38s---

eleven's update (2010.May.23)
has 41,261 38s

(can be found on my Multiply)

Thank you.
New 14423 38s raised.
So, there are 41261+14423=55684 known 38-clue puzzles.
40722 of them are derivative.

[Pat]

New 14423 38s raised.
So, there are 41261+14423=55684 known 38-clue puzzles.

re minimal 38s,
did you also look at the first, by ravel (2007.Jul.17) ?
+ 951 posted by HÃ¥vard (2007.Aug.9) ?

[dobrichev]

New 14423 38s raised.
So, there are 41261+14423=55684 known 38-clue puzzles.

re minimal 38s,
did you also look at the first, by ravel (2007.Jul.17) ?
+ 951 posted by HÃ¥vard (2007.Aug.9) ?

Thank you for the links.
No, I didn't know about them during the calculation. Maybe some or most of them are included in these 14423 38s.

[eleven]

Very nice idea, dobrichev !

27 new 39's in some seconds and over 14000 new 38's in some minutes, great.

Minimal puzzles with the same "outer" solution are very rare (I only knew the one you pointed to), but not in high clues, as you showed. Of course with so much givens you have many chances for an unavoidable set in the givens.

An example from your puzzles with 2 UA's:

Code: Select all

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

Though the puzzles differ in 11 cells, for a solver they are identical (if you are able to solve these ER 8.4 puzzles). The marked cells dont contribute anything more than you can eliminate the numbers from the rest of their units.

Using the newly found 38's with {-1+2}, and also {-2+2} then (not forgetting to find new ones by trying to "dob" them), i got 10 more 39's. See the updated list in the top post.

I am still calculating new 37's with this method. Its a bit more tricky because of the large file sizes, but there should be more than a million.

[dobrichev]

...Using the newly found 38's with {-1+2}, and also {-2+2} then (not forgetting to find new ones by trying to "dob" them), i got 10 more 39's.

Congratulations!
It is good that this method is not 100% parasitic, i.e. applying the transformations to the seed 38s doesn't result in the same 39s got by direct transformation of the old 39s.

[eleven]

Dobbing is a revolution for high clue search. A dobbed puzzle is a quick bridge to another promising region, which is at least [Edit:] {-4+4} away. It could speed up my method with a factor of about 5.
For a test i took the first 2000 of 1.7 mio (!) dobbed new 37's and applied a combination of {-1+1} and dobbing on them. The result was, that i found 16000 more new 37's, for which i made a {-1+2} to find 93 new 38's. This took 2 hours on a single cpu.

That means, that i never will have the time to expand all the new 37's. But i plan to feed my gotchi with small pieces for overnight runs. Probably i should restrict the new 37's to high weighted ones to get faster results.