Claaudio Baiocchi  The best minimum value is 181, given only by the rearrangement 8305426719.
Patrick Hamlyn  Min score 181 from 8 3 0 5 4 2 6 7 1 9.
Dick Saunders Jr.  7 0 8 9 6 2 4 5 3 1 Gives a score of 336.
Evgeni Lukin  The sequence is 7809624531. The sum is 344 .
Jeffrey Gosselin  4862539071 =346
Danny Potts  4986253701 which should total 348... I *think* that's as good as it's getting... I've tried a few moves to use up the free 5 segment, but I always end up losing in the long run... In the grand tradition of Florida, I'll amend my results if need be :)
Mike Shafer  The best case I've found so far is 3450798621 which gives a total of 348. I'll see if I can do better in the near future.
Dan Hennessy  The (unique) answer to the optimization problem with the graphical display of the digits 0 through 9 is: 0 7 5 3 4 9 8 6 2 1 scoring 352 points. Well, unless my program is broken. Knowing the way I code, this seems likely. ;)
Tom Turrittin  I just got a better result. I'm doing this all manually. :) 0476298531 comes to 352.
Juha Saukkola  352 ['0', '7', '5', '3', '4', '9', '8', '6', '2', '1']
Brian Deane  352
Dane Brooke  Best value I have found is 352 for sequence 0753498621. I find it somewhat annoying that the optimal sequence begin with zero; counterintuitive. O, well.
Ken Bateman  0753498621 0x2 + 1x2 + 2*6 + 3*6 + 4*7 + 5*7 + 6*9 + 7*6 + 8*10 + 9*9 = 352. It's unique.
Roger Phillips  Assuming the digits must be arranged in a row
as shown, the best score I've found is for 0753498621, as follows:
0x2 + 7x6 + 5x7 + 3x6 + 4x7 + 9x9 + 8x10 + 6x9 + 2x6 + 1x2 = 352
Patrick Hamlyn  A quick & dirty program takes about 2 seconds
to find the highest scoring sequence: Max score 352 from 0 7 5 3 4 9 8 6 2 1
The obvious extension is to find the lowest scoring sequence: Min score 181
from 8 3 0 5 4 2 6 7 1 9 Both are unique. Slightly harder is to find the median
score(s). When I get my upgraded 'puter up and running I'll sort the list of
scores, which is 100MB and too large for my backup machine.
Bob Bosch  First, I'd like to say that I love your web page! I discovered
it a couple of months ago, and I've been visiting it regularly ever since.
I write an optimizationbased recreational mathematics column for Optima, the
newsletter of the Mathematical Programming Society. If you are interested,
point your browser to http://www.ise.ufl.edu/~optima/ and check out issues 60
through 64. The column is called Optima Mindsharpener. (Incidentally,
the issue65 installment is about how integer programming can be used to solve
PaintbyNumbers puzzles. I learned about these puzzles from your page!)
The second reason I'm writing is to submit solutions to the 0123456789 optimization
puzzle offered by Cihan Altay. I really liked this puzzle. By the
way, the solution presented on your page has value 277, not 271. (The number
6 touches 5 squares from other numbers, not 4.)
I used integer programming to solve two versions of the puzzle: a "5x tiles"
version (in which each number is viewed as a 5x3 tile) and a "polyominoes" version
(in which each number is viewed as a polyomino, allowing for the pairs 1,4 and
1,7 to be "compressed"). The solutions are as follows:
5x3 tiles version  0753498621 value = 352
***000***000*
*000***000*** 0
* *0 0* 0* *0 0* *0
*00
* * 0***000***000***000*** 0
* * 0 * 0 * 0* *0 0*
0
*** 0***000 *000***000***000
0*2 + 1*2 + 2*6 + 3*6 + 4*7 + 5*7 + 6*9 + 7*6 + 8*10 + 9*9 = 352
polyominoes version 1762453980 value = 364
*000***000*
*000***000***000
**0 0* 0* *0 *0 0*
*0 0
* 0***000***000***000***0 0
* 0* *0 * 0
* 0* *0 0
*** 0***000 *000***000***000
0*5 + 1*2 + 2*7 + 3*7 + 4*7 + 5*7 + 6*9 + 7*7 + 8*10 + 9*9 = 364
One possibly interesting variant of the puzzle would be to place the 5x3 tiles
that correspond to the numbers 1 through 9 on a 3x3 board in such a way as to
maximize the weighted sum. Each cell of the board would hold a single 5x3 tile.
A polyomino version could be constructed too.
Nick Baxter  Attached are 3 solutions. The first is a somewhat
conventional solution with 404. The second is my best solution with numbers
turned sideways (not disallowed) with 419. The third is my best "minimal" solution,
with 126.
Luc Kumps  One can obtain 432 from these two: 1 7 5 3 4 9 8 0 6 2  1 7 5 3 4 9 0 8 6 2 (0 and 8 have the same "borders", and therefore they can be exchanged anytime)
Koshi Arai  My unassured answer is [4539807621].
Hi
Ed, I'm the same as fairfax a few weeks ago, my name's Greg Dulli.
The 0 1 2 3 4 5 6 7 8 9 sequence gave 277 as result. I've found a sequence which
result is 347 "points":
0 7 8 9 6 2 5 3 4 1
I'm not sure it's the optimum but I'll spend some words explaining how
I did proceed. Just take a look at the following table:
















































































































































































































































