九連環的數學分析

7 人贊了文章

九連環是中國著名的古典智力遊戲，距今至少已有800多年，在我國古籍中有關它的記載也很多見。對於解九連環，我想大多數玩過的人都對它的解環過程映像深刻，古人曾經總結出了三句口訣：

1.一二一三一二一

2.釵頭雙連下第二

3.獨環在釵上後環

本文將從九連環的基本操作規律中通過逆向歸納得到解法，並隨之導出解環所需步驟數的遞推關係式，得到了解下九連環的步數。在文末，舉例簡單地介紹了求解不同設定的九連環的步數問題。

九連環的基本操作規律

1.九個環中只有第一個環和第二個環既可單獨套上或取下，也可同時上下。

2.當前個環都解下而第個環在環柄時，第$n$個環才能上下，此時第個環不能上下（）。

3.上環過程是下環的逆。

註：熟悉九連環的可跳過下面的解法分析。

解法分析

根據基本操作規律，要想解下全部的九個環，首先要做的要讓第九個環解下，然後再依次解下所有環。類似於河內塔問題，要把全部n個盤挪位置，一定要讓最後一個位於塔底的盤挪出來，在接著後續的步驟。

而要解第九個環，根據上述規律2，操作狀態為：解下前7個環，九號環解下，八號環在環柄。這時然後再解第八個環，即當前六個環都解下時，八號環解下；接著解第七個環……，直至1號環和2號環解下，完成九個環的環柄分離。

上述是一個解九連環的分段目標，具體每一段的操作又有很大的重複性，我們可以通過逆向歸納得到每一階段的操作過程。

比如，解下九號環，要先解前七個環，則必須先解七號環，依次往下推：解下前5個環先解5號環解下前三個環解三號環，最後回到了開始時第一步：解下一號環。然後逆此方向就可以完成九號環下柄。

同理，當完成九號環的下柄過程後，繼續解八號環分兩步：

1.當九號環解下時，一至七環都已被解下，要解下八號環，要達到的狀態是：七號環上，而前六個環解下。 這時，七號上需要六號上而一至五環都解下，依次往下推有，五號上 四號上三號上二號上（一號上）；

2.接著此時狀態相當於九號環被解下，而一至八環在環柄上。所以需要先解下八號環，仍然可以通過逆推來完成八號環的下柄，不再多言。

依次類推，解下所有環。

從上述較為詳細而啰嗦的文字分析可以知道，粗略地說，在解九連環的過程中，每解下一個環，就得重複一遍之前所做的大部分工作。顯然，解環的過程是蘊含遞推關係的，下面來推導解環所需步驟數的遞推公式。

遞推公式和通項公式

令表示解下前n個環所需操作步驟數，將解下n個環的過程表述如下：

1. 解下前n-2個環

2. 解下第n號環

3. 前n-2個環重新上柄

4. 解下前n-1個環

所以，H(n)的遞推關係為：

可化為常係數齊次遞推公式：

利用初始條件：，易解得通項公式為：（n為奇數）（n為偶數）

這樣的話，解下九連環的步驟數為：H(9)=256

解特殊狀態的九連環

玩九連環時，一般是以九個環都在環柄上作為初始狀態開始解的，已經知道了這樣的情況需要256步。如果要求初始狀態是1至8號環都已經解下，只有九號環在環柄上，此時取下所有環需要多少步？

來解一下：

根據九連環的規律，必須先要九號環解下，所以讓已經解下的一至八環再套上去，這樣就回到了「正常」狀態的九連環。所以這樣的情況一共需要：H(8)+H(9)=383 步。

類似地，還可以隨便指定合理的初始狀態去求解。

本文屬於個人原創文章，歡迎各位讀者參閱、指正^_^