[Magictour] Re: private mailing list

Tim,


please look at

http://magictour.free.fr/knight.c

Fei Lu's program describes the algorithm and should be adaptable
for other similar problems.



For the general magical-leaper-tours problem
I'd like a program, which reads a graph G with vertexset V={1..n}

and boundfunctions ub:V-->|N and lb:V-->|N
and coordinate functions ("projections") c : V --> |N*d (d="dimensions")

and then searches for all paths p(1)..,p(k) which satisfy

lb(|{v,c_j(p(v))=x}|) <= SUM {v,c_j(p(v))=x} <= ub(|{v,c_j(p(v))=x}|)

for all j in {1..d}
for all x in {1..k}


{v,c_j(p(v))=x} can also be written as c^-1(x,j) or M(x,j) , which
is really a M(n,p,c,x,j) since it depends on all those parameters.
Then the condition reads :

lb(|M(x,j)|) <= SUM M(x,j) <= ub(|M(x,j)|)


the bounds can also depend on the pathlength k ,
so are functions V*V-->|N


in fact, we require this condition for all subpaths
p(1),..,p(s) of p(1)..,p(k) with s<=k ,
so that we can build all valid {k+1}-paths from all valid k-paths


sounds complicated, but for the computer it should read
just as the actual magical-tour program, only with
some "x" replaced by "f[x]" with additional parameters f.
The speed shouldn't change.



Guenter


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