九連環(huán)的解法　 九連環(huán)的歷史
　　分析解九連環(huán)的完全記法，由于每次只動一個環(huán)，故兩步的表示也只有一個數(shù)字不同。下面以五個環(huán)為例分析。左邊起第一列的五位數(shù)是5個環(huán)的狀態(tài)，依次由第一環(huán)到第五環(huán)。第二列是把這個表示反轉(zhuǎn)次序的五位數(shù)，似乎是二進(jìn)制數(shù)，但是與第四列比較就可以看出這不是步數(shù)的二進(jìn)制數(shù)表示。
　　第三列是從初始狀態(tài)到這個狀態(tài)所用的步數(shù)。最右邊一列才是步數(shù)的二進(jìn)制表示。
　　00000－00000－0－00000
　　10000－00001－1－00001
　　11000－00011－2－00010
　　01000－00010－3－00011
　　01100－00110－4－00100
　　11100－00111－5－00101
　　10100－00101－6－00110
　　00100－00100－7－00111
　　00110－01100－8－01000
　　10110－01101－9－01001
　　11110－01111－10－01010
　　01110－01110－11－01011
　　01010－01010－12－01100
　　11010－01011－13－01101
　　10010－01001－14－01110
　　00010－01000－15－01111
　　00011－11000－16－10000
　　10011－11001－17－10001
　　11011－11011－18－10010
　　01011－11010－19－10011
　　01111－11110－20－10100
　　11111－11111－21－10101
　　我們發(fā)現(xiàn)，右邊一列數(shù)恰好是十進(jìn)制數(shù)0到21的二進(jìn)制數(shù)的格雷碼！ 這當(dāng)然需要21步。如果把5位二進(jìn)制數(shù)依次寫完，就是
　　10111－11101－22－10110
　　00111－11100－23－10111
　　00101－10100－24－11000
　　10101－10101－25－11001
　　11101－10111－26－11010
　　01101－10110－27－11011
　　01001－10010－28－11100
　　11001－10011－29－11101
　　10001－10001－30－11110
　　00001－10000－31－11111
　　這說明，對于只有5個環(huán)的五連環(huán)，從初始到狀態(tài)11111用的不是并不是最多，到狀態(tài)00001才是最多，用31步。類似，對于九連環(huán)，從初始到狀態(tài)111111111用的不是并不是最多，到狀態(tài)000000001才是最多，用511步。由于格雷碼111111111表示二進(jìn)制數(shù)101010101，表示十進(jìn)制數(shù)341，故從初始狀態(tài)到9個環(huán)全部上去用341步。這就是九連環(huán)中蘊(yùn)涵的數(shù)學(xué)內(nèi)涵。
　　注 由二進(jìn)制數(shù)轉(zhuǎn)換為格雷碼：從右到左檢查，如果某一數(shù)字左邊是0，該數(shù)字不變；如果是1，該數(shù)字改變（0變?yōu)?，1變?yōu)?）。例，二進(jìn)制數(shù)11011的格雷碼是10110.
　　由格雷碼表示變?yōu)槎�進(jìn)制數(shù)：從右到左檢查，如果某一數(shù)字的左邊數(shù)字和是偶數(shù)，該數(shù)字不變；如果是奇數(shù)，該數(shù)字改變。
　　例 格雷碼11011表示為二進(jìn)制數(shù)是10010.
　　以上可以用口訣幫助記憶：2G一改零不改，G2奇變偶不變。
　　例 設(shè)九連環(huán)的初始狀態(tài)是110100110，要求終止?fàn)顟B(tài)是001001111，簡單解法與完整解法各需要多少步？過程如何？
　　解 初始狀態(tài)110100110，格雷碼是011001011，轉(zhuǎn)換為二進(jìn)制數(shù)是010001101，相應(yīng)十進(jìn)制數(shù)是141.終止?fàn)顟B(tài)是001001111，格雷碼是111100100，轉(zhuǎn)換為二進(jìn)制數(shù)是101000111，相應(yīng)十進(jìn)制數(shù)是327.二者差326－141＝186，完整解法需要186步。
　　簡單解法步數(shù)，我們由141，327分別求相應(yīng)的簡單步數(shù)，
　　對于N=141，得到N0=103；對于N=327，N0=242.二者差139，故簡單步數(shù)139.這個結(jié)果很容易在下一頁九連環(huán)電腦游戲上驗(yàn)證。