Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 A Divide-and-Conquer Algorithm for
the Knight's Tour Problem
A Divide-and-Conquer Algorithm for
the Knight's Tour Problem
We present a new
divide-and-conquer algorithm that constructs a
knight's tour for all even n> 6,
variants of which can be used
to construct quadrisected knight's tours for all even n> 12,
tours that are invariant under a 180 degree rotation for all
even n> 8,
and tours that are invariant under a 90 degree rotation for all
n> 10 congruent to 2 modulo 4.
The divide-and-conquer algorithm runs in O(n2)
(i.e. linear) time
on a sequential processor, and is particularly amenable to implementation
on many different types of parallel computer:
in time O(n2/p)
by a bounded degree network with p processors
for all p = O(n2/log n),
in time O(n2/p2) by a pxp
mesh
for all p<n2/3,
in O(1) time on an nxn mesh with multiple CREW buses,
and in O(1) time on a CREW PRAM with O(n2) processors.
Created by Ian Parberry,
October 15, 1997. Last updated
Wed Apr 23 16:01:11 CDT 2003