High clue tamagotchis

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

High clue tamagotchis

Postby eleven » Sun May 23, 2010 9:04 pm

[Added Dec 18 2010:] This thread is about the search for minimal (irreducible) unique sudokus with the maximum number of clues. The predecessor thread is Max number of clues 2.
After i had stopped my search, enormous progress has been made by dobrichev and blue, see the thread The unexplored 40+ clue puzzle space on the programmers forum. I try to keep the list of 39's up-to-date, but please refer to this thread to get the most recent news.
Note dobrichev's site, where you can also find the collection of known 38's, minimal multisolution puzzles with 41 clues and more.

Unfortunately this thread was lost with the crash of the old forums. But i have the first post and the first summary:
2009-11-08 eleven wrote:More than 2 years ago Havard found two minimal 39 clues (see here. This was the end of the high clue search, probably also because he had used a high speed processor for several weeks to find them. This is not very encouraging for others to try it.

But things are not that worse for normal cpu users. Within 2 weeks i could repeat his experiment on a dual core 3Gh with similar results.

Using Brian Turners high speed bb solver, gsf's canonicalisation and a minimal test i got very fast -n+m functions (-1+2 14000/h, -2+1 2000/h, -2+2 600/h per core for 36/37 puzzles).

Then i generated some 1000 37's each as starting sets for my high clue tamagotchi's and let them mutate from generation to generation with -n+m operations.

I found more than 280000 37's, 2939 38's and 2 39's:
Code: Select all
...|...|...
.23|..6|7.5
..6|7.2|1.3
-----------
2.8|.4.|..1
.64|8.1|...
..1|62.|4.8
-----------
8..|.64|..7
.47|2.8|5..
612|57.|8.4

...|...|...
3.1|..7|..2
..2|.43|871
-----------
2.6|...|.5.
.15|.3.|6.7
43.|.65|.28
-----------
.5.|..4|2.6
6.4|...|.15
123|.56|.84


The first tamagotchi died out last night, but the second one still becomes fatter and fatter. In the moment it has 50000 37's and i have to wait about 2 days for the next generation. Though the last one with 40000 did not add a 39, i am optimistic to find more.

Some details:

Gotchi 1:
110827 37's, no 39.
973 38's, min 2.6, max 9.1, average 7.4223
92.5 % have only 8 digits given
61.6 % have an empty row/column
663 different patterns
First 1000 37's, min 3.2, max 9.2, average 7.9932

Gotchi 2:
173467 37's , 2 39's (still living)
1966 38's, min 3, max 9.2, average 7.7675
97.4% have only 8 digits given
94.6% have an empty row/column
1127 different patterns
First 1000 37's, min 2, max 9.1, average 7.5444

There was not one common pattern in the 2 sets.
In the second set 12 puzzles each had these patterns:
Code: Select all
XXXXXXXX.XX.X.......X.XX...XXXXX.XX.XX.X.X.....X.XX...X..XXXX..X....XXX........X.
XXXXXXXX.XX.XX....X.X..X...XXXX.XXX.X.X..X....X.XX....XXX.X.X..X...X.XX........X.


2010-01-05 eleven wrote:Here is a summary of 10 weeks high clue search.

I found over 1.5 mio 37's, 20000 38's and 42 39's. The 39's are shown in the first post of this thread. I uploaded the 38's and 37's to a free file hosting service, hopefully they can be downloaded (without banners) for some time.
  • 38's (~300K): {broken link removed}
  • 37's (~17MB): {broken link removed}
Its too early to draw any serious conclusions from my data about the number of minimal 39 and 40 clue puzzles. However, i am quite sure now, that there is no minimal 41 clue and that the number of 39's should be at te lower side of my last estimate, less than 3000.

Since i am engaged in other things now, i wont have much better results for longer time. So - to make it more interesting - here is my next

Conjecture
There is no unique, minimal puzzle with 40 givens.

Of course i hope, that its wrong again, but i have some good reasons for it:
The (-n+m) method is very effective to find high clues and especially big clusters containing them. I also could improve it by preferring the 37's with (-1+1) neighbours and higher weights (Havard needed 400000 37's to find 2 39's).
When you generate 1000 37's bottom up (strongly biased, but from a random puzzle set), you will get only a few ones, which are part of a big cluster. After i had a million 37's, i did that four times - and each of the gotchi's i started with these sets, refound 37's in my pool (then i had to combine them to avoid double computations). The last one with 2000 puzzles had 4 known 37's in the starting set. After removing them and doing 10 (-2+2)'s, 3/4 of the newly generated 1100 puzzles were known.
This suggests, that i already have found a good part of the big clusters - and my results confirm, that dense and big clusters have much more 39's than smaller ones on average.


What i missed to do was, to add cluster numbers to the puzzles (the number of the starting puzzle). This would make it possible to see exactly, how big the clusters are and how many 38's/39's they have. I had thought of that, but it was too much work for me to write my own fgrep functions to find duplicates of puzzles, renumber puzzles which belong also to another cluster etc. I like mathematics more than programming :)

Other improvements would be to make the generation of new 37 sets faster and - first of all - to use more cpu's.


One of the motivations for this search was to find out more about the distribution of high clue puzzles. This is, how i would expect the distribution of all minimals now (shows the log of the number of all non equivalent puzzles).

Image

So no 16 and no 40, about 700 39's.
The left side could be made more precise with Red Ed's subset program, but i did not bother, because the uncertainties on the right side are much larger.


