要說編碼 首先要說到我們採用展開圖的方式 讓使用者輸入一個魔術方塊的狀態 但是因為考量到要讓旋轉的action較為容易 編碼並沒有直接用每一個面9格的狀態 而是採用立體小方格的編碼方式 先將整個方塊轉成27個立體小方塊 扣除掉看不到的中心方塊 以及六個不會改變狀態的每面中心方塊 所以用20個小方塊來代表一個大方塊的狀態 也因為當每一個小方塊的朝向確立時 這個小方塊所能在大方塊的位置是唯一的 所以就不需要描述小方塊在大方塊的相對位置了 定出如何表現一個魔術方塊的方法後 接著要開始描述sat式子 首先要描述的部份 分成 initial state final state action action exclusion frame 幾個部份 首先定義一個步數steps 把state加上第幾個時間點編碼產生一組變數 每個state包括20個(如果2*2的魔方就只有8個)小方塊*24個朝向 initial state 就是時間0 第一步旋轉後就是 時間1 ........... 第n步就是時間 n 而final state就是時間 (steps值) action 要描述在precodition下會動到的方塊狀態 我們採用corner和edge的小方塊分開的表示法 所以把coner的編碼和action獨立出來 就自然變成 2*2的魔方實作了 採用的方式 舉個例 (a,4,0) 且 u_0 -> not(a,4,1) 且 (a,1,1) 最前面那個括號中的a表某一個顏色組成的小方塊 4表示他的朝向(也暗示了他的位置) 0 表示他的state u_0表示第0時間點選擇採用了上層順時針旋轉 描述完action的rule後 要加上 一個時間點只能有一個action發生 以及至少有一個action發生 的action exclusion條件 但是這樣還有一個重要的問題 就是要描述在一個action發生時 所有不變的小方塊規則 否則將會造成 選定上層旋轉了 但下層卻自動亂轉等錯誤發生 這就是frame的問題 我們採取用 "一個state的變化必定是哪些action的影響" 這樣式子的寫法 上面那句話的逆否命題 就可以確保 如果沒有發生會影響到小方塊的旋轉法 小方塊的狀態將不會變化 最後將所有條件取交集就可以送入solver解了 接下來要分析輸出檔 如果是satisfiable 要擷取出旋轉法的變數部份 然後解碼輸出旋轉法 如果是unsat 就要繼續遞增steps 然後回到前面 重新產生sat式子……如此迴圈下去 而這樣就可以解出當一個方塊是確實可解的問題了 但還要去解決若一個方塊是無法轉出正確的情形的判斷法 這個部分就比較數學了 大致上就是下面這個link中的東西 http://members.tripod.com/~dogschool/rubikscube.html 我們用五個規則去檢查 前兩個是在編碼過程 1.若是讀到不符合的顏色號碼 2.若是產生不可能存在的方塊，例如是不相鄰的顏色出現在同一個小方塊 3.用odd permutation和 even permutation去檢查 corner 和 edge cubelets 4.同樣用上述方法去檢查 facelet of corner 和 edge(事實上只須查 edge的) 5.用twist的parity 去檢查所有的corner cubelets 如果有任何一個規則不合正常的方塊 就是UNSOLVABLE 這就將所有的unsolvable給涵蓋完了 我剛看了一下你寫的東西 還差蠻多的… 我已經覺得極度不妙了~~~~ 唉~~ 你明天不是還要考試嗎？ 這樣包括書面、投影片和有剩下code的實作 真的很多未完成 我這兩天應該已經想出該怎麼具體去 完成unsolvable的判斷法 但還沒coding ………… 總不會要我全都做吧… magulo~~~~ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.135.58.37