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 optimization-based 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 issue-65 installment is about how integer programming can be used to solve Paint-by-Numbers 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:

 0 1 2 3 4 5 6 7 8 9 0 2 4 3 3 4 5 2 5 4 1 1 1 1 0 1 1 0 1 1 2 4 2 3 3 4 4 2 4 4 3 5 2 4 3 4 5 2 5 4 4 5 2 4 3 4 5 2 5 4 5 4 1 4 3 2 4 1 4 3 6 4 1 4 3 2 3 1 4 3 7 5 2 4 3 3 4 5 5 4 8 5 2 4 3 3 4 5 2 4 9 5 2 4 3 3 4 5 2 5

The number n in the position (row, column) = (a, b) means that a touches n squares of b, if b follows a in the sequence.
Since that a sequence is a noncircular list of the numbers 0...9, every sequence can be marked on the table marking the corresponding crosspoints on the table. As example, just take the given sequence 0 1 2 3 4 5 6 7 8 9:

 0 1 2 3 4 5 6 7 8 9 0 2 4 3 3 4 5 2 5 4 1 1 1 1 0 1 1 0 1 1 2 4 2 3 3 4 4 2 4 4 3 5 2 4 3 4 5 2 5 4 4 5 2 4 3 4 5 2 5 4 5 4 1 4 3 2 4 1 4 3 6 4 1 4 3 2 3 1 4 3 7 5 2 4 3 3 4 5 5 4 8 5 2 4 3 3 4 5 2 4 9 5 2 4 3 3 4 5 2 5
You can immediately figure out two obvious facts:

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:

0x2 + 1x(2+1) + 2x(1+3) + 3x(3+3) + 4x(3+4) + 5x(4+4) + 6x(4+1) + 7x(1+5) + 8x(5+4) + 9x4 = 277

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:

2x(0+1) + 1x(1+2) + 3x(2+3) + 3x(3+4) + 4x(4+5) + 4x(5+6) + 1x(6+7) + 5x(7+8) + 4x(8+9) = 277

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 optimum-bounded strategy. Obviously you could use the table to build up a tableau of an LP01 problem; more quickly, you could try to find the best-fitting 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 sequence-top, 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 home-made 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

 0 1 2 3 4 5 6 7 8 9 0 2 4 3 3 4 5 2 5 4 1 1 1 1 0 1 1 0 1 1 2 4 2 3 3 4 4 2 4 4 3 5 2 4 3 4 5 2 5 4 4 5 2 4 3 4 5 2 5 4 5 4 1 4 3 2 4 1 4 3 6 4 1 4 3 2 3 1 4 3 7 5 2 4 3 3 4 5 5 4 8 5 2 4 3 3 4 5 2 4 9 5 2 4 3 3 4 5 2 5
I'm not sure that 347 is the maximum.

Anyway, the following LP01 problem should find it. The term xi,k = 1 or 0 indicates if the crosspoint (i, k) is marked or not, while ti,k is the number on row i, column k of the table.

max ?i=0…9 ?k=0…9,k?i xi,k ti,k (i+k)

?i=0…9 xi,k = 1, k=0…9

?k=0…9 xi,k = 1, i=0…9

xi,i = 0, i=0…9

xi,k in {0,1},   i, k=0…9, k?i

Bye!