[Updated list of known 39's:]
Code: Select all
                                                                                   SER  av.weight
havard
12345.67.46.72.5.1.........24.3..86..8....4.5..684..1.81.23..566...8...3.325..18.  8.3    6.56
12345.6..47.62.153.......4.24.3.658..5..4.3.1.8.5...6473.26.81.8.........12.8..3.  8.4    6.74

eleven
12345.67.46.72......76.34..21.3..8..3..28514..........63..7....7.28.6.1..4153.76.  7.8    6.08
12345.67.57.1.64....6.37.5.73.6.2...6.1.7..2.2..31.76.81...354.3..5.128..........  8.5    9.28
12345.67.57.1.64....6.37.5.73.6.2...6.1.7..2....31.76.812..354.3..5.128..........  8.3   10.33
12345.67.46.2..5..5.71...4.37654.82.8.5....64.4..8.7.573.81...66..3...87.........  7.8    7.15
12345.6..46.7.152...56..4..21786.3...3.1..862.........34.....5.7.154.23..52...7.4  7.6    6.13
12345.6..56.7.142...46..5..21786.3...3.1..862.........35.....4.7.154.23..42...7.5  7.6    5.95
12345.67.46.72....7.56.34..2513...4.3...42.5..........5.283.76.8.72.65...3..7..8.  8.3    6.74
12345.67.47....1.5..57...3424.58..615.16.2....3..4.5..71.26...33.287..16.........  9.0    5.72
12345.67.45.6..2.1..6....5.24..3.18.3.1.4..27.........51....86.83.56.7126.2.8...5  7.7   13.05
12345.67.45.7..2.1..7....5.24..3.81.3.1.4..26.........51....78.83.57.1627.2.8...5  7.7   12.15
12345.6..67.1...5...5..63..21.84.73..37.1248..........78..6154..51..486..6.58....  9.0    8.13
12345.6..47.26.153.......4.24.3.658..5..4.3.1.8.5...6471.62.83.8.........32.8..1.  8.4    6.85
12345.6..47.26.153.......4.24.3.658..5..4.3.1.8.5...6473.62.81.8.........12.8..3.  8.4    6.90
12345.67.45.6.......6.3...423..7.18..1538.7.2.........58.76.4.1.6184..27.4....86.  8.3    6.33
12345.6..67.1..5....5..6.3.23.81.74..17.4238..........78..6145..51..486..6.58....  8.9    6.51
12345....46.27.513......4..38.7..2.16...2.38..128.....84.5...3.5.6.8.1.4.3164.8..  8.4    9.41
12345.67.47.26.5.3.........28.1...353...2.78...78..1..81.6.235.7...8...1.32.1.84.  8.4    5.41
12345.67.47.26.5.3.........28.1...353.1.2.78...78..1..7...8...18..6.235..32.1.84.  8.4    5.31
12345.67.47.6..52.5..7..4.334..8..6.68.14.23..12...8.483...67.22..87.3...........  6.6    6.87
12345.67.47....52.5..7..4.334..8..6.68.14.23..12.6.8.483...67.22..87.3...........  6.6    7.28
12345.67.47....52.5..7..4.325.87.3..83...67.2.........34.18.26.68..4..3..12.6...4  7.7    6.03
12345.67.47.26.5.3.........58..1..3.3.15.278..47.8.1..7..8...618..62.3.7.3.1..8..  8.4    5.82
12345.67.47....52.5..7..4.338.14.26.64..8..3..12.6.8.483...67.22..87.3...........  6.6    7.54
12345.67.47.6..52.5..7..4.338.14.26.64..8..3..12...8.483...67.22..87.3...........  6.6    7.13
12345.67.47.36.5.2.........38.1...252...3.78...78..1..81.6.325.7...8...1.32.1.84.  8.4    5.49
12345.67.47.36.5.2.........38.1...252.1.3.78...78..1..7...8...18..6.325..32.1.84.  8.4    5.38
12345.6..46.2.7.....5.364..517.8.24.34.72518..........63.572.1.7...6.....513...6.  7.7    5.77
12345.6..46.2.7.....5.364..517.8324.34.72.18..........63.572.1.7...6.....513...6.  7.7    5.72
12345.6..46.2.7.....5.364..317.8524.54.72.18..........63.572.1.7...6.....513...6.  7.7    5.69
12345.6..46.2.7.....5.364..317.8.24.54.72318..........63.572.1.7...6.....513...6.  7.7    5.67
12345.6..46.2.7.....5.364..317.8.24.54.72318..........65.372.1.7...6.....315...6.  7.7    5.82   
12345.6..46.2.7.....5.364..317.8524.54.72.18..........65.372.1.7...6.....315...6.  7.7    5.67
12345.6..46.2.7.....5.364..517.8.24.34.72518..........65.372.1.7...6.....315...6.  7.7    5.62
12345.6..46.2.7.....5.364..517.8324.34.72.18..........65.372.1.7...6.....315...6.  7.7    5.74
12345.67.4..16.5.2.......4.23..1.86.61.83..25..86.....3.154.28.8.2..145..4..8....  8.4    8.82
12345.6..74.2.65136..7..4..38.6.....46.....31.12.4.8.687.1.23.5.3.57.1.8.........  7.3    5.38
12345.67.45.6.712...7...5..21...436..34.6.81..........54...378.3.27.6.5..7154....  8.9    6.36
12345.67.46...2...5.761.4..21.58.7..7..2.1....35.4....37216..846..82.3.7.......6.  8.4    5.46
12345.67.47.6.21356.....4..2......178.....3...371.....38254.76.74...6583.6.....4.  7.3    4.59
12345.67.47.6.21356.....4..2.7....1.8.....3...3.1....738254.76.74...6583.6.....4.  7.3    3.97
12345.67.47.6.21356.....4..38254.76.74...6583.6.....4.81....3..2.......7.371.....  7.3    5.13
12345.67.4.........7.62.3.438.2.....2.158.73...7.1.8..6.4..2.8..1286.4.3.3.14..6.  8.8    8.67
12345.67.4.........7.62.4.338.2.....2.158.73...7.1.8..6.4..2.8..1286.3.4.3.14..6.  8.8    8.51
12345.67.47...62..5.67...3434...5.6.6.21..3.....6...4283.5.172.2.58.7.13.........  8.9    5.95
12345.6..47.6..1..6.5...43.3.756.28..5..8.36..........54..1.72.7.12.584..32.4..1.  8.9    5.41
12345.6..56.7.........6352.23..4781.8.........1.83.24.68.3.415.3.158..6..5...6.8.  9.0   11.41
12345.6..47.6..1..6.5...43.3.758.26..5..6.38..........54..1.72.7.12.584..32.4..1.  8.9    5.05
12345.67.4..6......6..7243.21.58.36.38.26.1....6....8.84........3172.84...284..1.  8.3   14.49
1234..5..46.17.38...8......6.132.7...37.1426..4...7.3..1624.85..84.5162....8.....  7.8    7.00
12345.67.4..6......6..7243.21.58.36.38.26.1....6....8.84........3274.81...182..4.  8.3   15.46
12345.67.45....1....73...5424..3.78.7.184.32..382...41.1.52.867.7.6...1..........  7.9   10.03
12345.67.56.2..4..4.7.365..25.783.4.3.4..285....54....8..32.76..3.8.......2.6..8.  7.8    9.41
12345.67.46.7.....8.5.364.135..8.71..1.5738...........64.3.51..5...67..4.3.84..6.  7.8    9.10
12345.67.47.........671.3.463.82.1..8..1....6.1.....3.74.28..633.8.7.4.2.6..4.78.  8.3    9.36
12.34.56.35.16.27..........48.5.36...35.1684...148..5.87.6.1.....387..26....3.78.  9.0    6.03
12.34.56.34.6.5..7....284.351.48.7.64.........8..6.1.485.2.63.12..83.6.5.3..5....  8.9   15.15
12345.6..67.2...5...5..63..21.84.73..37.2148..........78..6254..52..486..6.58....  9.0    8.46
12.34.56.35.16.27..........48.5.16...15.3684...348..5.87.6.3.....187..26....1.78.  9.0    5.85
12345.6..47.62.153.......4.24.3.658..5..4.3.1.8.5...6471.26.83.8.........32.8..1.  8.5    6.69
12345.67.46.7..2.55.7....3.23158.4....514..23.........7.281.3.63..6..7....6.7..42  8.5    4.44
12345.67.46....2.55.76...3431284.....4.51.3.2.........63.18..272..7...6..7..6.5.3  8.5    4.03
12345.67.46....2..5.76...3431284..5..4.51.3.2.........63.18..272..7...6..7..6.5.3  8.5    4.08
12345.6..6..7.1.25.....64..56.8.....3.85..2.6.12.675.883.14.7.22.1.738.4.........  8.9    4.95
12345.67.45.7.61....7.3..5.23.6.481.8.........1438..6.3....75..5..8637.1...54..8.  8.8    6.28
12345.67.46.72.5.1.......4.3.65...8..1.83.765.8....1..84....3..6.2.8.41..3124.8..  8.3    5.26
12345.6..4..62.31.........431.76.4.87.48...63....4.17.83..7....2.158.73...72..8.1  9.0    5.97
12345.67.57.1.64....6.37.5.231...74.7..34182..........65..1328.3.....5...125...6.  9.0    8.95
12345.67.57.1.64....6.37.5.231...74.7..34128..........65..1382.3.....5...125...6.  9.0    8.82
12345.67.57.62.41...47..5..2...4.861.1.8...5..........78.....3.3.128.74..4237.18.  7.8    5.87
12345.67.4..3.651..5.......38.6.27..5...4382..12.8..4.8..2......3..6418...183.26.  8.0    5.44
12345.67.4..3.651..5.......23..6418.8..2.......183.26.38.6.27..5...4382..1..8..4.  8.0    5.49
12345.6..57.6.21....6.3..5.3571.684..6.........134.76.7..5.342..32.1457....2.....  8.4    5.36
12345.67.4..3.651..5.......38.6.2.5.5...432...1258..4.83..6412...123.86....8.....  8.4    5.44
12345.67.54.7..2..8.7.3..5.3..5.486...46.351..........41.36.78.7.8.4..2..3.8.71..  8.4    4.79
12345.67.48.6..2..6.7.3..4.2..58..67.7.16..52.........84.3..7..7.184.52...2.1..84  8.4    4.92
12345.67.46...7..27....634.21.7.583..3..8.72..........3526.148.6..54.2.3.4.....6.  7.8    6.44
12345.67.46.7.15....5...4..21.3768.58.651.7.2.........64..3....3.16.72.4...14.3..  8.2    5.67
12345.67.46.7.25....5...4..21.3768.5.8652.7.1.........64..3.....326.71.4...24.3..  8.2    5.72
12345.67.45.6.72....7.3.45.21.3..86..3.86.1...........3417.658.5....37...725...1.  7.2   10.13
12345.67.45.6.71....7.3.54.21.3..86.3..86.2...........5327.648.7.15...2..4...37..  7.2   10.33

dobrichev
12345.67.45.7.62....7.3.45.21.3..86..3.86.1...........3416.758.5....37...725...1.  7.2   10.21
12345.67.46.72.5.1.......4.3.65...8..1.83.765.8....1..84....3..6.2.4.81..3128.4..  8.3    5.36
12345.67.57.62.41...47..5..2...7.8...1.862.4..........85..3....4.128.35..3254.18.  7.8    5.77
12345.67.47.62.51...57..4..2...7.8...1.862.5..........84..3....5.128.34..3254.18.  7.8    5.97
12345.67.57.2.64....6.37.5.231...74.7..34281..........65..2318.3.....5...125...6.  9.0    8.85
12345.67.57.2.64....6.37.5.231...74.7..34218..........65..2381.3.....5...125...6.  9.0    8.72
12345.67.47.........672.3.463.81.2..2......6..8.2....374.18..363...4.78..68.7.4.1  8.3    9.00
12345.67.47.........672.3.436.81.2..2......3..8.2....674.18..636...4.78..38.7.4.1  8.3    9.05
12345.67.47.........671.3.436.82.1..8..1....3.1.....6.74.28..366.8.7.4.2.3..4.78.  8.3    9.31
12345.67.46....5..8.76.1.3464.1..7.33....6.45.7..4.86.73.51..8..1.8..357.........  7.8    8.77
12345.67.46.7.....8.5.364.153..8.71..1.3758...........64.5.31..3...67..4.5.84..6.  7.8    8.79
12345.67.46....5..8.76.1.3437.51..8..1.8..753.........64.1..3.77....6.45.3..4.86.  7.8    9.08
12345.67.46.2..5..5.7.364..34.782.5.2.5..384....54....8..32.76..3.8.......2.6..8.  7.8    9.08
12345.67.46.2..5..5.7.364..24.783.5.3.5..284....54....8..32.76..3.8.......2.6..8.  7.8    9.10
12345.67.56.2..4..4.7.365..35.782.4.2.4..385....54....8..32.76..3.8.......2.6..8.  7.8    9.38
12345.67.4..61.5.2.......4.21.3..86.63.18..25..8.6....3.154.28.8.2..145..4.8.....  8.4    9.13
12345.67.4..62.5.1.......4.21.3..86.63.28..15..8.6....3.254.18.8.1..245..4.8.....  8.4    9.10
12345.67.4..61.5.2.......4.23.1..86.61.38..25..8.6....3.154.28.8.2..145..4.8.....  8.4    9.03
12345.67.4..16.5.2.......4.21..3.86.63.81..25..86.....3.154.28.8.2..145..4..8....  8.4    8.92
12345.67.4..26.5.1.......4.21..3.86.63.82..15..86.....3.254.18.8.1..245..4..8....  8.4    8.90
12345.67.45.7.612...6...5..23...471..14.7.38..........54...386.3.26.7.5..6154....  8.9    5.95
12345.67.45.6.721...7...5..21...436..34.6.82..........54...378.3.17.6.5..7254....  8.9    6.31
12.34.56.34.5.61.2.........27.4..61.4.16.7.25.56...7..5.48.327.7.........827.435.  8.9   14.21
12.34.56.34.6.5..7....284.325.8.63.18..23.6.5.3..5....51.48.7.64.........8..6.1.4  8.9   15.59
12345.67.45.7.62....7.3..5.21.3.486.8.........3468..2.3....75..5..8637.2...54..8.  8.8    6.28
12345.67.45.7.61....7.3..5.21.3.486.8.........3468..1.3....75..5..8637.1...54..8.  8.8    6.62
12345.67.45.7.61....7.3.54.21.3..86.3..86.2...........5326.748.7.15...2..4...37..  7.2   10.44
12345.6..4..61.53..5.......21.57.3..7.4.2..5..351.427.36..4.82..4.86.7.3...2...6.  9.1    6.51   
12345.6..4..6...1..6...34.23.256...75.137.2.6.7.......83.74..212.48..7...1..3.8.4  8.4    6.23   
12345.67.47.6.12..6.57...4.25.3...1.3...17.2..........84...3.6.7.684...2.321.6.84  6.6    5.97   
12345.6..4.........5.2.634.57.6.1.3.3.257.16..1..2.7..74.16....2..8.547..35.4..1.  8.8    6.90   
12345.67.46.1..5.25.7.6.4..37..2.8..2...817.3........564.21.3.77....6..4.32.4.1..  7.9    8.44   
12345.67.46.7.21..7.56...4.35.8...2.2..5.3.81.....7...64.3.521.5....6..4.321...6.  7.9    8.44   
12345.67.4..3..2...7..1..4.3.28.1.6..6153.82..........6.874..52.371.548...4.8.7..  8.4    5.26
12345.67.4..3..2...7..1..4.3.28.1.6..6153.82..........6.478..52.371.548...8.4.7..  8.4    5.44
12345.67.45...61..6.83..4..54.6.382.3.6..2.4..8.54..6.83.2...1.7..13528..........  8.3    4.82
12345.6..4..6...1..6...34.23.157.2.65.236...7.7.......83.74..212.48..7...1..3.8.4  8.4    6.31
1234567..47.82....8.67.1...2386.415.64.5128.3......4..3.21.5...7..26.....6...7...  7.1    5.72
12345.6..47.26.135.......4.24.3.658.3.1.8..64.8..4...171.62.85.8.........328...1.  8.4    5.62
12345.6..47.26.135.......4.24.3.685.3.1.8..64.8..4...171.62.58.8.........328...1.  8.4    5.82
12345678.74.82....8.67.1...37.56..4.4.23.7.5..6...2.7.61.28....2.46......38..4...  6.7    4.36
12345678.74.82....8.67.1...21.68....6.42......38..4...37.56..4.4.23.7.5..6...2.7.  6.7    4.31

eleven
12345.67.45.76.2..7....3.4.2.534..1.3.1.8542..4..1....5.2.3.76.6..5...8..3..7...2  8.4    4.38
12345.67.46.2..5..5....3.4.3.682...7.7.13.8.6.........63254.78.7.5.82.64.4......5  7.2   10.54
12345.6..4.........5.2.714.38..2571..1.8.......517.83.53.78.4..84.5.23.7..2.4..8.  8.3    7.03
12345.67.47.62.1.55.......475.83..61.125...87.8....5..83.24.71.2...8.....473.....  6.6    3.97
12345.67.46.71.3.57......4.28.57..363.6.8.75.......8..83214..6.64.8...1...1...4..  7.9    6.26
12345.67.56.2.74..4.7.365..25.7.138.3..52.71........5.83...214..12.4.86..........  8.4    5.31
12345.67.46....5.25.76..41.63.5..1278.5....6..7..6.8.574.83.2.13..2..7......1....  7.2    5.13
12345.67.46....5.25.76..41.63.58.1278.5....6..7..6.8.574..3.2.13..2..7......1....  7.2    5.46
12345.67.46.7.2...7.561.4..54.2.1.3.3..5..2.........1.63.12578.8.7.6.....5.8.7.6.  7.2    5.85
12345.67.46.7.2...7.561.4..54.2.183.3..5..2.........1.63.1257..8.7.6.....5.8.7.6.  7.2    5.41
12345.67.45.67.21.7.6......34..6....6.583..2...25.4.6.5.73...422...457...3.7..1..  8.3    4.59
12345.67.46.27.5.1..5......214.8..6.3....2..5.56.4.8..83...4..66.182.....42.3.18.  8.4    6.08
12.34.56.35.1.642..........27.8.1.4.8..67.2...13.2478.58..1.6.4.31.658.......8.5.  8.9    9.21
12.34.56.35.1..42......2...27.8.1.4.8..67.2...13.2478.58..1.6.4.31.658.......8.5.  8.9    8.67

dobrichev
12.34.56.36.2.51...........6.37.248..82.3467..7.8.....75.42...62...8.75..365.7..4  9.0    6.56
12345.6..46.7..1......6..2.23.84..718.....2...1427.3.834....8.668.5.471...168....  7.8    6.97
12345.67.5..6.143..4..7....21.78.3..83.51.72........8.48......33.214.86..618...4.  7.9    9.87
12345.67.5..6.143..4..7....21.78.3..83.51.72........8.48..6...33.214.8...618...4.  8.3   11.67

blue
12345.67.46...25..5.863.4..34.21.78.8.2..314..1..4....63..2.8.72......6..8.3...5.  7.9    6.36
12345.6..46.1.7.....5.264..54.71238.3.7.8524..........65.271.3.7...6.....315...6.  7.7    5.46   
12345.6..45.7...2.7.6.3.54.36....41....34.86..........51..2378.6.751.2...32.7.15.  7.7    8.05   
12345.67.46.7..5.37......4.38....75.2.657.83..7.8....684..2.3656...4..8..32...4..  8.5    6.10   
12345.67.4..1.6....5..2.4..28.6.134.3.124..8..4..8....51..6283.83.51......28...5.  7.9    6.05   
12345.67.45.67.13.........458..67.133..8....5.1.5..86.83.74...12.1.8..4..4....38.  7.8    8.82   
12345.67.45.67.13.........438..67.155..8....3.1.5..86.83.74...12.1.8..4..4....38.  7.8    7.64   
12345.67.47.1.652.6...7.4..28651.73.71.6.3285.3...7...8.....3...42............842  8.3    4.56   
12345.67.46.3.71257....64..23.84.56.64.5.328..8.6...4.8.2.......1.7....2.7.....1.  7.2    4.23   
12345.67.46.3.71257..6..4..23.84.56.64.5.328..8...6.4.8.2.......1.7....2.7.....1.  7.3    4.74   
12345.67.4..16.5.2.......4.23..1685.51.83..2...85.....3.164.28.8.2..146..4..8....  8.4    8.21   
12345.67.46.1273.55..6....423.74.86.64.28.7.3.8..6.4..8.2.......1...25...5..1....  7.2    4.10   
12345.67.46.1273.55..6..4..23.74.86.64.28.7.3.8..6...48.2.......1...25...5..1....  7.3    4.51   
12345.67.46.3.71257....64..23.84.56.64.5.328..8.6...4.8.......2.127......7.....1.  7.2    4.26   
12345.67.46.3.71257..6..4..23.84.56.64.5.328..8...6.4.8.......2.127......7.....1.  7.3    4.59   
12345.67.46.1273.55..6....423.74.86.64.28.7.3.8..6.4..8....2....12...5...5..1....  7.2    4.23   
12345.67.46.1273.55..6..4..23.74.86.64.28.7.3.8..6...48....2....12...5...5..1....  7.3    4.69   
12345.67.47.62.5.15..7...4.28153.76.65.287.13.3..6...58423........8.........4....  7.2    5.74   
12345.67.47...152.6....74..28154.73.74.1.3285.3.7...4.8.....36..62............8.2  7.3    5.21   
12345.67.47...152.6....74..28154.73.74.1.3285.3.7...4.8.....36..6......2..2...8..  7.3    4.90   
12345.67.4..26.5.1.......4.21..3685.53.82..1...85.....3.264.18.8.1..246..4..8....  8.4    8.31   
12345.67.5..6.21......3.5..36.5...8.8.5.2346..1286..5.63128.74.2...4.81..........  7.2    4.87   
12345.67.46.3.71257..6..4..24.8.356.63.54.28..8...6.4.8.2.......1.7....2.7.....1.  7.3    4.77   
12345.67.46.3.71257..6..4..24.8.356.63.54.28..8...6.4.8.......2.127......7.....1.  7.3    4.69   
12345.67.56.3.71247....65..25.6.348.63.84.25..8.5...6.8.2.......1.7....2.7.....1.  7.2    4.33   
12345.67.56.3.71247..6..5..25.8.346.63.54.28..8...6.5.8.2.......1.7....2.7.....1.  7.3    4.79   
12345.67.46.3.71257....64..24.5.386.63.84.25..8.6...4.87.....1..1.7....2..2......  7.2    5.85   
12345.67.46.3.71257....64..24.5.386.63.84.25..8.6...4.87.....1..127.............2  7.2    5.67   
12345.67.46.3.71257....64..23.54.86.58.6.324..4.8...5.87.....1..127.............2  7.2    6.41   
12345.67.56.3.71247....65..23.54.86.48.6.325..5.8...4.87.....1..127.............2  7.2    6.41   
12345.67.56.3.71247....65..23.64.85.45.8.326..8.5...4.87.....1..127.............2  7.2    6.38   
12345.67.56.3.71247....65..23.64.85.45.8.326..8.5...4.87.....1..1.7....2..2......  7.2    6.36   
12345.67.46.3.752.7..6..4..28756.31.61.7.3285.3...1.6.842...1........8.........4.  7.2    5.46   
12345.67.46.3.752.7..6..4..28756.31.61.7.3285.3...1.6.8.2...1........8.........42  7.2    4.49   
12345.67.56.1273.44..6...5.23.74.86.64.28.7.3.8..6.4..8.2.......1...25...5..1....  7.2    4.15   
12345.67.46.72.3.55..6..4..28531.76.61.2875.3.3..6...18421........8.........4....  7.2    5.44   
12345.67.46.3.71257....64..23.84.56.68.5.324..4.6...8.8.......2.127......7.....1.  7.2    4.21   
12345.67.46.3.71257....64..23.84.56.68.5.324..4.6...8.8.2.......1.7....2.7.....1.  7.2    4.33   
12345.67.56.1273.44..6...5.23.84.76.74.26.8.3.8..7.4..85..1.....12...5.......2...  7.2    5.51   
12345.67.56.1273.44..6...5.234.8.76.75.26.8.3.8..7...58...1.....12.4.......8.2...  7.6    5.62   
12345.67.56.3.71247....65..25.6.348.63.84.25..8.5...6.8.......2.127......7.....1.  7.2    4.46   
12345.67.56.3.71247..6..5..25.8.346.63.54.28..8...6.5.8.......2.127......7.....1.  7.3    4.72   
12345.67.47.3.61256..7..4..23654.78.74...325..8...7.4.8.2.......1....86........12  7.3    5.33   
12345.67.47.3.61256..7..4..23654.78.74...325..8...7.4.8.......2.1....86...2....1.  7.3    5.03   
12345.67.46.72.5.15........28153.76.65.2871.3.3..6...58..3.2....42..6......84....  7.2    4.36   
12345.67.46.72.5.15..6.....28153.76.65.2871.3.3......58..3.2....42..6......84....  7.2    4.33   
12345.67.56.3.71247....65..27.84.35.85.7.324..3.5...8..1....86...2.........6...12  7.2    5.54   
12345.67.47.62.5.15........28153.76.75.2861.3.3..7...58..3.2....42..7......84....  7.2    4.23   
12345.67.46.2173.55.......423584.76.68.72.4.3.4.6.....8.2..6....1.5.2......18....  7.2    4.21   
12345.67.4..16.5.2.......4.21..3685.53.81..2...85.....3.164.28.8.2..146..4..8....  8.4    8.36   
12345.67.46.1273.55..6....423.84.76.74.26.8.3.8..7.4..85..1.....12...5.......2...  7.2    6.13   
12345.67.47.1263.55..7...4.24.56.8.335.28.46..8..4.5...1..7......28.........127..  7.2    4.38   
12345.67.47.1263.55..7...4.24.56.8.335.28.46..8..4.5...1..7......2.1.7.....8.2...  7.2    4.44   
12345.67.56.1273.44..6....523.74.86.64.28.7.3.8..6.4..8.2.......1...25...5..1....  7.2    4.00   
12345.67.46.72.5.15..6...4.28153.76.75.286.13.3..7...58423........8.........4....  7.2    5.77   
12345.67.46.72.1.55..6.....28513.76.61.2875.3.3..6...18423........8.........42...  7.2    4.82   
12345.67.46.3.71257...6.4..24.5.378.37.84.25..8.7...4..1.....6...26...1.......8.2  7.2    4.41   
12345.67.56.3.71247...6.5..25.8.374.37.54.28..8.7...5..1.....6...26...1.......8.2  7.2    4.33   
12345.67.46.17.52...76..4..3...1.862.1.8..35..........84.....3.7.1.4.28..3278.14.  8.0    6.31   
12345.67.47.1263.55..7...4.25.34.86.84.26.5.3.3..8.4...1.87......2..........127..  7.2    6.13   
12345.67.56.1273.44..6..5..23458.76.65.27...3.8..6...58.2.......1.84........12...  7.3    5.28   
12345.67.56.1273.44..6..5..23458.76.65.27...3.8..6...58....2....1.84......2.1....  7.3    4.90   
12345.67.46.1273.55..6....423.84.76.78.26.4.3.4..7.8..85..1.....12...5.......2...  7.2    6.10   
12345.6..46.2.7...7.5.164..54.72138..37.8514..........65.172.3.3.25...6.....6....  7.7    7.90   
12345.67.46.3.71257...6.4..24.8.375.37.54.28..8.7...4..1.....6...26...1.......8.2  7.2    4.38   
12345.67.46.72.1.55..6.....28513.76.61.2875.3.3..6...184...23....2.........34....  7.2    4.82   
12345.67.46.72.1.55..6.....28513.76.61.2875.3.3..6...184...23....28.........4....  7.2    4.74   
12345.67.47.62.1.55..7.....28513.76.71.2865.3.3..7...184...23....2.........34....  7.2    4.90   
12345.67.47.62.1.55..7.....28513.76.71.2865.3.3..7...184...23....28.........4....  7.2    4.82   
12345.67.56.3.71247..6..5..23..4.76.68.7.3245.7..6..8.85.....1..1......2..2...8..  7.3    4.77   
12345.67.56.3.71247..6..5..23..4.76.68.7.3245.7..6..8.85.....1..12............8.2  7.3    5.15   
12345.67.47.1263.55..7...4.25.38.46.84.26.5.3.3..4.8...1.87......2..........127..  7.2    6.10
12345.67.46.72...55..1..4..28563.74.64.2875.3.3..4...68.23......1...2......81....  7.3    4.62
12345.67.46.72...55..1..4..28563.74.64.2875.3.3..4...68..3.2....12.........81....  7.3    5.28
12345.67.46...752.7..6..1..28756.43.64.7.3285.3...4.6.8.2...3...1......2......81.  7.3    4.51
12345.67.4..7..1...8..3..452.158.36.5.........3826..5137.84..168.4...7...1..7...4  8.3    7.31
12345.67.46.1..5....7.6....63.28..572.....86..7.6..1..71.82.3.53.251.78..8.....1.  7.6     7.44
12345.67.46.1..5....7.6....31.82.7.57.251.38..8.....1.63.28..572.....86..7.6..1..  7.6     7.49
12345.67.47.26.5.16.....4..3..68.1.7.1753.86........5.74.3..2...3284.71.....2..4.  7.1     9.18
12345.67.47.36.5.16.....4..2..68.1.7.1752.86........5.74.2..3...3284.71.....3..4.  7.1     8.64
12345.67.46.2..5.........4.28.74..3.34..2678..7.8..4..81.57236.6.........326..85.  8.3     9.28
12345.67.46.7....27.5...41.25.3.784.3..58..2.....4....5328..16.61...5.....716.2..  8.4     6.31
12345.67.46.27.5....5..3...516.428..2.4.871.6.........6.172.3..3....4.6..42.3.7.1  8.0    10.05
12345.6..46.27.5....5..3...516.4287.2.4.8716..........6.172.3..3....4..6.42.3.71.  8.0    10.05
12.34.56.35.7.28.1..4.5..3.4.128.67.2..47.31..........54...718.8..5......1283.75.  8.0     7.56
12345.6..67.1.824...4..6...3176..4..4.238.76..6..4....73.81.52.2.15.387..........  7.1     5.05
12345.6..67.1.824...4..6...3176..4..4.238.76..6..4....73.51.82.2.18.357..........  7.1     5.33
12345.6..4..16.523.........23.54.7.88.4.7..52.7..8.3..71.8...363.261.8....87..2..  9.0     7.15
12345.6..4..16.523.........23.54.7..8.4.7..52.7..8.3..71.8...363.261.87...87..2..  9.0     7.26
12.34.56.35.7.28.1..4.5..3.4.128.67.2..47.31..........84...715.5..8......1253.78.  8.0     7.64
12345.67.4..7..1...8..3..542.158.36.5.........3826..1531.87..468.4...7...7..4...1  8.3     7.82
12345.67.45.7..2....73...5.24.16.83.3.184..62.........81.67..257.258...65.....7..  8.3     5.13
12345.67.45.7..2.3..7....5.24.16.83.3.184..62.........81.67..257.258...65.....7..  8.3     9.67
12345.67.4..63.5...6...2.4.21.3..85.83.52741..........38..7..6.6..2.378...286.1..  8.3     5.08
12345.67.45.7..2.1..7....5.24.36.81.3.184..62.........83.67..257.258...65.....7..  8.3    10.10
12345.67.45.6..2..6.7.3..5423.18.74.7..34...2.........37186..255.........4251..6.  7.7     6.87
12345.67.47...25..5..17.4.321.8..3..38.24.16.....1..8..4258.73..3..2.85....7.....  8.4     9.90
12.34.56.35.1..4.2..6..2..161.7.3.455.34.17.6.7....1..76.83.2..2....7....3.2.46..  9.0     9.82
12.34.56.35.1..4.2..6..2..151.7.3.466.34.17.5.7....1..76.83.2..2....7....3.2.46..  9.0     9.82
12345.67.46.17......7..3...23651.8...1.83..26.........64.3.178..71.8.4.2.8.74..6.  7.8     4.90
12345.67.46.7..1..7.86...4323.5.7.815..8.273...7......3.12.5.6.6...8.3....2..6.1.  7.8     7.74
12345.67.47.16.5.2.......4.23..1.78.8.........1783.25.74..813.53.154.82.......4..  8.3    15.44
12345.67.47.16.5.2.......4.21..3.78.8.........3781.25.74..813.53.154.82.......4..  8.3    19.46
12.34.56.37.6.52....6....3.7..8......8..7165...245.78.86.13..252.158.37..3....8..  9.0     8.31
12.34.56.35.7.18.2..4.5..3.48...732.2.153.78..3.8......4218.67..1.47.25..........  8.0     7.72
12345.67.46.27.51...7.....424..8.73.3.174..56.763..4..6..5..1...128..3.5.......6.  8.4     5.26
12345.67.46.27.513..7.....424..8.7..3.174..56.763..4..6..5..1...128..3.5.......6.  8.4     5.15
12345.67.4..62.5.1.6.....4.21..3.48.83.24.15...48.....68......53.158.76.....6.81.  7.9     6.10
12345.67.4..6......6..7241.21.86..3.38.72.16...6...8..84...7....3254.78....28..4.  7.9     5.97
12345.67.4..6......6..7241.21.86..3.38.72.16...6...8..84...7....3258.74....24..8.  7.9     6.03
12345.67.45.2671.........4.34..82...2.15.6..4.8574....83.625.1..1287..6.......8..  8.4     4.23
12345.6..67.12.534.....6...38.21..462..8..1.3.1....8..56..4.3.88..5......3268.4.5  8.9     5.69
12345.6..67.12.534.....6...21.86..4338.2..1.6....1.8..53..8.4..8.......5.6254.3.8  8.9     5.72
12345.67.56.7..34.7..6.....68.52.4.33.2.8.56.....6..8.83.27..542..84.73......5...  8.3     5.74
12345.67.45.6..2....73...4.37.8.5.2.2.513.78..1.......54.78.3.2.3254.81.......4..  8.3     4.74
12345.67.46.17......7..3...23654.8...4.38..26.........61..3478..748..1.2.8.71..6.  7.8     4.77
12345.67.47.61.5....6...4..23..618.76..7....2.1..8.3..84.....3.3.214.78...18..2.4  8.3     8.18
12345.67.47.61.5.3..6...4..2...618.76..7....2.1..8.3..84.....3.3.214.78...18..2.4  8.3     9.13
12345.67.4..6.7....7..3.4.528.3..16.31.86...4......8..54...378.83.7.65.1..158....  8.3     7.51
12345.67.46.71......7..3...23654.8...4.83..26.........61.3.478..74.8.1.2.8.17..6.  7.8     4.74
12345.67.46.72.5..7....1.4.28.1..73.37.28.1.5....7.8..81..4235..3.51.4.....8.....  8.3     5.82
12345.67.4..16.5.3.5....4..23.54.78.74.82.3.5..5....4.3..28.1.7.72.1.83..1.......  7.1     5.00
12345.67.4..16.5.3.5....4..23.54.78.74.82.3.5..5....4.3..21.8.7.72.8.13..1.......  7.1     5.31
12345.67.46.17......7..3...23651.8...1.38..26.........64..3178..718..4.2.8.74..6.  7.8     5.03
12345.67.46.17......7..3...23654.8...4.83..26.........61.3.478..74.8.1.2.8.71..6.  7.8     4.77
12345.67.4..6......6..7241.21.86.3..38.72.16...6....8.84...7....3258.74....24.8..  7.9     6.54
12345.6..47.26.135......4..31.8..2.484.12..53....4....63..8.5..78.51.3.6..16....8  7.7     9.92
12345.67.47.16.2536.....4..38.24..67.67.8...4.4....38.832.1.7.5.1..2.83..........  7.1     4.00
12345.6..47.62.31........4.38..62..12.781..3..1....8..73.28..6484..76..3..2.4..8.  8.9     9.41
12345.67.46.72.5..7....1.4.28.1..43.34.28.1.5....4.8..81..7235..3.51.78..........  8.3     6.46
12345.67.47.61.5.2.......4.23.1..78.8.........1738.25.74.8.13.53.154.82.......4..  8.3    14.95
12345.67.47.61.5.2......4..23.56.8.75.7.8.26........5.74..3.1..3.184.72..8.1...4.  7.1     9.56
12345.6..46.71..52.......4.23.57..865.6.8.72.......5..64..3..1.3.184.26..821..4..  8.9     8.33
12345.67.45.2671...........21478..6.38.642.1.......8..53.8.4...8.257.....41.26..5  7.3     3.51
12345.67.45.2671.........5.21478..6.38.6.2.1.......8..53.8.4...8.257.....41.26..5  8.4     4.62
12345.67.47.26.3.56.......478261...336.8....1.......6.83714....24.58.137......4..  7.1    16.21
12345.67.47.61.5.2.......4.21.3..78.8.........3718.25.74.8.13.53.154.82.......4..  8.3    18.97
12.34.56.34.5..2.7..6.8...426.83..7583.17..26.........6.341..524..7..6...82....41  8.3     5.67
12.34.56.36.2.51....4..6.3.24.5..78.7...2435...57.....4.16.287..324.761..7.......  9.0     8.56
12345.67.57.62.4....67.3.5.21.3..74..34...18.....4....3.186.5...6253.81..5.....6.  7.9     7.44
12345.67.46......55.716.3.431.82.5.78.....23..7.......64.2.1..373.68.4.2....4..6.  7.8     6.26
12345.67.46...7...7.53.614.31.7.582.8..23.....5.......53.6.248.64...32.1....4..6.  7.8     6.28
12345.67.47.6.12.........4.23781..6.81..65.27......8..78..43...3.21.6.8..4158....  8.3     6.10
12345.67.4..71.5.3.7.......28.5.173.7...8.2.5.3.27..8.34..2.8..85.14.362...8.....  7.7     5.56
12345.67.46.32715.5.......438..4256..5.7.38.....58....81..3.7...3287.41....2.....  8.3     6.05
12345.67.46.27.3157.......437......1.8671...3...8..76.64.58.13.83..4..56......4..  6.6     7.36
12345.67.47.63.5.2..6...4..21.56.8.7.67.8.25........6.74..1.3...8134.72....8...4.  7.1     7.62
12345.67.47.63.5.2..6...4..21.56.8.76.7.8.25........6.74..1.3..3.184.72....3...4.  7.1    10.00
12345.67.47.62.5.1..6...4..31.56.8.7.67.8.15........6.74..3.2...3284.71....2...4.  7.1    11.36
12345.67.47.62.5.1..6...4..31.56.8.7.67.8.1.........6.74..3.2...3284.71...12...4.  7.2     6.97
12345.67.47.63.5.2..6...4..21.56.8.7.67.8.25........6.74..1.3...3184.72....3...4.  7.1     9.87
12345.67.4..62.15..........2.7.4683.8..3.27...3487..1.78..643...4128..6...2....8.  8.4     6.85
12345.67.47.63.5.1..6...4..21.56.8.7.67.8.15........6.74..2.3...3284.71....3...4.  7.1    10.28
12345.6..56.7..14...7.6..533.468..216..2..43..1..4...675.82.31..3157............5  9.0     8.77
12345.67.57.62.4....67.3.5.21.3..74..34...18.....4....3.156.8...6283.51..5.....6.  7.9     7.33
12345.67.46.72.5.1.........31.8...5.8..5..3.6.56.4.81.6.72..18..31.8.7...8..7..63  8.3     4.92
12345.67.46.72.5.1.........35.8...1.8..5..3.6.16.4.85.6.72..18..31.8.7...8..7..63  8.3     4.90
12345.67.4..27.5.1.7.......28.34.16.3.18..2...4..2..8.71..348..8..7......3458.71.  8.3    11.15
12345.6..67.12.435.....6...28.61..5331..8.2.6...2..8..43.8..5..8.......4.6154.3.8  8.9     5.82
12345.67.47.26.5..5......4.25..7683.3..82..5..8.5.....8327..46.7..64238.........7  8.2     5.85
12345.6..47.61.32........4.38..76..474.18..63..1.4..8.83..61..22.....8...1782..3.  8.9    10.13
12345.67.57.62.4....67.3.5.21.3..74..34...81.....4....3.186.5...6253.18..5.....6.  7.9     7.10
12345.67.47.63.5.1..6...4..21.56.8.76.7.8.15........6.74..2.3..3.284.71....3...4.  7.1     9.59
12345.67.46.71......7..3...23654.8...4.38..26.........61..3478..748..1.2.8.17..6.  7.8     4.79
12345.67.45.7..1....7.3..4523.86..1..8134...6......8..37268..515....3....1.57..6.  8.3     5.36
12345.67.47.63.5.2......4..21.56.8.75.7.8.26........5.74..1.3..3.184.72..8.3...4.  7.1     8.59
12345.67.46.72.5.1.........35.8...1.8..5..3.6.16.4.85.6.12..78..37.8.1...8..7..63  8.3     4.92
12345.67.46.72.5.1.........31.8...5.8..5..3.6.56.4.81.6.12..78..37.8.1...8..7..63  8.3     4.95
12.34.56.36.5.14.2.....6.1.6..4..7...3.6.7.25.7..5364.78..3.25.2.3..517..1.7.....  9.2     7.59
12.34.56.36.5.14.2.....6.1.6..4..7...3.6.7.25.7..5364.78.13.25.2.3..5.7..1.7.....  9.2     8.33
12345.67.46.2..5.15.7....4.276.4.18.34..8.7.5..5....6473.12.8.66.2....17.........  7.9     6.05
12345.67.45.76.21.7.....4..31.5.678..7..8.....8.37.1..53.64.8.184..1536..........  7.8    10.36
12.34.56.36.2.51....4..6.3.24.5..78.8...2435...58.....4.16.287..324.861..8.......  9.0     9.67
12345.67.45.67.1..7....3.4.23.5.648.8...4.....4.3.....38..6572.5.273.86..7.8.....  8.2     8.33
12345.67.47.61.5.2..6...4..23.56.8.76.7.8.25........6.74..3.1..3.184.72....1...4.  7.1    11.08
12345.67.47.61.5.2..6...4..23.56.8.76.7.8.2.........6.74..3.1..3.184.72...21...4.  7.2     6.95
12345.67.47.6..52...57..4.334.18.25.2.154..3..5......471..6.3...328..7......7...2  8.9     9.15
12.34.56.35.2.64.1.........71.46.8.22...8.67..8.7.2.1483...7.4..7.63...8..18..73.  9.0     5.51
12345.6..5..6..34..6..7..5221.84.73.83.71..25.........3.216...46...8...3.815..26.  8.9     4.79
12345.67.45.6..1....6.2...524178.3..3..24.817.........53.86.7.16.4....837.....56.  8.3     5.69
12345.67.45.6..1....6.2...524178.3..3..24.817.........53.86...16.4.7..837.....56.  8.3     4.62
12345.67.45.6..1....6.2...524178.3..3..24.817.........53.86.7.16.45...837......6.  8.3     5.10
12345.67.45.6..1....6.2...524178.3..3..24..17.........73.86.5.16.457..835......6.  8.3     4.26
12.34.56.36.5.24.1.....6...2....78.57...85.4..8.42.7..6..7.41.8.1..5.67..7..61.54  9.0     6.56
12.34.56.35.6.27.1....1...328.73.4.54.5.2.3...3.4.....81.27.65.5.216...7.6....1..  9.0     9.08
12.34.56.35.6.27.1....1...348.72.3.52.5.3.4...3.4.....81.27.65.5.216...7.6....1..  9.0     8.74
12.34.56.35.6.27.1....1...348.72.3.55.2.3.4...3.4.....81.27.65.2.516...7.6....1..  9.0     8.44
12345.67.48.2.7.....7.3.4..23.78516..1.32.85..........34.5.278.8......4..7284.5..  7.7     4.92
12345.67.48.2.......7.3.4..23.78516..1.32.85..........34.5.278.8...7..4..7284.5..  7.7     4.67
12.34.56.34.5.6..1.........78.63..522..7....6.3..5..7.87..156.44..8.3.15.1.46.28.  8.9     8.72
12.34.56.34.6.52.1.........27.83.6.58..5.4..2.3..6.8..78..16.5.4....31.6.1.45.72.  8.9     7.77
12345.67.46.27.35.5.......438..2..6...218.7.3......8..84...253.2.58..4.6.3654....  7.9     6.31
12345.67.46.27.35.7.......438..2..6...218.5.3......8..84...273.2.78..4.6.3674....  7.9     5.87
12345.67.46.72.35.5.......438.2...6...281.7.3......8..84...253.2.5.8.4.6.3654....  7.9     6.46

dobrichev
12.34.56.35.1..4.2..6..2..161.7.3.545.34.17.6.7....1..76.83.2.52....7....3.2..6..
12345.67.46.17...5..5..3..431678.5.22..53..6..5.......63184.2...4.3....6..2.1.4..
12345.67.46.17...5..5..3..431678.5.2.5..........53.76.63184.2...4.3....6..2.1.4..
12345.67.46.17...5..5..3..431678..52.5..........53.76.63184..2..4.3....6..2.1..4.
12345.67.57.3.61246...7.5..28..47.5.75.8.3241.3.5...8.8.......2.62.......1....86.
12345.67.56.3.71247....65..23184.76..7..6328..8.7...4.85.....1...2...8.........52
12345.67.57.3.61246...7.5..28..4735.75.8.324..3.5...8.86.....1...2...86.........2
12345.67.56.3.71247....65..23.84.76.47..6328..8.7...4.85......2.1....85...2......

This is the first minimal 41-clue with multiple solutions found by dobrichev
Code: Select all
........1.12.34.56.65.1243...7..81...8142...362..7158..582436.7.7.......2.6.873.5
Last edited by eleven on Thu Jan 16, 2014 8:17 am, edited 14 times in total.
eleven
 
Posts: 3121
Joined: 10 February 2008

Re: High clue tamagotchis

Postby eleven » Sun May 23, 2010 9:15 pm

Today i finished my search for minimal puzzles with maximum givens.

Here is my final list with 80 new 39's:
Code: Select all
                                                                                  SER  av.weight
12345.67.46.72......76.34..21.3..8..3..28514..........63..7....7.28.6.1..4153.76.  7.8    6.08
12345.67.57.1.64....6.37.5.73.6.2...6.1.7..2.2..31.76.81...354.3..5.128..........  8.5    9.28
12345.67.57.1.64....6.37.5.73.6.2...6.1.7..2....31.76.812..354.3..5.128..........  8.3   10.33
12345.67.46.2..5..5.71...4.37654.82.8.5....64.4..8.7.573.81...66..3...87.........  7.8    7.15
12345.6..46.7.152...56..4..21786.3...3.1..862.........34.....5.7.154.23..52...7.4  7.6    6.13
12345.6..56.7.142...46..5..21786.3...3.1..862.........35.....4.7.154.23..42...7.5  7.6    5.95
12345.67.46.72....7.56.34..2513...4.3...42.5..........5.283.76.8.72.65...3..7..8.  8.3    6.74
12345.67.47....1.5..57...3424.58..615.16.2....3..4.5..71.26...33.287..16.........  9.0    5.72
12345.67.45.6..2.1..6....5.24..3.18.3.1.4..27.........51....86.83.56.7126.2.8...5  7.7   13.05
12345.67.45.7..2.1..7....5.24..3.81.3.1.4..26.........51....78.83.57.1627.2.8...5  7.7   12.15
12345.6..67.1...5...5..63..21.84.73..37.1248..........78..6154..51..486..6.58....  9.0    8.13
12345.6..47.26.153.......4.24.3.658..5..4.3.1.8.5...6471.62.83.8.........32.8..1.  8.4    6.85
12345.6..47.26.153.......4.24.3.658..5..4.3.1.8.5...6473.62.81.8.........12.8..3.  8.4    6.90
12345.67.45.6.......6.3...423..7.18..1538.7.2.........58.76.4.1.6184..27.4....86.  8.3    6.33
12345.6..67.1..5....5..6.3.23.81.74..17.4238..........78..6145..51..486..6.58....  8.9    6.51
12345....46.27.513......4..38.7..2.16...2.38..128.....84.5...3.5.6.8.1.4.3164.8..  8.4    9.41
12345.67.47.26.5.3.........28.1...353...2.78...78..1..81.6.235.7...8...1.32.1.84.  8.4    5.41
12345.67.47.26.5.3.........28.1...353.1.2.78...78..1..7...8...18..6.235..32.1.84.  8.4    5.31
12345.67.47.6..52.5..7..4.334..8..6.68.14.23..12...8.483...67.22..87.3...........  6.6    6.87
12345.67.47....52.5..7..4.334..8..6.68.14.23..12.6.8.483...67.22..87.3...........  6.6    7.28
12345.67.47....52.5..7..4.325.87.3..83...67.2.........34.18.26.68..4..3..12.6...4  7.7    6.03
12345.67.47.26.5.3.........58..1..3.3.15.278..47.8.1..7..8...618..62.3.7.3.1..8..  8.4    5.82
12345.67.47....52.5..7..4.338.14.26.64..8..3..12.6.8.483...67.22..87.3...........  6.6    7.54
12345.67.47.6..52.5..7..4.338.14.26.64..8..3..12...8.483...67.22..87.3...........  6.6    7.13
12345.67.47.36.5.2.........38.1...252...3.78...78..1..81.6.325.7...8...1.32.1.84.  8.4    5.49
12345.67.47.36.5.2.........38.1...252.1.3.78...78..1..7...8...18..6.325..32.1.84.  8.4    5.38
12345.6..46.2.7.....5.364..517.8.24.34.72518..........63.572.1.7...6.....513...6.  7.7    5.77
12345.6..46.2.7.....5.364..517.8324.34.72.18..........63.572.1.7...6.....513...6.  7.7    5.72
12345.6..46.2.7.....5.364..317.8524.54.72.18..........63.572.1.7...6.....513...6.  7.7    5.69
12345.6..46.2.7.....5.364..317.8.24.54.72318..........63.572.1.7...6.....513...6.  7.7    5.67
12345.6..46.2.7.....5.364..317.8.24.54.72318..........65.372.1.7...6.....315...6.  7.7    5.82   
12345.6..46.2.7.....5.364..317.8524.54.72.18..........65.372.1.7...6.....315...6.  7.7    5.67
12345.6..46.2.7.....5.364..517.8.24.34.72518..........65.372.1.7...6.....315...6.  7.7    5.62
12345.6..46.2.7.....5.364..517.8324.34.72.18..........65.372.1.7...6.....315...6.  7.7    5.74
12345.67.4..16.5.2.......4.23..1.86.61.83..25..86.....3.154.28.8.2..145..4..8....  8.4    8.82
12345.6..74.2.65136..7..4..38.6.....46.....31.12.4.8.687.1.23.5.3.57.1.8.........  7.3    5.38
12345.67.45.6.712...7...5..21...436..34.6.81..........54...378.3.27.6.5..7154....  8.9    6.36
12345.67.46...2...5.761.4..21.58.7..7..2.1....35.4....37216..846..82.3.7.......6.  8.4    5.46
12345.67.47.6.21356.....4..2......178.....3...371.....38254.76.74...6583.6.....4.  7.3    4.59
12345.67.47.6.21356.....4..2.7....1.8.....3...3.1....738254.76.74...6583.6.....4.  7.3    3.97
12345.67.47.6.21356.....4..38254.76.74...6583.6.....4.81....3..2.......7.371.....  7.3    5.13
12345.67.4.........7.62.3.438.2.....2.158.73...7.1.8..6.4..2.8..1286.4.3.3.14..6.  8.8    8.67
12345.67.4.........7.62.4.338.2.....2.158.73...7.1.8..6.4..2.8..1286.3.4.3.14..6.  8.8    8.51
12345.67.47...62..5.67...3434...5.6.6.21..3.....6...4283.5.172.2.58.7.13.........  8.9    5.95
12345.6..47.6..1..6.5...43.3.756.28..5..8.36..........54..1.72.7.12.584..32.4..1.  8.9    5.41
12345.6..56.7.........6352.23..4781.8.........1.83.24.68.3.415.3.158..6..5...6.8.  9.0   11.41
12345.6..47.6..1..6.5...43.3.758.26..5..6.38..........54..1.72.7.12.584..32.4..1.  8.9    5.05
12345.67.4..6......6..7243.21.58.36.38.26.1....6....8.84........3172.84...284..1.  8.3   14.49
1234..5..46.17.38...8......6.132.7...37.1426..4...7.3..1624.85..84.5162....8.....  7.8    7.00
12345.67.4..6......6..7243.21.58.36.38.26.1....6....8.84........3274.81...182..4.  8.3   15.46
12345.67.45....1....73...5424..3.78.7.184.32..382...41.1.52.867.7.6...1..........  7.9   10.03
12345.67.56.2..4..4.7.365..25.783.4.3.4..285....54....8..32.76..3.8.......2.6..8.  7.8    9.41
12345.67.46.7.....8.5.364.135..8.71..1.5738...........64.3.51..5...67..4.3.84..6.  7.8    9.10
12345.67.47.........671.3.463.82.1..8..1....6.1.....3.74.28..633.8.7.4.2.6..4.78.  8.3    9.36
12.34.56.35.16.27..........48.5.36...35.1684...148..5.87.6.1.....387..26....3.78.  9.0    6.03
12.34.56.34.6.5..7....284.351.48.7.64.........8..6.1.485.2.63.12..83.6.5.3..5....  8.9   15.15
12345.6..67.2...5...5..63..21.84.73..37.2148..........78..6254..52..486..6.58....  9.0    8.46
12.34.56.35.16.27..........48.5.16...15.3684...348..5.87.6.3.....187..26....1.78.  9.0    5.85
12345.6..47.62.153.......4.24.3.658..5..4.3.1.8.5...6471.26.83.8.........32.8..1.  8.5    6.69
12345.67.46.7..2.55.7....3.23158.4....514..23.........7.281.3.63..6..7....6.7..42  8.5    4.44
12345.67.46....2.55.76...3431284.....4.51.3.2.........63.18..272..7...6..7..6.5.3  8.5    4.03
12345.67.46....2..5.76...3431284..5..4.51.3.2.........63.18..272..7...6..7..6.5.3  8.5    4.08
12345.6..6..7.1.25.....64..56.8.....3.85..2.6.12.675.883.14.7.22.1.738.4.........  8.9    4.95
12345.67.45.7.61....7.3..5.23.6.481.8.........1438..6.3....75..5..8637.1...54..8.  8.8    6.28
12345.67.46.72.5.1.......4.3.65...8..1.83.765.8....1..84....3..6.2.8.41..3124.8..  8.3    5.26
12345.6..4..62.31.........431.76.4.87.48...63....4.17.83..7....2.158.73...72..8.1  9.0    5.97
12345.67.57.1.64....6.37.5.231...74.7..34182..........65..1328.3.....5...125...6.  9.0    8.95
12345.67.57.1.64....6.37.5.231...74.7..34128..........65..1382.3.....5...125...6.  9.0    8.82
12345.67.57.62.41...47..5..2...4.861.1.8...5..........78.....3.3.128.74..4237.18.  7.8    5.87
12345.67.4..3.651..5.......38.6.27..5...4382..12.8..4.8..2......3..6418...183.26.  8.0    5.44
12345.67.4..3.651..5.......23..6418.8..2.......183.26.38.6.27..5...4382..1..8..4.  8.0    5.49
12345.6..57.6.21....6.3..5.3571.684..6.........134.76.7..5.342..32.1457....2.....  8.4    5.36
12345.67.4..3.651..5.......38.6.2.5.5...432...1258..4.83..6412...123.86....8.....  8.4    5.44
12345.67.54.7..2..8.7.3..5.3..5.486...46.351..........41.36.78.7.8.4..2..3.8.71..  8.4    4.79
12345.67.48.6..2..6.7.3..4.2..58..67.7.16..52.........84.3..7..7.184.52...2.1..84  8.4    4.92
12345.67.46...7..27....634.21.7.583..3..8.72..........3526.148.6..54.2.3.4.....6.  7.8    6.44
12345.67.46.7.15....5...4..21.3768.58.651.7.2.........64..3....3.16.72.4...14.3..  8.2    5.67
12345.67.46.7.25....5...4..21.3768.5.8652.7.1.........64..3.....326.71.4...24.3..  8.2    5.72
12345.67.45.6.72....7.3.45.21.3..86..3.86.1...........3417.658.5....37...725...1.  7.2   10.13
12345.67.45.6.71....7.3.54.21.3..86.3..86.2...........5327.648.7.15...2..4...37..  7.2   10.33

The last two, which i found recently, are the easiest. Maybe wapati may like them.

If you dive through the banners, you can download my sets of 41,261 38's and 3,513,474 37's here:
  • sudoku38.zip {broken link removed www4.zippyshare.com/v/69419000/file.html}
  • sudoku37.zip {broken link removed www4.zippyshare.com/v/40576610/file.html}

Not much has changed with my results in the last 4 months. My conjecture, that there is no 40 clue still holds and it became more probable now. Some arguments:

When you know, that only one of 100000 grids has a 17 clue, and it needs weeks to check, if a given grid has a 17 clue, you may resist to try to find one. For 39's things are even worse, probably less than one in 10 mio grids have one.
The reason, why so much 17's and high clues could be found, is that they are highly clustered, i.e. "in the near" of many 18 clues you have much better chances to find a 17. "Near" simply means exchanging only a few givens, denoted as (-n+m) - remove n givens and add m.

Now when there is a 40 clue, we can expect to find a rather dense 37 cluster beneath it. But my search results suggest, that i already found the densest regions.

Since January my program ran this way:
I did (-1+1) on my current set of new 37 clue puzzles, as long i found new ones, and -2+2 on the resulting sets. The puzzles, which dont have a -1+1 neighbour, were added to the "unexpanded" set, i.e. the collection, i have not done a -2+2 yet (this set steadily became larger, more than 1/2 a mio at the end). This was repeated, until less than 1000 -1+1 puzzles were generated.
Then i added the 10000 puzzles with highest weights from the unexpanded set to the current set and continued.

Parallel i generated new sets of 37's bottom up from random 27's (also preferring those with higher weights, when the sets for the -1+2 were too large). These sets were added to the current set of 37's above (after removing duplicates). This way in 35 runs more than 35000 puzzles were generated.

It turned out that with ongoing search i needed more and more 37's to find a new 39. While in "good times" this were 30000, i needed 330000 for the last two. I tried to extrapolate by dividing the 37's into 2, 3 or 4 parts. In all cases the result was, that also if continuing forever i would not find more than 150 39's.

Why is it unprobable, that there are huge 37 clusters with a 39, which i never touched ? Already with the first gotchi's i noticed, that after several (-2+2)'s there were more and more duplicates between different gotchi's. This was the reason, why i had to make a union to avoid double computations. All of them had a strong trend to the same known clusters/regions.
At the end i repeated the experiment with the most promising bottom-up set. It had 2040 puzzles (i.e. a dense set, because the average was 1000) and no duplicates (on average i got about 1% dups, more for larger sets). After a -1+1 i already found 11 new 38's. But with 23 (-2+2)'s the first 8 dups popped up. After 37 (-2+2)'s already 70% of the newly generated 37's were duplicates of known 37's. After that i removed known puzzles from the "new" 37's and continued up to 64 (-2+2)'s.
What i had at the end were 47459 37's/304 38's, where 29662/218 were new, which gives a ratio of 734 38's per 100000 37's. (The numbers of new 37's did not show a trend up- or downwards, never reached 1000).

In the same time my main gotchi found 42516 37's/472 38's. i.e. 1110 38's per 100000 37's.

So though i cant say, how much of the extra gotchi's puzzles belong to known clusters, it is clear, that the explored regions are worse than the known ones.


Also my estimated curve of the overall distribution did not change much. It is now based on this table.
Code: Select all
#clues    puzzles/grid       puzzles total     log()
19        2.28342e+003       1.07e+13          13.1
20        3.2221e+006        1.76e+16          16.23
21        1.2910e+009        7.065e+18         18.85
22        1.6152e+011        8.84e+20          20.946
23        6.9042e+012        3.778e+22         22.577
24        1.0647e+014        5.83e+23          23.765
25        6.2480e+014        3.4193e+24        24.533
26        1.4855e+15         8.13e+24          24.91
27        1.5228e+15         8.34e+24          24.92
28        7.2063e+14         3.94e+24          24.60
29        1.6751e+14         9.17e+23          23.96
30        1.9606e13          1.07e+23          23.03
31        1.22849e+012       6.20e+21          21.8275
32        4.44203e+010       2.24e+20          20.386
33        9.26177e+008       4.97e+18          18.704
34        1.35441e+007       7.41e+16          16.84
35        1.06190e+005       5.81e+14          14.65

It is the last copy i have about the distribution, where the entries between 21 and 28 are by Red Ed and Denis Berthier, 20 and 29-31 by Red Ed and the most recent ones for 19 and 32-35 by ano1 (calculated with a variation of Red Ed's sub/superset algorithm). For the 35's he had found about 1.5 times more puzzles (with relative error of i think 30%) than i had expected (based on calculations up to 32), also the number of 19's increased by about 15%.

I added an estimate of 50000 puzzles for the 17 clues and my new guess of only 300 minimals with 39 givens.
Then i tried to get a smooth curve again.

Image

In my set of 38's there are some symmetrical ones, 6 with diagonal symmetry
Code: Select all
..........64..9.23.97.324.6....138....92...14.819..3.2..83.6.41.1..2.6.8.46.9123. SER 9.0
...........9.32.46.46..92.3....13.8..9.2..1.4.189...32..1.2..68.8.3.64.1.64.91325 SER 9.0
...........9.32.46.46..92.3....13.8..9.2..1.4.189.7.32..1.2..68.8.3.64.1.64.9132. SER 8.9
.....9....92.8..51.175.28.9..4..651..6.8....47.1..56.8..69.4.8..4.2..9.6.79.68.45 SER 9.0
.....9....92.8..51.175.28.9..4..651..6.8....47.1..56.8..69.4.8..4.2..9.6.79.68.45 SER 9.0
........5.23..546..5624.38...2..4.7...7.23.46.6.79.....79....54.3547.6986...5.73. SER 7.7

and one with 180° rotational symmetry
Code: Select all
..5...6.131.....757961.5.43.....346.6..2.9..7.734.....43.5.172616.....545.7...1.. SER 7.7

This one is interesting for an exotic solving technique, so i restored it in this thread.
eleven
 
Posts: 3121
Joined: 10 February 2008

Re: High clue tamagotchis

Postby coloin » Fri May 28, 2010 10:13 am

Excellent work.

Im still thinking about the common equivalent clues in all these 39s......... hmmm.

The clue distribution stats shows how we shouldnt have been surprised at finding so many 19s [but no 18] in one random grid. It also shows that indeed most grids will probably have at least a 35.

Incidently - have we lost "max no of clues" and "max no of clues 2" - I cant find it ?

We have also lost anon17's symmetrical 36

Perhaps we need a thread for important lost posts ?

C
coloin
 
Posts: 2456
Joined: 05 May 2005
Location: Devon

Postby Pat » Sun May 30, 2010 7:14 am

coloin wrote:
have we lost "Max number of clues" and "Max number of clues 2" - I cant find it ?

    i've inserted URLs in the above -- is there a problem ?


    ( off-topic )
    coloin wrote:We have also lost ano1's symmetrical 36

    now recovered from my notes
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re: High clue tamagotchis

Postby eleven » Sun May 30, 2010 7:44 pm

coloin wrote:Im still thinking about the common equivalent clues in all these 39s......... hmmm.

Hi Coloin,

i guess its a very hard job to find out a maximum set of common clues of all 81 puzzles with equivalents. Personally i dont even have a correct program to do it for a pair (dont know, if gsf's program can). But for a start - can someone calculate it for those 3 puzzles, which i think have pairwise few common clues (should be 18,19) ?
Code: Select all
.2..5..89..6.8912...92.1.....7.94..8.451.8.9..9.57.41..74812..........4..62.45871
....5..8..5718.23668.73215....5..8....581.96286.92751.....7.3.1....9..2..3.2.1...
.....6.....718...66.8.73.152.6.4157.78..2...4.45.6..2...4......5..718.42872.34.51
eleven
 
Posts: 3121
Joined: 10 February 2008

Re: High clue tamagotchis

Postby ronk » Sun May 30, 2010 9:33 pm

eleven wrote:
coloin wrote:Im still thinking about the common equivalent clues in all these 39s......... hmmm.

i guess its a very hard job to find out a maximum set of common clues of all 81 puzzles with equivalents. Personally i dont even have a correct program to do it for a pair (dont know, if gsf's program can). But for a start - can someone calculate it for those 3 puzzles, which i think have pairwise few common clues (should be 18,19) ?
Code: Select all
.2..5..89..6.8912...92.1.....7.94..8.451.8.9..9.57.41..74812..........4..62.45871
....5..8..5718.23668.73215....5..8....581.96286.92751.....7.3.1....9..2..3.2.1...
.....6.....718...66.8.73.152.6.4157.78..2...4.45.6..2...4......5..718.42872.34.51

gsf's program will find a "maximum similarity" on a pairwise basis with the -CSf option. The 'f' specifies that all comparisons be made against the 1st puzzle in a file. The result for the above is ...
Code: Select all
similarity 19
.2..5..89..6.8912...92.1.....7.94..8.451.8.9..9.57.41..74812..........4..62.45871
62..54789.....64..4.92876.57......58.....81.....57.9....48125.6....6...426..45891
similarity 22
.2..5..89..6.8912...92.1.....7.94..8.451.8.9..9.57.41..74812..........4..62.45871
.2165978.675.8.91......1....17.94.68.4.1.8.9..9.56.1....4......75...64...62.4587.

As I understand it, the 2nd and 3rd puzzles are sequentially morphed and compared to the 1st to obtain the maximum similarity on a pairwise basis. For comparison of the 1st and 2nd, therefore, there are 19 common clues. The 1st puzzle is output unmorphed and the 2nd morphed. Ditto for the comparison of the 1st and 3rd, for which there are 22 common clues.

AFAIK, the program can't find clues common to all three puzzles.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: High clue tamagotchis

Postby eleven » Mon May 31, 2010 2:06 pm

Thanks Ron,

but you dont tell me, that you read that out of gsf's man page ? This program really cries for an own thread "gsf sudoku for dummies" :)

Anyway it is very fast (for this job). With a simple script i compared the 82 39's pairwise in a few hours.

On average there are only 22.53 common clues for a pair of known 39's, so for an av. pair you would need a {-16+16} or {-17+17} to get from one to the other.

The smallest similarity is 19 common clues, there are 21 pairs, all with the 3 puzzles, which uncommonly have a box with a single clue, the 2 latter also at least 2 clues in each row/column:
Code: Select all
.2.4...8.4.6.8......9..2...268.41.75..1..7....4752861..742951..692.14.57.1..7....
....5..8..5718.23668.73215....5..8....581.96286.92751.....7.3.1....9..2..3.2.1...
....5..8..5718.23668.73215....5..8....581.96286.92751.....7...1...39..2..3.2.1...

There are 315 pairs with 20 common clues.

For fun:
Comparing a 17 clue with 3 39's each gave 10 common clues. So with a {-7+29} you can get from a 17 clue to a 39. These are less clue changes than you have with the {-20+20} to get from one 39 to the other when they have 19 common clues.

Btw Havards first 39 (which i did not find) has 27 common clues with my "nearest" puzzle.

Clusters of 39's:
Code: Select all
similarity 34-38
1.3.5678.4..78.1..7.8.13.642.587..46..4.3587...76.4.5.3.2...61.5.136.............
1.3.5678.4..78.1..7.8.13.642.587..46..4.3587.8..6.4.5.3.2...61.5.136.............
1.3.5678.4..78.1..8.7.13.642.587..46..4.3587.7..6.4.5.3.2...61.5.136.............
1.3.5678.4..78.1..8.7.13.642.587..46..4.3587...86.4.5.3.2...61.5.136.............
1.3.5678.4..87.1..7.8.13.642.578..46..4.3587...76.4.5.3.2...61.5.136.............
1.3.5678.4..87.1..7.8.13.642.578..46..4.3587.8..6.4.5.3.2...61.5.136.............
1.3.5687.4..78.1..7.8.13.642.587..46..4.3578...76.4.5.3.2...61.5.136.............
1.3.5687.4..78.1..7.8.13.642.587..46..4.3578.8..6.4.5.3.2...61.5.136.............

1.34.67.94..1.9..6.96.37....198..5..3.89.54..5.47139.8...........13..6.5.356.1.4.
1.34.67.94..1.9..6.96.37..4.198..5..3.89.5...5.47139.8...........13..6.5.356.1.4.
1..4.6..94.31.97.6.9..37..4.198..5..3.89.5...5.47139.8...........13.86.5.356.1.4.
4.31.67.91..4.9..6.96.37..4.198..5..3.89.5...5.47139.8...........13..6.5.356.1.4.
4.31.67.91..4.9..6.96.37....198..5..3.89.54..5.47139.8...........13..6.5.356.1.4.
similarity 35-38
..34..7..45.78..2.78..2346..38.9.64.6..3.895.9........37.8..29..9...2.7.8.297.53.
..34..7..45.78..2.78..2346..38.9.64.6..3.895.9.........7.8..29..9..32.7.8.297.53.
..34..7..45.78..2.78..2346..38.9.64.6..3.895.9.........7..32.9..9.8..27.8.297.53.
..34..7..45.78..2.78..2346..38.9.64.6..3.895.9........39.8..27..7...2.9.8.297.53.
similarity 38
12.45678..5718.2..6..2.71..21.........651.92.8956.2.1..7..6..9.56.9..87.9....5...
12..5678..5718.2..6..2.71..21........3651.92.8956.2.1..7..6..9.56.9..87.9....5...
12..5678..5718.2..6..2.71..21.........651.92.8956.241..7..6..9.56.9..87.9....5...
similarity 36-37
.2.4...8.4.6.8......9..2...268.41.75..1..7....4752861..742951..692.14.57.1..7....
42.....8...64......89..2...268.41.75..1..7....4752861..742951..692.14.57.1..7....
42.....8...648......9..2...268.41.75..1..7....4752861..742951..692.14.57.1..7....
similarity 35-36
1234.6..94..1.923..........2319.4.585.4....2..895..4.33.56.18.28....539...28....5
1234.6...4..1.923..........2319.4.585.4...92..89..54.33.56.18.28..5..39...2..8..5
1234.6..94..1.923..........2319.4.585.4....2..89..54.33.56.18.28..5..39...2..8..5

Additionally there are 11 pairs within (-4+4)
eleven
 
Posts: 3121
Joined: 10 February 2008

Re: High clue tamagotchis

Postby dobrichev » Sat Sep 04, 2010 9:51 pm

If there is no bug in my program, the Hamming distance between the following two puzzles is <= 5.
[EDIT: There was a bug and the result is INCORRECT. See the posts below.]
Code: Select all
123056089050009206609000015206000050015030607930065028301007002002093871000000000
003400700450780020780023460038090640600308950900000000070800290090032070802970530

Found by transforming the first puzzle into an isomorph of the second by 1) relabeling 3 of the clues, 2) removing 1 of the rest of the clues, and 3) adding 1 new clue on a new place.
Didn't stored information for the exact transformations. It took ~2 hours. Can repeat and obtain transformations if there is interest.

MD
Last edited by dobrichev on Sun Sep 05, 2010 8:44 pm, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1859
Joined: 24 May 2010

Re: High clue tamagotchis

Postby gsf » Sun Sep 05, 2010 5:19 am

dobrichev wrote:If there is no bug in my program, the Hamming distance between the following two puzzles is <= 5.
Code: Select all
123056089050009206609000015206000050015030607930065028301007002002093871000000000
003400700450780020780023460038090640600308950900000000070800290090032070802970530

Found by transforming the first puzzle into an isomorph of the second by 1) relabeling 3 of the clues, 2) removing 1 of the rest of the clues, and 3) adding 1 new clue on a new place.
Didn't stored information for the exact transformations. It took ~2 hours. Can repeat and obtain transformations if there is interest.

