"A Real-Time Algorithm for the
Information Processing Letters, Vol. 56, pp. 23-28, 1995.
A real-time algorithm for the (n2
-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 5n3
moves, and that any such algorithm must make at least
moves in the worst case, at least 2n3
/3 moves on average, and with probability
one, at least 0.264n3
moves on random configurations.
"An Efficient Algorithm for the Knight's Tour Problem",
Discrete Applied Mathematics, Vol. 73, pp. 251-260, 1997.
See more knight's tour images here
and I. Wegener,
"Bounds on the Number of Knight's Tours",
Discrete Applied Mathematics, Vol. 74, pp. 171-181, 1997.
Knight's tours are a fascinating subject. New lower bounds on the number of knight's tours
and structured knight's tours on n x n chessboards and even n are presented. For the natural
special case n = 8 a new upper bound is proved.