# Math Puzzles

For a few years I got interested in some mathematical puzzles, like Rubik's cube, the knight's tour problem, the peaceful queens problem, and the $(n^2-1)$-puzzle. Only some of those research projects bore fruit, the results of which you can see below. My coauthors in this work include colleague Ingo Wegener and his student Oleg Kyek.

# Computing Knight's Tours (1997)

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.

# Counting Knight's Tours (1997)

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.

# The $(n^2-1)$-Puzzle (1995)

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.

Created April 21, 2010. Written in HTML 4.01 and CSS 3 using vi. Last updated October 17, 2014.