Home   News   Publication List   Publications by Subject

Math Puzzles

Thumbnails.

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)

Thumbnails.

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)

Thumbnails.

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)

Thumbnails.

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.

Valid HTML 4.01 Strict Valid CSS!