1. there are no rows/columns with more than one MC (=marked crosspoint), and that's because every number is followed by/follows not more than another;
2. the MCs are nine, since that the list is noncircular. This means that there's a row with no MCs à the one of the last number of the sequence; and a column with no MCs à the one of the first.
Facts 1 & 2 are found in every possible sequence.
How to obtain the result of a sequence form the table and the MCs? For example, in the given sequence, "2" touches 4=1+3 squares, and you can find 1 and 3 respectively on the "2" column (when "2" is the number on the right of) and on the "2" row (when "2" is on the left).
Proceeding this way, you easily find the result:
There is also a dual way to calculate the result: just multiply every MC by the sum of its row and its column, and then add the nine partial results. This is because the MC (a, b) = n indicates that a and b touch one another in n squares, which must be considered both in the "a" and in the "b" terms above, as shown in the two examples in red and blue.
Again we have the same result:
You can see that every number appears twice between parenthesis, except, of course, for the first and the last number of the sequence.
This second way helps you better to find an heuristic optimumbounded strategy. Obviously you could use the table to build up a tableau of an LP01 problem; more quickly, you could try to find the bestfitting sequence catching the most appropriate MCs. For example, the following MC:
(9, 8) = 5
is particularly "inviting", because it gives you 5x(9+8) = 85 "points".
Two good tips are the following:
· leave "1" at the end, so that you won't have MCs on its row, which is the one with the lowest "scores";
· since that multiplying by 0 is a "loss of points", choose "0" as the sequencetop, so that you'll only multiply it by the MC on the "0"row.
Any number you'll choose as the first, you'll erase the corresponding column, since that no MC can be put on that one. For similar reasons, any time you locate a MC = (r, c) you'll erase all the crosspoint on row r and on column c.
Other tips:
· if you've begun with "0" and you decide to continue for example with "7", after deleting "0"column, "0"row and "7"column, choose the column c so that:
(7, c)x(7+c)
is maximized. In this case c = 8 à erase "7"row and "8"column à choose c = 9 to maximize the term (8, c)x(8+c) and so on.
(notation (r, c) indicates the crosspoint on row r, column c.)
· If you've chosen "1" to be the last of the sequence, never select it until you're forced to.
It is very important to proceed sequentially in order to avoid cycles like in the following cases:
· you choose both (8, 9) and (9, 8);
· you choose "0" as first, "1" as last and the MCs (2, 1), (6, 2), (5, 3), (3, 4), (4, 5), (8, 6), (0,7), (9, 8), (7, 9). You obtain no valid sequence from these MCs because (5, 3), (3, 4) and (4, 5) make a cycle.
With this homemade heuristics I found the sequence I told you about at the beginning:
0 7 8 9 6 2 5 3 4 1
which result is 347 (see the following page).
0
7 8 9 6 2 5 3 4 1 347
























































































































Anyway, the following LP01 problem should find it. The term x_{i,k} = 1 or 0 indicates if the crosspoint (i, k) is marked or not, while t_{i,k} is the number on row i, column k of the table.
max ?_{i=0…9}_{} ?_{k=0…9,k?i}_{ }x_{i,k} t_{i,k} (i+k)
?_{i=0…9}_{ }x_{i,k }= 1, k=0…9
?_{k=0…9}_{ }x_{i,k }= 1, i=0…9
x_{i,i }= 0, i=0…9
x_{i,k }in {0,1}, i, k=0…9, k?i
Bye!