these two puzzles are not isomorphic
so how can you "transform the first puzzle into an isomorph of the second"?

all of the hamming/similarity discussions on the players and programmers forums
only allow the 9 sudoku transforms (or their equivalent)

for these two puzzles I get minimum distance 29 maximum similarity 21
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: High clue tamagotchis

Postby dobrichev » Sun Sep 05, 2010 8:05 am

gsf wrote:these two puzzles are not isomorphic

Yes, they are not isomorphic.
gsf wrote:so how can you "transform the first puzzle into an isomorph of the second"?

By applying transformations which are not validity-preserving. Each transformation leads to a new, not necessarily valid puzzle.
gsf wrote:all of the hamming/similarity discussions on the players and programmers forums only allow the 9 sudoku transforms (or their equivalent)

9 sudoku validity-preserving transformations, which is not the case.

Here is an example for first iteration.
Take the puzzle
123056089050009206609000015206000050015030607930065028301007002002093871000000000
Take the first given (1 at r1c1).
In a loop replace the given 1 at r1c1 with 2,3,4,5,6,7,8,9.
223056089050009206609000015206000050015030607930065028301007002002093871000000000
Check for validity and minimality, but do not ignore invalid puzzles generated at this step.
In an inner loop, take the next given (2 at r1c2) and do the same.
233056089050009206609000015206000050015030607930065028301007002002093871000000000
In an inner loop, take the third given (3 at r1c2) and do the same.
234056089050009206609000015206000050015030607930065028301007002002093871000000000
In an inner loop, remove, one at a time, all the givens except these 3 relabelled in the outer loops.
234006089050009206609000015206000050015030607930065028301007002002093871000000000
In an inner loop, add a clue in each empty position, one at a time, assigning all possible digits.
234106089050009206609000015206000050015030607930065028301007002002093871000000000
Check the puzzle for validity and minimality. Ignore invalid and non-minimal puzzles.
Canonicalize and print the puzzle.

