The New Sudoku Players' Forum

by **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).

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

by **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.

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.

by **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

by **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 ?

off-topic

coloin wrote:We have also lost ano1's symmetrical 36

recovered

by **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

by **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.

by **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)

by **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

by **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

by **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.

by **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.

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

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

Yes please.

by **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.

by **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

by **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 ...

The New Sudoku Players' Forum

High clue tamagotchis

High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis

Re: High clue tamagotchis