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

Abstract

A real-time algorithm for the (n²-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³ moves, and that any such algorithm must make at least n³ moves in the worst case, at least 2n³/3 moves on average, and with probability one, at least 0.264n³ moves on random configurations.

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 x n chessboards and even n are presented. For the natural special case n = 8 a new upper bound is proved.