狠狠撸

戴嘉駿 darkgerm <darkgerm@gmail.com>

? 目前就讀於交通大學資工系，是個熱愛 Python 及
各種資訊技術的大學生
? 平時的休閒活動喜歡玩各種益智遊戲，像是魔術方
塊、紙上謎題、和各類益智玩具。
? 於 2011 年底開始參加
Python 新竹地區的使用
者社群(PyHUG)，現在
是 PyHUG 的協辦單位
幹部，也曾在 PyHUG
上給過一個與 ctypes
相關的 talk。
<photo here>

? 1. 魔術方塊的基本認識
? 1.1 魔方的介紹
? 1.2 魔方的解法
? 2. pyRubiks 程式架構
? 2.1 什麼是 pyRubiks - 動機及目的
? 2.2 讀取 – 讓電腦「看到」魔方
? 2.3 儲存 – 魔方的資料結構
? 2.4 尋解 – 找出其解法
? 2.5 顯示 – 畫出一顆魔方
? 2.6 demo !
? 2.7 pyRubiks 其他延伸應用
? 3. 一些魔方記錄及軼事

? 1.1 魔方的介紹
? 1.2 魔方的解法

? 1974 年匈牙利建築學教授 Rubik Ern? 發明
? 1980 年代大流行
? 變化數：
? 角排列 * 角旋轉 * 邊排列 * 邊旋轉 / 反向排列
? 37 EB !
? KB MB GB TB PB(PetaByte) EB(ExaByte)
8! × 37 × 12! × 211
2
= 43,252,003,274,489,856,000

? 爆力解 (?)
? 我的解法
? 阿公的解法
? layer-by-layer
? 速解魔方(Fridrich Method, CFOP system)
? 八角定位(corner first)
? 8355 解法 (出自台灣！)
? 盲解魔方

? 爆力解 (?)
? 重貼貼紙
? 拆開重組
FAIL !

? layer-by-layer
? 一層一層解

? 速解魔方(Fridrich Method, CFOP system)
? layer-by-layer 的進階版
? 人轉起來速度最快，目前在比賽最多人使用
? 公式眾多：第三階段有 57 個、第四階段有 21 個

? 八角定位(corner first)
? 「角先」轉法
? 與我發現的解法相同！

? 8355 解法 (出自台灣！)
? 許技江老師所規劃出來的解法
? 強調沒有公式！靠理解的方式解魔方

? 盲解魔方
? 把整個方塊背下來，頭腦的 memory 要夠

? 2.1 什麼是 pyRubiks - 動機及目的
? 2.2 讀取 – 讓電腦「看到」魔方
? SimpleCV
? 2.3 儲存 – 魔方的資料結構
? numpy
? 2.4 尋解 – 找出其解法
? 2.5 顯示 – 畫出一顆魔方
? VPython
? 2.6 demo !
? 2.7 pyRubiks 其他延伸應用

? 一個用 Python 寫的魔術方塊程式
? 要能有像動畫般的轉方塊畫面
? 要能夠自己找到解
? 最好還要可以讀取一顆方塊
? 動機
? 出自對魔方的興趣
? 看到網路上有人用樂高做「轉魔方機器」，想自己也做一
個
? https://bitbucket.org/darkgerm/pyrubiks/src

? 使用 SimpleCV 做攝影機的控制及顏色的判別
? 週遭燈光的影響，有些顏色常常會誤判...
? 黃色 vs 白色
? 紅色 vs 橙色
? SimpleCV 在 mac 上非常難安裝orz

? 一顆 3D 的魔方，如何用文字描述？
? 分別寫出每個小方塊的顏色
? 魔方是 3D 的，太難閱讀
? 以展開圖的形式畫出魔方
? 雖然無法表示出一個小方塊的狀態，但可讀性高很多

? 一個表示魔方的字串，要用什麼檔案格式儲存？
? JSON
? 字串不能換行，可讀性消失了
? ini
? 字串可換行
? 魔方是資料，不是設定檔，感覺很怪
? 寫程式也是需要 feeling 的 ?
? XML
? 字串可換行
? DTD(Document Type Definition)

? 要用什麼資料結構儲存魔方？
? numpy.array
? 可以轻鬆的取出某个特定的面，同时也可以直接赋新值

? 魔方能有什麼動作(method)？
? turn()
? Singmaster notation
? L U L‘ y R2 u‘ R U‘ R‘ U R‘ u R2

? Singmaster notation (綠色面向自己)
? F (Front) B (Back)

? U (Up) D (Down)

? R (Right) L (Left)

? 使用 Fridrich Method
? 最多人使用的解法，但尚未看過有程式做過
? Fridrich Method 分成四個階段 (CFOP)
? cross
? F2L (First 2 Layer)
? OLL (Orientation of Last Layer)
? PLL (Permutation of Last Layer)

? stage 1: cross
? 目標為完成底層十字
? 每個邊有 24 種狀況，有 4 個邊
? algorithm:
? 一次完成一個邊(1,0,2)
? 做一次 “y”，重複 4 次即可完成十字

? stage 2: F2L (First 2 Layer)
? 目標為完成下面兩層
? 每個 pair 有 41 種狀況，有 4 個 pair
? algorithm:
? 預處理邊角位置
? 套用 F2L 第一層公式(組合 pair)
? 套用 F2L 第二層公式(pair 歸位)
? 做一次 “y” 並重複前面步驟 4 次

? stage 3: OLL (Orientation of Last Layer)
? 頂層的方向，目標為讓頂層顏色正確
? 一共有 57 種狀況
? algorithm:
? 把頂層的顏色編碼，尋找對應的公式

? stage 4: PLL (Permutation of Last Layer)
? 頂層的排列，目標為完成整顆方塊
? 一共有 21 種狀況
? algorithm:
? 把頂層的方塊位置編碼，尋找對應的公式

? 重整轉法
? 把 “2”、”’” 全部展開
? 把 fbudrl/MES extension，全部改用 FBUDRL 及 xyz
表示
? 消除 xyz (用一張 table 維護舊轉法與新轉法的對應關系)
? 重新合併相同轉法
? len(整理完的轉法) = 實際的步數

? VPython 是一個可以畫 3D 圖形的模組
? 每個魔方有 27 個小方塊
? 每個小方塊有 6 面需要畫
? 畫 27 * 6 個 box

? 旋轉的動畫
? 用 frame 把所有的 box 收集起來，再轉這個 frame

? 遇到的困難
? VPython 在今年 2/19 出了第 6 版
? 以前的 code 不會動了orz....
? 陣列索引一回事；空間座標系一回事
? 第一版和第二版的座標系不同XD

? 實作出其他種類的方塊

? 與機器人連結，自動轉魔方機

類型時間(單次最佳) 記錄保持人我的記錄(平均)
2x2x2 0:00.69 Christian Kaserer 17 sec.
3x3x3 0:05.55 Mats Valk 35 sec.
4x4x4 0:26.44 Sebastian Weyer 4 min.
5x5x5 0:51.09 Feliks Zemdegs 6 min.
6x6x6 1:49.46 Kevin Hays 15 min.
7x7x7 2:41.63 Lin Chen 30 min.
3x3x3盲解 0:26.36 Marcell Endrey
3x3x3單手 0:09.43 Giovanni Contardi 3 min.
3x3x3腳轉 0:27.93 Fakhri Raihaan 10+ min.
∞

? 各種特別的轉魔方方式
? 用腳轉 (比賽項目)
? 用筷子轉
? 邊丟邊轉

狠狠撸

Py rubiks

Recommended

More Related Content

Featured (20)

Py rubiks