魔術方塊 By:陳建廷&毛思宣.

Presentation on theme: "魔術方塊 By:陳建廷&毛思宣."— Presentation transcript:

1 魔術方塊 By:陳建廷&毛思宣

2 魔術方塊公式的推導 魔術方塊公式的形成多半是利用一種方法： Trial and Error 這個萬用法則無論是用在數學、物理等自然科學， 或是電機資訊等工程科學，或者其他社會科學都適用。 魔術方塊當然也不例外。 Trial and Error 就是「嘗試錯誤法」。

3 多試試幾種情形，如果其中一種方法達到了你要求的效果 就把他紀錄下來，這就是所謂的嘗試錯誤。 一般人就能利用嘗試錯誤法發掘不少魔術方塊的公式， 但是如果你要找最短路徑、最佳解或是最順手的公式，常需要依賴電腦的協助(同樣是利用嘗試錯誤法)。 當電腦幫人找出許多可用的公式後，我們在自行從中尋找最適合的公式。 簡單來說魔術方塊公式的推導，就是利用 Trial and Error 的方法完成的。

4 魔術方塊的發明 魔術方塊（英語：Rubik's Cube），在中國大陸稱為魔方，在香港稱為扭計骰，是匈牙利建築學教授和雕塑家魯比克·厄爾諾（Rubik Ernő），於1974年發明的機械益智玩具，最初的名稱叫Magic Cube，後來被Ideal Toys改為Rubik's cube。根據估計，魔術方塊自發明以來在全世界已經售出了3億多個[1]。魔術方塊與華容道、獨立鑽石棋同被稱為智力遊戲界的三大益智遊戲。

5 魔術方塊在1980年代最為風靡，至今未衰。面世不久後，很多類似的玩具也紛紛出現，有些出自發明人魯比克，包括2階、4階和5階版本的魔術方塊；有些則是出自別人之手。
魔術方塊發明人魯比克教授在1974年獲得匈牙利專利號HU170062，他認為別人不太願意生產這種玩具，因此沒有申請國際專利，但實際上仿製品幾乎馬上就出現了。它總共有約四千三百億的變化。

6 魔術方塊中的數學原理 二階與三階的方塊： 三階方塊（Rubik's Cube）是一般最常見的方塊，是由六個中心面（center），八個角(corner)，十二個邊(edge)所組成的。而二階的方塊（Pocket Cube）則是沒有中心面的方塊，只有三階方塊的八個角。

7 首先，我們來看對於一個魔術方塊來說，它可以亂轉成幾種組合呢？
全部的組合數： 2階：7! x 3^7（環排） 3階：8! x 12! x 3^8 x 2^12 （非環排）

8 但是，所有的狀態都有可能出現嗎？或者說，如果我們把一個方塊拆開，再隨便裝回去，一定有辦法把它轉回原來的樣子嗎？答案是不行的。事實上，對於一個三階的魔術方塊來說，如果不把一顆魔術方塊給拆了，下面三種狀態是不可能出現的： (1)單對互換(exchange single pair ) (2)單邊翻轉(flip single edge)， (3)單角自旋(twistsingle corner )。

9 現在，我們就來說明這三種情形為什麼不可解，首先，我們要先說明的第一個東西是不變量，什麼是不變量？ 如果我們定義出一個函數，使得這個函數的值在變換之下仍然保持不變，那它就是一個不變量。

10 在３－puzzle中一共有六種case，而其中只有三種有解，我們稱之為偶至換(even swap)而另外三種不可解的則稱為奇至換(odd swap)，並不是所有的題目中奇至換都不可解，只是在這個例子中，剛好不可解。

11 現在，我們回到魔方上。對於下列的三種情形，現在我們分別給出三種不變量：
單對互換：位置的不變量。 單邊翻轉：邊的不變量。 單角自旋：角的不變量。

12 所以現在我們知道了，如果要用不變量來確認一個狀態和另一個狀態之間是否互通（就是可解的意思），我們可以先建構一個不變量的函數出來，然後計算它的值，再確認在合理的操做之下，這個值不會改變，那麼，我們就可以說如果有一個狀態，代入我們給出的公式計算，得到和原來不一樣的值，那這個狀態就不可解。

13 首先我們來看位置的不變量： 這裡我們給出一個和３－puzzle相似的函數： 為什麼是２０？因為我們有８個角和１２個邊，一共有２０個小方塊。 接著，我們考慮邊和角的情形： 對於每一個邊來說，有一面是1/2而有另外一面是0，而在每一個轉動中，每個面增加的總量是一個整數，減少的總量也是一個整數，所以不存在只有一個邊翻轉的情形。

14 對於每一個角來說，三面分別是０，1/3，2/3。則對於每一個旋轉來說，每個面的改變量一定是整數，而如果旋轉單一角，則會導致面的改變量是分數，所以單一角的旋轉也是不存在的。
所以，實際上的組合數應該是： 2階：7!x 3^7/3=3,674,160 3階：8! x 12! x 3^8 x 2^12 /2 /2 /3=4,325,003,274,489,856,000

15 問題討論 如果我們把所有的狀態都當成一個點，而一個狀態可以經由一個旋轉達成另一個狀態的話，我們說這兩個點之間有邊。如此一來，我們會得到一個有4,325,003,274,489,856,000個點的圖。 為什麼要這樣模型化呢？因為這牽涉到一個相當複雜的問題：對於任意亂的方塊，是否存在一個最短路徑的解法？這個答案是肯定的，那麼如果存在一個這樣的解法，那麼將之推廣的話，對於所有的狀態，是否都能在n轉之內將其復元呢？

16 資料出處 １：C. Bandelow : Inside Rubik’s Cube And Beyond (Boston : Birkhäuser, c1982) ２：Ernő Rubik :Rubik's cubic compendium (Oxford [Oxfordshire] : Oxford University Press, 1987) 特別感謝:雅虎奇摩˙Google & 維基百科