梅姬之環（Rings of the Magi）遊戲的電腦解法研究

Use Computers to Study the Solutions of the Game "Rings of the Magi"

在本文中，我們嘗試利用電腦的高速運算能力及龐大的記憶空間，配合資料結構及適當的演算法來求出梅姬之環(Rings of the Magi）遊戲各種盤面的可行解。一般人在玩此遊戲時並無一定的規則可循，大多以直覺、本能判斷及經驗來求解，大多數人類的專注力及推理力很難判斷下一步所有的狀況並記憶所有走過的盤面，而且也無法週詳的考慮如何走對盤面的影響會有解或無解。而且此遊戲有許多盤面的解法步數極大，且盤面狀態總數極為龐大，不能以暴力法或尋常方法搜尋求解，因此我們構思如何解決此困難的問題。在此論文中，我們發展了一些有用的技術，目標是能求出一些矩形無障礙盤面的解答，並實際撰寫程式測試，要求在可忍受的時間內求得可行解。希望拋磚引玉，藉此論文引起大家對此問題進一步研究的興趣。

In this paper, we will use computers to design data structures as well as algorithms to derive the solutions for the game "Rings of the Magi". Since many initial configurations of this game need lots of steps to reach the final configurations, its game tree grows very rapidly. We could not search the entire game tree with the "brute force" approach. Previously, there are no computer solutions for this hard problem, but there are many manual trials that are found in many software documents. In this paper, we will explore some useful techniques for solving this game. The results show that we can get available solutions for most boards in a reasonable amount of time. We hope that this paper can introduce the interest of subsequent researchers.