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 this. 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).

Background
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).
• 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).

Original Search Program

• Original Search Program, copyright by Mark Manasse, Danny Sleator, and Victor K. Wei.

Web Applets

• Panex Applet, by David Bagley, http://gwyn.tux.org/~bagleyd/java/PanexApp.html.
• Panex Puzzle (level 4 only), By Emmett Henderson, http://www.cheesygames.com/panex/, and uncredited at numerous other sites.

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.