[Magictour] Re: pandiagonal

>that's McKay,BTW., not to be confused with our Mackay.
>And he only counts the closed tours, so that's just one of our
>136 ranges. He gets 1.3e13 tours , with our 200 cycles
>per knight-move that would be 2.6e15 cycles or 30 days.
>But that's only for the maximum nodes in the tree.
>Fei Lu gets 4e4 tours per second with 300MHz , so that's
>1.3e5/s*GHz or 1 year with a 3GHz Computer, so it's doable.
>Hmm, maybe Fei Lu is counting open tours too, I'll have to check.
>Anyway... JC, Hugues , is that a project for us ?!?

It may be.
Fei Lu used a trick to reduce the number of nodes, because of some
properties of closed knight tours.
I already implemented it, and could possibly add it to my ASM generator.
Since no closed magic tour on 12x12 is known to this date, I suggest that we
put our efforts on enumerating all semi-regular closed 12x12 magic tours.
However, my first tests show that enumerating them is pretty slow, even
though the same program solved the 136 start-end semi-regular magic tour in
3 minutes (I can post the program if someone is interested).
Having a long running time leads to the problem of saving the computation
state, since when you shut down your computer, all computation is lost. This
is why we need to find a way to either add other constraints, or split the
computation ranges into smaller computation ranges. I'm open to any idea.

One day, I'll start the writing of a database which will enumerate the first
jumps, and every client will connect to this database, get one or more
starting tours, compute them and return them to the server.
This way, we can really finetune the program so that a range takes a given
amount of time !
(This is a lot of work !)
Perhaps will I write this server for the non-crossing knight tour problem
first, then use it for the tours enumeration.
This way, we could enumerate all possible 8x8 tours.

> John Beasley, in an afterthought to a recent e-mail writes:
>
> Here's a thought. A pan-diagonal nxn square must satisfy 4n constraints,
> which goes up linearly with n. The number of knight's tours on an nxn
board
> goes up (I would think) by something not too far short of factorial-n.
Does
> there exist a suitably huge N such that a knight's tour forming a
> pan-diagonal magic square is possible?
>
I think that a pandiagonal magic square may exist on the 12x12 board, and
DOES exist on the 16x16 board.
Enumerating regular 12x12 magic squares will surely lead to interesting
discoveries in this area.
16x16 is currently too big to compute in reasonable time, except if we find
good constraints.

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