There are 9 nested loops - position and value for first, second, and third relabeling, position to remove, position to add, value to add. And it is slow and took > 5 hours to process the above puzzle.
The second puzzle was printed twice, so there are 2 different ways to transform the first to an isomorph of the second by applying these non-preserving transformations.
dobrichev
2016 Supporter
 
Posts: 1859
Joined: 24 May 2010

Re: High clue tamagotchis

Postby Red Ed » Sun Sep 05, 2010 8:31 am

gsf wrote:for these two puzzles I get minimum distance 29 maximum similarity 21

I think I recall sending you some code for this problem. I just tried mine, and it has a bug. If I put the puzzles one way round I get 29/21 like you; the other way round, I get 30/21.

Did I send you code? And, if so, did you manage to find and correct the bug?

EDIT: bug found & zapped. The problem was with the previous version of the line that is now
Code: Select all
        tscore += ((gpermed[i][j]==0) ^ (gtarget[i][j]==0));
The code I sent you (if I sent any) may not even have had tscore in it, in which case it would not have the bug.
Last edited by Red Ed on Sun Sep 05, 2010 9:28 am, edited 2 times in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: High clue tamagotchis

Postby Red Ed » Sun Sep 05, 2010 8:46 am

dobrichev wrote:Can repeat and obtain transformations if there is interest.

