Computing Knight's Tours (1997)
"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
Counting Knight's Tours (1997)
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 \times n$ chessboards and even $n$ are presented. For the natural
special case $n = 8$ a new upper bound is proved.
The $(n^2-1)$-Puzzle (1995)
"A Real-Time Algorithm for the
Information Processing Letters, Vol. 56, pp. 23-28, 1995.
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.
Created April 21, 2010.
Written in HTML 4.01 and CSS 3 using vi.
Last updated October 17, 2014.