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

On the Complexity of the Linear Sliding-Coin Puzzle

林庭宇(Ting-Yu Lin)

指導教授 ： 蔡錫鈞

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00429

摘要

硬幣移動問題的初始盤面是一列硬幣，有 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.

並列關鍵字

Sliding-Coin Puzzle

參考文獻

Dover Publications, 1954.

[4] Erik D. Demaine, Martin L. Demaine, and Helena A. Verrill, “Coin-Moving Puzzles,”

[5] C.-C. Chu, M.-Y. Lee, and C.-S. Tsai, “Sliding-Coin Puzzle,” Unpublished manuscript

[6] Erik D. Demaine, and Martin L. Demaine, “Puzzles, Art, and Magic with Algorithms,”

“Moving Coins”, Computational Geometry, volume 34, issue 1, pages 35–48, 2006.