Yes please.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: High clue tamagotchis

Postby ronk » Sun Sep 05, 2010 12:36 pm

dobrichev wrote:
gsf wrote:all of the hamming/similarity discussions on the players and programmers forums only allow the 9 sudoku transforms (or their equivalent)

9 sudoku validity-preserving transformations, which is not the case.

I agree with your usage of the Hamming distance term, as my terse 2007 post implies.

A percentage of 39s, maybe even a significant percentage, were found with "neighborhood searches" of known 39s, as with -go{-4+4} using gsf's program. Were none or only one of two such neighbors subsequently (iso)morphed, I believe gsf's -C option would find the correct Hamming distance. However, when both are morphed, as with canonicalization, the probability of its finding the correct Hamming distance may be quite low.

dobrichev, many of the 39s are not close neighbors. What caused you to choose this close pair :?:

Red Ed wrote:
dobrichev wrote:Can repeat and obtain transformations if there is interest.
Yes please.

I'm interested as well.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: High clue tamagotchis

Postby gsf » Sun Sep 05, 2010 3:36 pm

Red Ed wrote:
gsf wrote:for these two puzzles I get minimum distance 29 maximum similarity 21

I think I recall sending you some code for this problem. I just tried mine, and it has a bug. If I put the puzzles one way round I get 29/21 like you; the other way round, I get 30/21.

Did I send you code? And, if so, did you manage to find and correct the bug?

EDIT: bug found & zapped. The problem was with the previous version of the line that is now
Code: Select all
        tscore += ((gpermed[i][j]==0) ^ (gtarget[i][j]==0));
The code I sent you (if I sent any) may not even have had tscore in it, in which case it would not have the bug.

you sent me your Munkres Hungarian Algorithm implementation (you are in the CONTRIBUTORS credits listed by --man)
I modified it to fit in with my solver distance() function that computes either distance or similarity between two grids
can you post the two pairs that exposed your bug
I'll check with mine
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: High clue tamagotchis

Postby Red Ed » Sun Sep 05, 2010 3:54 pm

It's really only my port of someone else's code.

The old version of that now-fixed line of code was something like:
Code: Select all
        tscore += ((gpermed[i/9][i%9]==0) ^ (gtarget[i/9][i%9]==0));

I look forward to MD's next post. I he'll have a bug that is bigger and hairer than the tscore one ...
Red Ed
 
Posts: 633
Joined: 06 June 2005

Next

Return to General