Ian Parberry,
"An Efficient Algorithm for the Knight's Tour Problem",
Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997.
[pdf]

### Author's Comment

See more knight's tour images

here.

O. Kyek,
Ian Parberry,
and I. Wegener,
"Bounds on the Number of Knight's Tours",
Discrete Applied Mathematics, Vol. 74, pp. 171-181, 1997.
[pdf]

### Abstract

Knight's tours are a fascinating subject. New lower bounds on the number of knight's tours
and structured knight's tours on $n \times n$ chessboards and even $n$ are presented. For the natural
special case $n = 8$ a new upper bound is proved.

Ian Parberry,
"A Real-Time Algorithm for the
$(n^2-1)$-Puzzle",
Information Processing Letters, Vol. 56, pp. 23-28, 1995.
[pdf]

### Abstract

A real-time algorithm for the $(n^2-1)$-puzzle is designed using greedy and divide-and-conquer
techniques. It is proved that (ignoring lower order terms) the new
algorithm uses at most $5n^3$ moves, and that any such algorithm must make at least
$n^3$ moves in the worst case, at least $2n^3/3$ moves on average, and with probability
one, at least $0.264n^3$ moves on random configurations.