硬幣移動問題的計算複雜度

Abstract

硬幣移動問題的初始盤面是一列硬幣，有 n 個五分錢硬幣接連排著 n 個一分錢硬幣。玩家必須重新排序這列硬幣，讓五分錢的硬幣和一分錢的硬幣交錯排列。每一回合，玩家可以把 k 個相鄰的硬幣移動到新的位置。在移動過程中，這 k 個硬幣的相對順序不能調動。

我們證明至少需要 n 回合，才能解決此問題，更針對參數為 k=2 和 k=3 的問題，設計了能產生最佳移法的演算法。此外，我們提出一套建構最佳解答的辦法，並成功套用於參數為 k=4 和 k=5 的問題。

Consider a line of n nickels and n pennies with all nickels arranged to the left of all pennies, where n >= 3. The puzzle asks the player to rearrange the coins such that nickels and pennies alternate in the line. In each move, the player is allowed to slide k >= 2 adjacent coins to a new position without rotating. We prove that it takes at least n moves to solve the puzzle, and present algorithms to generate the optimal solutions for k = 2 and k = 3. We also propose a framework to extend solutions, and apply it successfully to construct optimal solutions for k = 4 and k = 5.