|
緣起
|
讀國中時吧！某天，大哥帶回一個純手工打造的九連環，當時只看著大哥玩得不亦樂乎，
但並沒有引起我太大的興趣；
直到大學時再次接觸，才發現原來九連環是有遞迴性的，那時就想寫個程式來解它，
記得已動手寫程式了，但應該是當天有事外出吧，回來後就把這件事給忘了。
2007年到宜蘭國立傳統藝術中心時又發現它，這次總算把遞迴程式完成了，
當時叫小孩來看九連環的動作，看看後就跑去玩他的玩具了，當時的他應該看不懂吧！
|
各種連環
 |
|
純手工打造(參1)
|
標準形(參2)
|
 |
 |
直立式(參3)
|
四連環(參4) |
 |
|
| 玉女穿梭 |
扭出來(Spin Out)
(參5)
|
九連環的玩法
九連環由九個相互連接的環及一個中空的長形柄所組成。
九連環的一般玩法有兩種，第一種是將這九個環從柄上取下來，第二種是反過來將九個環放入長柄中。
另外也可以由任意狀態解成九個環全取下或全放上的玩法。
|
| 九個相互連接的環及中空的長形柄 |
|
 |
| 九個環全放入長柄的狀態 |
|
|
| 九個環的任意狀態 |
九連環的規則
九連環的每個環是互相牽制的，除了第１環，要上下其他環是要在特定的狀態下才可以的，其規則有二：
規則一：第１環可以在任何時候放上或取下。
規則二：想放上或取下第Ｎ環 (N > 1)，就必須：
將第 N-1 環放在柄上，而第 1 到 N-2 環全部取下，如此才能放上或取下第 N 環。
例：取下第9環
|
| 1-7
環全部在柄下，第8環在柄上，此時第9環可以放上或取下。 |
九連環與遞迴
九連環的拆解過程是一種遞迴式，關於遞迴程式可參考
疊代與遞迴 這篇文章，其內文所介紹的範例均為直接遞迴，
而九連環會用到直接遞迴與間接遞迴，感覺好像很複雜，其實遞迴是相當直覺的，由例子直接說明。
以5連環全解來說明，目的是要將5個環全部取下:
|
(00)
|
(01)
|
同遞迴的思考方式由外而內推導:
即由最後一環往前推導，思考如何把第5環取下，
要把第5環取下，依規則先要取下1到3環，才能取下第5環
而要下第3環必須第1環在下，第2環在上，所以要先下第1環
(目的：第5環要下）
|
此時可下第3環
(目的：第5環要下） |
(02)
|
(03)
|
下第2環必須第1環在上，所以要上第1 環
(目的：第5環要下） |
此時可下第2環
(目的：第5環要下） |
(04)
|
(05)
|
|
下第1環
(目的：第5環要下） |
終於可以下第5環了
步驟01到05可以看成是3個環全下的方式
即要下第N個環，要先下1到(N-2)個環 |
(06)
|
(07)
|
|
這時要下第4環，必須第3環在上，第3環要上則必須第2環在 上，
第2環要上則必須第1環在上，所以先上第1環
(目的：第4環要下） |
第2環上
(目的：第4環要下） |
(08)
|
(09)
|
第3環要上，必須第1環下
(目的：第4環要下） |
此時可上第3環
(目的：第4環要下） |
(10)
|
(11)
|
|
第2環要下，所以第1環要上
(目的：第4環要下） |
第2環下
(目的：第4環要下）
有沒有發現，步驟07到11，相當於把1到3個環全上的方式
而目前狀態可看成4個環全下的狀態
這是一個遞迴的狀態，相當於下完第5環後，
再把1到3環全上，然後變成4個環全下的遞迴 |
(12)
|
(13)
|
第1環下
(目的：第4環要下） |
可以下第4環了 |
(14)
|
(15)
|
|
要下第3環必須第2環上，第2環要上，必須第1環上
(目的：第3環要下） |
第2環上
(目的：第3環要下） |
(16)
|
(17)
|
第1環下 (目的：第3環要下）
3環全下的遞迴狀態 |
可以下第3環了 |
(18)
|
(19)
|
|
第2環要下，必須第1環要上
(目的：第2環要下） |
第2環下
(目的：第2環要下）
2環全下的遞迴狀態 |
(20)
|
(21)
|
|
第1環下
(目的：第1環要下） |
完成 |
|
遞迴解說:
由上面的例子可看出:
(1) 步驟01到05，相當於3個環全下的方式 。
(2) 步 驟06為，放下第5環。
(3) 步驟07到11，相當於3個環全上的方式。
(4)步驟12開始，變成 4個環全下的遞迴。
推廣到 N 連環全下，其遞迴步驟為:
|
(1)
|
|
1至N-2個環全下
|
|
(2)
|
|
取下第N環 |
|
(3)
|
|
1至N-2個環全上，
此時為 N-1連環全下的遞迴狀態
|
|
(4)
|
|
1至N-1個環全下 |
推廣到 N 連環全上，其遞迴步驟為:
|
(1)
|
|
1至N-1個環全上 |
|
(2)
|
|
1至N-2個環全下 |
|
(3)
|
|
放 上第N環，
此時為 N-2連環全上的遞迴狀態 |
|
(4)
|
|
1至N-2個環全上 |
遞迴式:
allRingDown(N) =
allRingDown(N-2) + showRingDown(N) +
allRingUp(N-2) + allRingDown(N-1)
allRingUp(N) =
allRingUp(N-1) + allRingDown(N-2) +
showRingUp(N) + allRingUp(N-2)
|
|
allRingDown(N)
: 第 1 ~ N 環全下，allRingUp(N)
: 第 1
~ N 環全上
showRingDown(N) : 顯示第N環下的動作，showRingUp(N)
: 顯示第N環上的動作
其中
allRingDown(N)為遞迴函式 :
(1) 直接遞迴 : 呼叫
allRingDown(N-2) 及 allRingDown(N-1)
(2) 間接遞迴 : 呼叫
allRingUp(N-2)
其中
allRingUp(N) 為遞迴函式:
(1) 直接遞迴 : 呼叫
allRingUp(N-1) 及 allRingUp(N-2)
(2) 間接遞迴 : 呼叫
allRingDown(N-2)
九連環遞迴程式碼:
JavaScript:
function allRingDown(n)
{
if
(n > 0) {
allRingDown(n-2);
printRing(n, "DOWN");
allRingUp(n-2);
allRingDown(n-1);
}
}
function allRingUp(n)
{
if
(n > 0) {
allRingUp(n-1);
allRingDown(n-2);
printRing(n, "UP");
allRingUp(n-2);
}
}
var stepCounter = 0;
function printRing(n,
action)
{
++stepCounter;
document.write("<p>"
+ stepCounter + ": " + n + "
" + action );
}
allRingDown(5);
|
程式可於 jsBin 線上執行.
另外為 C 語言所寫的 Windows console program:
nineLinkedRings.zip
|
|
九連環與格雷碼
由於遞迴式不太適合用來寫九連環遊戲，一般若無適當的疊代法(iteration)就只能用推疊(stack)
取代遞迴呼叫，
經網路搜尋後找到了格雷碼 。
另人驚訝的是格雷碼的順序居然完全和九連環解法的順
序相同。
先看看什麼是格雷碼：
格雷碼
(Gray Code)是由貝爾實驗室的Frank
Gray在1940年代提出的，用來在使用PCM（Pusle Code Modulation）
方法傳送訊號時避免出錯。格雷碼是一個數列集合，相鄰兩數間只有一個位元改變，為無權數碼。(參6)
數字0～7的編碼比較如下：
十 進位
|
格雷碼 |
二進位
|
0
|
000
|
000
|
1
|
001
|
001
|
2
|
011
|
010
|
3
|
010
|
011
|
4
|
110
|
100
|
5
|
111
|
101
|
6
|
101
|
110
|
7
|
100
|
111
|
|
格雷碼的鏡射排列:
n位元的格雷碼可以從n-1位元的格雷碼以上下鏡射後加上新位元的方式快速的得到，如下圖所示。(參6)
九連環與格雷碼的關係:
|
步數
|
5連環全部放上的順序 |
格雷碼 |
二進制 |
00
|
|
00000
|
00000
|
01
|
 |
00001
|
00001
|
02
|
|
00011
|
00010
|
03
|
|
00010
|
00011
|
04
|
|
00110
|
00100
|
05
|
|
00111
|
00101
|
06
|
|
00101
|
00110
|
07
|
|
00100
|
00111
|
08
|
 |
01100
|
01000
|
09
|
 |
01101
|
01001
|
10
|
|
01111
|
01010
|
11
|
|
01110
|
01011
|
12
|
|
01010
|
01100
|
13
|
|
01011
|
01101
|
14
|
|
01001
|
01110
|
15
|
|
01000
|
01111
|
16
|
|
11000
|
10000
|
17
|
|
11001
|
10001
|
18
|
|
11011
|
10010
|
19
|
|
11010
|
10011
|
20
|
|
11110
|
10100
|
21
|
|
11111
|
10101
|
|
由上圖可以看出，解九連環的順序就是格雷碼的順序，不禁讓人懷疑，法蘭克．格雷(Frank
Gray)是不是有玩過九連環？
格雷碼與二
進制的 轉換：
由於格雷碼為無權數碼，無法直接拿來運算，但可以經由與二進制的互換，得到格雷碼的值與順序的關係。
轉換方法如下或參考 Converting
Between Gray and Binary Codes 中非常清楚的動態說明。
二進制碼轉換成格雷碼:(參7,
參8)
|
|
g(1) = b(1)
g(2) = b(1)
xor b(2)
g(3) = b(2)
xor b(3)
g(4) = b(3)
xor b(4)
g(5) = b(4)
xor b(5)
|
|
|
JavaScript:
function binaryToGray(num)
{
return (num >> 1) ^
num;
}
|
|
|
格雷碼轉換成二進制:(參7,
參8)
|
b(1) = g(1)
b(2) = b(1) xor g(2)
b(3) = b(2) xor g(3)
b(4) = b(3) xor g(4)
b(5) = b(4) xor g(5)
|
|
|
JavaScript:
function grayToBinary(num,
numBits)
{
var
shift;
for(shift = 1; shift <
numBits; shift=2*shift) {
num = num ^ (num >>
shift);
}
return num;
}
|
|
|
九連環遊戲
九連環的遊戲是用
JavaScript 寫成，其中連環的動態動作是以 KineticJS javascript
framework 完成，
在 Chrome下最順暢
FireFox , IE9 都不太流暢但還是可執行。
由於九連環的狀態與順序的關係即為格雷碼與順序的關係，程式中剩餘步數的計算(左下)，提示，自動，
均是由九連環的狀態對應到格雷碼，然後由格雷碼轉成二進制，並作加減法運算，再轉回格雷碼而來的。
程式原始碼
GitHub: https://github.com/SimonHung/NineLinkedRings
Simon's GitHub Projects: https://simonhung.github.io
參考資料
(1) 純手工打造-迷你九連環: http://whereyou.pixnet.net/blog/post/22696509
(2) 九連環拆裝攻略: http://game.titan24.com/tbm/news/2009-09-10/133.html
(3) 直立式九連環: http://www.wzweiao.com/1338.htm
(4) 成人益智玩具: http://www.chinastuffedtoys.com/new_view.asp?id=4305
(5) Spin Out 線上遊戲: http://www.puzzles.com/products/SpinOut/PlayOnline.htm
(6) 格雷碼 wiki: http://zh.wikipedia.org
/wiki/格雷碼
(7) Gray
Code from/to binary and
decimal: http://www.matrixlab-examples.com/gray-code.html
(8) Gray
code wiki: http://en.wikipedia.org/wiki/Gray_code
|
|
