
Panex Puzzle Resources 
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 level11 (76,245 moves), level12 (184,191 moves), and level13 (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 level5 and greater. They also described a program to search for optimal solutions, but could only verify their algorithm as optimal for up to level6 (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 level9.
Derek Kisman is a notable competitive programmer: topranked at TopCoder for over a year, twice a topfive 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 11time member of the Canadian Puzzle Team.
Papers
Original Search Program
Web Applets
Other Publications
© 19992010 by 