[Magictour] Re: Bounds

>64 07 62 05 60 03 58 01
00 00 00 00 00 00 00 00
08 63 06 61 04 59 02 57
>but are you starting with 64 ?

Yes, we start with 64, and decrement at every jump.
You can also view the problem as starting with 1, and getting the smallest
possible sum:
01 00 03 00 05 00 07 00 -> sum=1+3+5+7
00 00 00 00 00 00 00 00
00 02 00 04 00 06 00 00

We can get:

01 00 03 10 05 00 07 00 -> sum=1+3+5+7+10=26
00 00 00 00 08 00 00 00
00 02 09 04 00 06 00 00

01 00 03 10 05 00 07 12 -> sum=1+3+5+7+10+12=38
00 00 00 00 08 11 00 00
00 02 09 04 01 06 00 00

01 00 03 10 05 14 07 12 -> sum=1+3+5+7+10+12+14=52
00 00 00 00 08 11 00 00
00 02 09 04 01 06 13 00

Are 26, 38 and 52 the lowest possible sums with 3,2 and 1 empty square ?

If yes, these values will speedup the search !

>Completable means to me, that the empty squares can be filled later
with numbers bigger than the largest number in the row.
>to solve(approximate) it numerically,
>you could try to generate all SMKTs where you ignore the sums of the
columns
>and then find the maxima with 3,2,1 of all their rows.
>It should be sufficient to generate a lot random such {rows=260}-tours

Of course, finding the best sum with real tours is great, but can you prove
that your MonteCarlo method is correct ?

>do you have an estimate, how long it will take ?

I have no idea for the moment !
I think we need more computation results from Hugues, in order to define the
best strategy to find one.

Perhaps can we start with a closed tour (which one ?), or is there a special
first move to be sure to get at least one solution in reasonable time ?

Perhaps the start/end approach is not the best way to work on this problem ?

JC


Magictour mailing list
To unsubscribe: mailto:magictour-request@ml.free.fr?subject=unsubscribe
To mail to the mailing list: mailto:magictour@ml.free.fr


Received on Thu Dec 04 14:24:18 2001