The traditional Klotski sliding block puzzle (Red Donkey) uses the same pieces and same goal (big square to bottom middle) as the Century Puzzle, Supercompo, and Supercentury, although the orientations of the 2x1 blocks differ. This conveniently allows multiple ways to enjoy the same set of pieces (so long as they can be arbitrarily rearranged).
Inspired by a physical Klotski puzzle in which one can easily rearrange the pieces, and with a thin big square block and thin slot at the bottom of the frame indicating the goal. The rest of the blocks are thick so will not fit through the slot.
What is the most difficult puzzle with this set of blocks and final goal?
Slightly simpler: Among all the goal positions for (say) the Donkey, what starting position has the greatest minimum distance? That is, what is the most difficult starting position for the Donkey if you are not allowed to take pieces out? This is a minimax graph distance problem.
Some collections of 4x5 sliding block puzzles:
http://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzRedDonkey.html
http://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzDadsFamilySet.html
http://www.johnrausch.com/SlidingBlockPuzzles/4x5.htm
http://www.pro.or.jp/~fuji/java/puzzle/slide/V1.0/fuji.index-eng.html
No comments :
Post a Comment