News!

On Nov. 21, 2010, Derek Kisman verified that the shortest solution for the Panex Puzzle is 31,537 moves! For almost 30 years the upper bound given by Manasse, et al. was believed to be the minimum move count, but it had never been confirmed until now.

Derek made fresh observations about the structure of the puzzle and designed a search algorithm to take advantage of these. His program outperforms previous search programs by multiple orders of magnitude, taking just 30 minutes and 50Mb to find the minimum move count. He also found the shortest solutions for level-11 (76,245 moves), level-12 (184,191 moves), and level-13 (444,807 moves).

In 1982, Mark Manasse, Danny Sleator, and Victor Wei wrote an unpublished paper describing a solving algorithm for the Panex Puzzle, giving an upper bound for all variations of the puzzle of level-5 and greater. They also described a program to search for optimal solutions, but could only verify their algorithm as optimal for up to level-6 (before exhausting their computing resources). Between 2002 and 2004, David Bagley revised the program, and ultimately verified that the original solving algorithm was optimal for up to level-9.

Derek Kisman is a notable competitive programmer: top-ranked at TopCoder for over a year, twice a top-five finisher at the ACM World Finals, and winner of the ICFP three years in a row. He is also a Putnam Fellow, IMO silver medalist, and 11-time member of the Canadian Puzzle Team.

Papers

• Recent Results for the Panex Puzzle, Nick Baxter, G4G5, April, 2002 and revised November 2008 (confirmation of X₉ by David Bagley added). This includes a simplified algorithm that produces near-optimal results.
• Some Results on the Panex Puzzle, Mark Manasse, Danny Sleator, and Victor K. Wei, originally unpublished (1983); edited by Nick Baxter (v1.d, April 28, 2002).
• The Panex Puzzle, Mark Manasse, Danny Sleator, Victor K. Wei, and Nick Baxter, published in 2004 in A Tribute to a Mathemagician (published by AK Peters).

Other Publications

• Nesting Puzzle, Part 1: Moving Oriental Towers, by Vladimir Dubrovsky, Quantum Jan/Feb 1996,  pp 53-57, 49-51.
• Puzzles Old & New, by Jerry Slocum & Jack Botermans, Plenary Publications International, 1986, p 135.
• Sliding Piece Puzzles, by L.E. Hordern, Oxford University Press 1986, pp 144-145, 220.