Panex Puzzle Resources
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).
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.
Original Search Program
© 1999-2010 by