High clue tamagotchis

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

Re:

Postby ronk » Sun Sep 12, 2010 5:21 pm

Pat wrote: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?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Re:

Postby RW » Sun Sep 12, 2010 6:39 pm

ronk wrote:
Pat wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Re:

Postby daj95376 » Mon Sep 13, 2010 12:47 pm

ronk wrote:
Pat wrote: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.

coloin wrote:... 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
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: High clue tamagotchis

Postby coloin » Mon Sep 13, 2010 2:48 pm

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
coloin
 
Posts: 1637
Joined: 05 May 2005

23 more

Postby dobrichev » Mon Sep 13, 2010 9:45 pm

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
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

The Method

Postby dobrichev » Mon Sep 13, 2010 11:30 pm

coloin wrote: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
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Postby Pat » Tue Sep 14, 2010 9:24 am

dobrichev wrote: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!! ]
User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

Re: The Method

Postby coloin » Tue Sep 14, 2010 11:16 am

dobrichev wrote: .......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
 
Posts: 1637
Joined: 05 May 2005

Re: High clue tamagotchis

Postby coloin » Tue Sep 14, 2010 6:58 pm

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
coloin
 
Posts: 1637
Joined: 05 May 2005

recent 38's list

Postby dobrichev » Tue Sep 14, 2010 8:37 pm

Pat wrote:
dobrichev wrote: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.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

re: minimal 38s

Postby Pat » Thu Sep 16, 2010 4:41 pm

dobrichev wrote: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) ?
User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

Re: re: minimal 38s

Postby dobrichev » Sat Sep 18, 2010 3:54 pm

Pat wrote:
dobrichev wrote: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.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: High clue tamagotchis

Postby eleven » Sat Sep 18, 2010 5:20 pm

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

Re: High clue tamagotchis

Postby dobrichev » Sat Sep 18, 2010 7:19 pm

eleven wrote:...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.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: High clue tamagotchis

Postby eleven » Sun Sep 19, 2010 1:25 pm

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.
Last edited by eleven on Mon Sep 20, 2010 8:00 am, edited 1 time in total.
eleven
 
Posts: 1563
Joined: 10 February 2008

PreviousNext

Return to General