晨 發(fā)自 凹非寺
量子位 報道 | 公眾號 QbitAI

魔方解不開了怎么辦，讓程序來幫你。

只需用攝像頭把魔方的六個面掃描一遍就能直接給出還原步驟。

即使你的魔方不是標準配色或房間的照明情況特殊也可以通過顏色校準模式來識別。

這款荷蘭小哥發(fā)布的3階魔方解算器“Qbr”已經(jīng)在GitHub上開源。

小哥還貼心地把魔方公式中的步驟代號翻譯為人話，并且支持中文，可以直接按照描述操作。

中文是小哥自學的，他還給自己起了個中文名叫“金可明”。

解算結(jié)果大概是這樣的。

步驟數(shù): 20
復原教程: B2 U2 F' R U D' L' B' U L F U F2 R2 F2 D' F2 D R2 D2

1. 將魔方的后面旋轉(zhuǎn)180°。
2. 將魔方的頂層旋轉(zhuǎn)180°。
3. 將魔方的前面向左旋轉(zhuǎn)90°。
...
20.將魔方的底層向右旋轉(zhuǎn)90°。

安裝方法

使用Qbr需要你的電腦裝有Python3，Git以及一個攝像頭。

安裝方法如下

$ git clone --depth 1 https://github.com/kkoomen/qbr.git
$ cd qbr
$ python3 -m venv env
$ source ./env/bin/activate
$ pip3 install -r requirements.txt

運行時要注意每次運行前都要激活虛擬環(huán)境

$ source ./env/bin/activate 
$ ./src/qbr.py

操作也非常簡單，可以先按L鍵循環(huán)切換語言到中文，C鍵進入/退出顏色校準模式。

掃描模式下按空格鍵保存識別好的一個面，6個面都識別好之后按esc就可以在終端里看到結(jié)果了。

如果需要將結(jié)果翻譯成“人話”，則運行時加入?yún)?shù)“-n”即可。

解魔方的算法方面Qbr直接使用了開源的Kociemba算法庫，該算法可以在20步以內(nèi)還原任意3階魔方。

那么問題來了，如何將攝像頭掃描的圖像輸入給算法呢？

攝像頭如何識別魔方？

Qbr使用開源的計算機視覺庫OpenCV。

首先將圖像灰度化，稍微做一下模糊，然后用邊緣檢測識別出魔方小面的邊緣。

把所有邊緣加粗，使屬于一個邊緣的多條線可以合并。

將邊緣疊加到原始圖像上，使用OpenCV的approxPolyDP函數(shù)識別出閉合區(qū)域。

再去掉一些多余的輪廓，就得到了魔方的所有小面。

金可明在此基礎(chǔ)上改進了形狀檢測算法，即使魔方小面帶有弧度、不是標準正方形也可以識別。

掃描好6個面后計算每個小面中顏色的平均值。

然后用CIDE2000算法計算出每個小面屬于哪種標準色。

最后按順序?qū)㈩伾幋a合成為一個字符串就可以作為魔方算法的輸入了。

下一步，機器人

金可明出生于荷蘭，自學中文后來到中國留學。

除了Qbr外他還編寫過一個為代碼自動生成文檔的Vim插件，并用文檔生成器（Documentation Generator）的英文字母開頭給插件命名為“Doge”，獲得Github 500星好評。

作為程序員的他看到這個擰魔方只需要不到1秒的機器人后決定自己也要做一個。

現(xiàn)在軟件部分寫好了，讓我們期待他何時能做出機器人吧。

Qbr項目地址：
https://github.com/kkoomen/qbr

參考鏈接：
[1]http://programmablebrick.blogspot.com/2017/02/rubiks-cube-tracker-using-opencv.html
[2]https://www.youtube.com/watch?v=ixTddQQ2Hs4

— 完 —

量子位 QbitAI · 頭條號簽約

關(guān)注我們，第一時間獲知前沿科技動態(tài)

前幾天發(fā)布的視頻，有部分粉絲找我要，那就公開給大家下載吧。

部分軟件的源代碼沒有做保存，有的呢涉及違fa。也不給大家公開發(fā)布了。后期能免費分享的東西我都會毫無保留的給大家發(fā)布出來！

感謝關(guān)注。這段時間我將會在和西瓜視頻平臺，做一套完整的易語言簡單腳本開發(fā)系列視頻教程！

Html魔方源碼

https://www.lanzous.com/i9p2gjg

視頻地址：https://www.ixigua.com/i6797636021107294728/

石頭剪刀布

https://www.lanzous.com/i9p1t2b

視頻地址：https://www.ixigua.com/i6797218487283483144/

箭頭射擊

https://www.lanzous.com/i9o82ad

視頻地址：https://www.ixigua.com/i6796844230112182796/

方是個結(jié)構(gòu)簡單而變化無窮的神奇玩具。那么如何在萬能的瀏覽器里模擬出魔方的無盡變換，又如何將其還原呢？下面讓我們一步步地來一探究竟吧。

魔方的抽象

拆解過魔方的同學可能知道，現(xiàn)實中魔方的內(nèi)部結(jié)構(gòu)包含了中軸、彈簧、螺絲等機械裝置。但當我們只是想要「模擬」它的時候，我們只需抓住它最顯著的性質(zhì)即可——3x3x3 的一組立方體：

基本概念

上圖演示了魔方最基本的思維模型。但光有這樣的感性認識還不夠：組成魔方的每個塊并非隨意安置，它們之間有著細微的區(qū)別：

• 位于魔方各角的塊稱為角塊，每個角塊均具有 3 個顏色。一個立方體有 8 個角，故而一個魔方也具有 8 個角塊。
• 位于魔方各棱上的塊稱為棱塊，每個棱塊均具有 2 個顏色。一個立方體有 12 條棱，故而一個魔方也具有 12 個棱塊。
• 位于魔方各面中心的塊稱為中心塊，每個中心塊僅有 1 個顏色。一個立方體有 6 個面，故而一個魔方也具有 6 個中心塊。
• 位于整個魔方中心的塊沒有顏色，在渲染和還原的過程中也不起到什么實際的用處，我們可以忽略這個塊。

將以上四種塊的數(shù)量相加，正好是 3^3=27 塊。對這些塊，你所能使用的唯一操作（或者說變換）方式，就是在不同面上的旋轉(zhuǎn)。那么，我們該如何標識出一次旋轉(zhuǎn)操作呢？

設(shè)想你的手里「端正地」拿著一個魔方，我們將此時面對你的那一面定義為 Front，背對的一面定義為 Back。類似地，我們有了 Left / Right / Upper / Down 來標識其余各面。當你旋轉(zhuǎn)某一面時，我們用這一面的簡寫（F / B / L / R / U / D）來標識在這一面上的一次順時針 90 度旋轉(zhuǎn)。對于一次逆時針的旋轉(zhuǎn)，我們則用 F' / U' 這樣帶 ' 的記號來表達。如果你旋轉(zhuǎn)了 180 度，那么可以用形如 R2 / U2 的方式表示。如下圖的 5 次操作，如果我們約定藍色一面為 Front，其旋轉(zhuǎn)序列就是 F' R' L' B' F'：

關(guān)于魔方的基礎(chǔ)結(jié)構(gòu)和變換方式，知道這些就足夠了。下面我們需要考慮這個問題：如何設(shè)計一個數(shù)據(jù)結(jié)構(gòu)來保存的魔方狀態(tài)，并使用編程語言來實現(xiàn)某個旋轉(zhuǎn)變換呢？

數(shù)據(jù)結(jié)構(gòu)

喜歡基于「面向?qū)ο蟆钩橄蟮耐瑢W可能很快就能想到，我們可以為每個塊設(shè)計一個 Block 基類，然后用形如 CornerBlock 和 EdgeBlock 的類來抽象棱塊和角塊，在每個角塊實例中還可以保存這個角塊到它相鄰三個棱塊的引用……這樣一個魔方的 Cube 對象只需持有對中心塊的引用，就可以基于各塊實例的鄰接屬性保存整個魔方了。

上面這種實現(xiàn)很類似于鏈表，它可以 O(1) 地實現(xiàn)「給定某個塊，查找其鄰接塊」的操作，但不難發(fā)現(xiàn)，它需要 O(N) 的復雜度來實現(xiàn)形如「某個位置的塊在哪里」這樣的查找操作，基于它的旋轉(zhuǎn)操作也并不十分符合直覺。相對地，另一種顯得「過于暴力」的方式反而相當實用：直接開辟一個長度為 27 的數(shù)組，在其中存儲每一塊的顏色信息即可。

為什么可以這樣呢？我們知道，數(shù)組在基于下標訪問時，具有 O(1) 的時間復雜度。而如果我們在一個三維坐標系中定位魔方的每一個塊，那么每個塊的空間坐標都可以唯一地映射到數(shù)組的下標上。更進一步地，我們可以令 x, y, z 分別取 -1, 0, 1 這三個值來表達一個塊在其方向上可能的位置，這時，例如前面所定義的一次 U 旋轉(zhuǎn)，剛好就是對所有 y 軸坐標值為 1 的塊的旋轉(zhuǎn)。這個良好的性質(zhì)很有利于實現(xiàn)對魔方的變換操作。

旋轉(zhuǎn)變換

在約定好數(shù)據(jù)結(jié)構(gòu)之后，我們?nèi)绾螌崿F(xiàn)對魔方的一次旋轉(zhuǎn)變換呢？可能有些同學會直接將這個操作與三維空間中的四階變換矩陣聯(lián)系起來。但只要注意到一次旋轉(zhuǎn)的角度都是 90 度的整數(shù)倍，我們可以利用數(shù)學性質(zhì)極大地簡化這一操作：

在旋轉(zhuǎn) 90 度時，旋轉(zhuǎn)面上每個角塊都旋轉(zhuǎn)到了該面上的「下一個」角塊的位置上，棱塊也是這樣。故而，我們只需要循環(huán)交替地在每個塊的「下一個」位置賦值，就能輕松地將塊「移動」到其新位置上。但這還不夠：每個新位置上的塊，還需要對其自身六個面的顏色做一次「自旋」，才能將它的朝向指向正確的位置。這也是一次交替的賦值操作。從而，一次三維空間繞某個面中心的旋轉(zhuǎn)操作，就被我們分解為了一次平移操作和一次繞各塊中心的旋轉(zhuǎn)操作。只需要 30 余行代碼，我們就能實現(xiàn)這一魔方最核心的變換機制：

rotate (center, clockwise=true) {
  const axis=center.indexOf(1) + center.indexOf(-1) + 1
  // Fix y direction in right-handed coordinate system.
  clockwise=center[1] !==0 ? !clockwise : clockwise
  // Fix directions whose faces are opposite to axis.
  clockwise=center[axis]===1 ? clockwise : !clockwise

  let cs=[[1, 1], [1, -1], [-1, -1], [-1, 1]] // corner coords
  let es=[[0, 1], [1, 0], [0, -1], [-1, 0]] // edge coords
  const prepareCoord=coord=> coord.splice(axis, 0, center[axis])
  cs.forEach(prepareCoord); es.forEach(prepareCoord)
  if (!clockwise) { cs=cs.reverse(); es=es.reverse() }

  // 移動每個塊到其新位置
  const rotateBlocks=([a, b, c, d])=> {
    const set=(a, b)=> { for (let i=0; i < 6; i++) a[i]=b[i] }
    const tmp=[]; set(tmp, a); set(a, d); set(d, c); set(c, b); set(b, tmp)
  }
  const colorsAt=coord=> this.getBlock(coord).colors
  rotateBlocks(cs.map(colorsAt)); rotateBlocks(es.map(colorsAt))

  // 調(diào)整每個塊的自旋朝向
  const swap=[
    [[F, U, B, D], [L, F, R, B], [L, U, R, D]],
    [[F, D, B, U], [F, L, B, R], [D, R, U, L]]
  ][clockwise ? 0 : 1][axis]
  const rotateFaces=coord=> {
    const block=colorsAt(coord)
    ;[block[swap[1]], block[swap[2]], block[swap[3]], block[swap[0]]]=[block[swap[0]], block[swap[1]], block[swap[2]], block[swap[3]]]
  }
  cs.forEach(rotateFaces); es.forEach(rotateFaces)
  return this
}
復制代碼

這個實現(xiàn)的效率應該不差：在筆者的瀏覽器里，上面的代碼可以支持每秒 30 萬次的旋轉(zhuǎn)變換。為什么在這里我們需要在意性能呢？在魔方的場景下，有一個非常不同的地方，即狀態(tài)的有效性與校驗。

熟悉魔方的同學應該知道，并不是隨便給每塊涂上不同顏色的魔方都是可以還原的。在普通的業(yè)務開發(fā)領(lǐng)域，數(shù)據(jù)的有效性和校驗常常可以通過類型系統(tǒng)來保證。但對于一個打亂的魔方，保證它的可解性則是一個困難的數(shù)學問題。故而我們在保存魔方狀態(tài)時，只有保存從六面同色的初始狀態(tài)到當前狀態(tài)下的所有變換步驟，才能保證這個狀態(tài)一定是可解的。這樣一來，反序列化一個魔方狀態(tài)的開銷就與操作步驟數(shù)量之間有了 O(N) 的關(guān)聯(lián)。好在一個實際把玩中的魔方狀態(tài)一般只會在 100 步之內(nèi)，故而上面以犧牲時間復雜度換取數(shù)據(jù)有效性的代價應當是值得的。另外，這個方式可以非常簡單地實現(xiàn)魔方任意狀態(tài)之間的時間旅行：從初始狀態(tài)走到任意一步的歷史狀態(tài)，都只需要疊加上它們之間一系列的旋轉(zhuǎn) diff 操作即可。這是一個很可靠的思維模型。

上面的實現(xiàn)中有一個特別之處：當坐標軸是 y 軸時，我們?yōu)樾D(zhuǎn)方向進行了一次取反操作。這初看起來并不符合直覺，但其背后卻是坐標系定義的問題：如果你推導過每個塊在順時針變換時所處的下一個位置，那么在高中教科書和 WebGL 所用的右手坐標系中，繞 y 軸旋轉(zhuǎn)時各個塊的下一個位置，其交換順序與 x 軸和 z 軸是相反的。反而在 DirectX 的左手坐標系中，旋轉(zhuǎn)操作的正負能完全和坐標系的朝向一致。筆者作為區(qū)區(qū)碼農(nóng)，并不了解這背后的對稱性是否蘊含了什么深刻的數(shù)學原理，希望數(shù)學大佬們解惑。

到此為止，我們已經(jīng)基本完成了對魔方狀態(tài)的抽象和變換算法的設(shè)計了。但相信很多同學可能更好奇的是這個問題：在瀏覽器環(huán)境下，我們該如何渲染出魔方呢？讓我們來看看吧。

魔方的渲染

在瀏覽器這個以無數(shù)的二維矩形作為排版原語的世界里，要想渲染魔方這樣的三維物體并不是件查個文檔寫幾行膠水代碼就可以搞定的事情。好在我們有 WebGL 這樣的三維圖形庫可供差遣（當然了，相信熟悉樣式的同學應該是可以使用 CSS 來渲染魔方的，可惜筆者的 CSS 水平很菜）。

WebGL 渲染基礎(chǔ)

由于魔方思維模型的簡單性，要渲染它并不需要使用圖形學中紋理、光照和陰影等高級特性，只需要最基本的幾何圖形繪制特性就足夠了。正因為如此，筆者在這里只使用了完全原生的 WebGL API 來繪制魔方。籠統(tǒng)地說，渲染魔方這樣的一組立方體，所需要的步驟大致如下：

1. 初始化著色器（編譯供 GPU 執(zhí)行的程序）
2. 向緩沖區(qū)中傳遞頂點和顏色數(shù)據(jù)（操作顯存）
3. 設(shè)置用于觀察的透視矩陣和模-視變換矩陣（傳遞變量給 GPU）
4. 調(diào)用 drawElements 或 drawArray 渲染一幀

在前文中，我們設(shè)計的數(shù)據(jù)結(jié)構(gòu)使用了長度為 27 的數(shù)組來存儲 [-1, -1, -1] 到 [1, 1, 1] 的一系列塊。在一個三重的 for 循環(huán)里，逐個將這些塊繪制到屏幕上的邏輯大概就像前面看到的這張圖：

需要注意的是，并不是越接近底層的代碼就一定越快。例如在最早的實現(xiàn)中，筆者直接通過循環(huán)調(diào)用來自（或者說抄自）MDN 的 3D 立方體例程來完成 27 個小塊的渲染。這時對于 27 個立方體區(qū)區(qū)不足千個頂點，60 幀繪制動畫時的 CPU 占用率都可能跑滿。經(jīng)過定位，發(fā)現(xiàn)重復的 CPU 與 GPU 交互是一個大忌：從 CPU 向 GPU 傳遞數(shù)據(jù)，以及最終對 GPU 繪圖 API 的調(diào)用，都具有較大的固定開銷。一般我們需要將一幀中 Draw Call 的數(shù)量控制在 20 個以內(nèi)，對于 27 個立方體就使用 27 次 Draw Call 的做法顯然是個反模式。在將代碼改造為一次批量傳入全部頂點并調(diào)用一次 drawElements 后，即可實現(xiàn)流暢的 60 幀動畫了 :)

旋轉(zhuǎn)動畫實現(xiàn)

在實現(xiàn)基本的渲染機制后，魔方整體的旋轉(zhuǎn)效果可以通過對模-視矩陣做矩陣乘法來實現(xiàn)。模-視矩陣會在頂點著色器由 GPU 中對每一個頂點并行地計算，得到頂點變換后的 gl_Position 位置。但對于單個面的旋轉(zhuǎn)，我們選擇了先在 CPU 中計算好頂點位置，再將其傳入頂點緩沖區(qū)。這和魔方旋轉(zhuǎn)動畫的實現(xiàn)原理直接相關(guān)：

• 在一次某個面的旋轉(zhuǎn)過程中，魔方的數(shù)據(jù)模型不發(fā)生改變，僅改變受影響的頂點所在位置。
• 在旋轉(zhuǎn)結(jié)束時，我們調(diào)用上文中實現(xiàn)的 rotate API 來「瞬間旋轉(zhuǎn)好」魔方的數(shù)據(jù)模型，而后再多繪制一幀。

我們首先需要設(shè)計用于渲染一幀的 render API。考慮到魔方在繪制時可能存在對某個面一定程度的旋轉(zhuǎn)，這個無狀態(tài)的渲染 API 接口形如：

render (rX=0, rY=0, moveFace=null, moveAngle=0) {
  if (!this.gl) throw new Error('Missing WebGL context!')
  this.buffer=getBuffer(this.gl, this.blocks, moveFace, moveAngle)
  renderFrame(this.gl, this.programInfo, this.buffer, rX, rY)
}
復制代碼

而對單個面的旋轉(zhuǎn)過程中，我們可以使用瀏覽器的 requestAnimationFrame API 來實現(xiàn)基本的時序控制。一次調(diào)用 animate 的旋轉(zhuǎn)返回一個在單次旋轉(zhuǎn)結(jié)束時 resolve 的 Promise，其實現(xiàn)如下：

animate (move=null, duration=500) {
  if (move && move.length===0) return Promise.resolve()
  if (!move || this.__ANIMATING) throw new Error('Unable to animate!')

  this.__ANIMATING=true
  let k=move.includes("'") ? 1 : -1
  if (/B|D|L/.test(move)) k=k * -1
  const beginTime=+new Date()
  return new Promise((resolve, reject)=> {
    const tick=()=> {
      const diff=+new Date() - beginTime
      const percentage=diff / duration
      const face=move.replace("'", '')
      if (percentage < 1) {
        this.render(this.rX, this.rY, face, 90 * percentage * k)
        window.requestAnimationFrame(tick)
      } else {
        this.move(move)
        this.render(this.rX, this.rY, null, 0)
        this.__ANIMATING=false
        resolve()
      }
    }
    window.requestAnimationFrame(tick)
  })
}
復制代碼

連續(xù)旋轉(zhuǎn)實現(xiàn)

在實現(xiàn)了單次旋轉(zhuǎn)后，如何支持連續(xù)的多次旋轉(zhuǎn)呢？本著能偷懶就偷懶的想法，筆者對上面的函數(shù)進行了不改動已有邏輯的遞歸化改造，只需要在原函數(shù)入口處加入如下幾行，就可以使支持傳入數(shù)組為參數(shù)來遞歸調(diào)用自身，并在傳入的連續(xù)動畫數(shù)組長度為 1 時作為遞歸的出口，從而輕松地實現(xiàn)連續(xù)的動畫效果：

if (Array.isArray(move) && move.length > 1) {
  const lastMove=move.pop()
  // 返回遞歸得到的 Promise
  return this.animate(move).then(()=> this.animate(lastMove))
} else if (move.length===1) move=move[0] // 繼續(xù)已有邏輯
復制代碼

到這里，一個可以供人體驗的魔方基本就可以在瀏覽器里跑起來了。但這還不是我們最終的目標：我們該怎么自動還原一個魔方呢？

魔方的還原

魔方的還原算法在學術(shù)界已有很深入的研究，計算機在 20 步之內(nèi)可以解出任意狀態(tài)的魔方，也有成熟的輪子可以直接調(diào)用。但作為一個（高中時）曾經(jīng)的魔方業(yè)余愛好者，筆者這里更關(guān)注的是「如何模擬出我自己還原魔方的操作」，故而在這里我們要介紹的是簡單易懂的 CFOP 層先算法。

在開始前，有必要強調(diào)一個前文中一筆帶過的概念：在旋轉(zhuǎn)時，魔方中心塊之間的相對位置始終不會發(fā)生變化。如下圖：

因此，在魔方旋轉(zhuǎn)時，我們只需關(guān)注角塊和棱塊是否歸位即可。在 CFOP 層先法中，歸位全部角塊和棱塊的步驟，被分為了逐次遞進的四步：

1. 還原底部四個棱塊，構(gòu)建出「十字」。
2. 分組還原底層和第二層的所有角塊和棱塊。
3. 調(diào)整頂層塊朝向，保證頂面同色。
4. 調(diào)整頂層塊順序，完成整個求解。

讓我們依次來看看每一步都發(fā)生了什么吧。

底層十字

這一步可以說是最簡單也最難的，在此我們的目標是還原四個底部棱塊，像這樣：

對一個完全打亂的魔方，每個目標棱塊都可能以兩種不同的朝向出現(xiàn)在任意一個棱塊的位置上。為什么有兩種朝向呢？請看下圖：

這是最簡單的一種情形，此時直接做一次 R2 旋轉(zhuǎn)即可使紅白棱塊歸位。但下面這種情況也是完全合法的：

這時由于棱塊的朝向不同，所需的步驟就完全不同了。但總的來說，構(gòu)成十字所需的棱塊可能出現(xiàn)的位置總是有限的。拆解分類出所有可能的情形后，我們不難使用貪心策略來匹配：

1. 每次找到一個構(gòu)成十字所需的棱塊，求出它到目標位置的一串移動步驟。
2. 在不影響其他十字棱塊的前提下將其歸位，而后尋找下一個棱塊。

這個最簡單的策略很接近語法分析中向前看符號數(shù)量為 1 時的算法，不過這里不需要回溯。實現(xiàn)機制可以抽象如下：

solveCross () {
  const clonedCube=new Cube(null, this.cube.moves)
  const moveSteps=[]
  while (true) {
    const lostEdgeCoords=findCrossCoords(clonedCube)
    if (!lostEdgeCoords.length) break
    moveSteps.push(solveCrossEdge(clonedCube, lostEdgeCoords[0]))
  }
  return moveSteps
}
復制代碼

這個實現(xiàn)原理并不復雜，其代價就是過小的局部最優(yōu)造成了較多的冗余步驟。如果同時觀察 2 個甚至更多的棱塊狀態(tài)并將其一并歸位，其效率顯然能得到提升（這時的實現(xiàn)難度也是水漲船高）。作為對比，一流的魔方玩家可以在 7 步內(nèi)完成十字，但這個算法實現(xiàn)卻需要 20 步左右——不過這里意思已經(jīng)到了，各位看官就先不要太苛刻啦。

底部兩層

這里的目標是在底部十字完成的基礎(chǔ)上，完成底部兩層所有塊的歸位。我們的目標是實現(xiàn)這樣的狀態(tài)：

這個步驟中，我們以 Slot 和 Pair 的概念作為還原的基本元素。相鄰的十字之間所間隔的一個棱和一個角，構(gòu)成了一個 Slot，而它們所對應的兩個目標塊則稱為一個 Pair。故而這個步驟中，我們只需要重復四次將 Pair 放入 Slot 中的操作即可。一次最簡單的操作大概是這樣的：

上圖將頂層的一對 Pair 放入了藍紅相間的 Slot 中。類似于之前解十字時的情形，這一步中的每個棱塊和角塊也有不同的位置和朝向。如果它們都在頂層，那么我們可以通過已有的匹配規(guī)則來實現(xiàn)匹配；如果它們在其它的 Slot 中，那么我們就遞歸地執(zhí)行「將 Pair 從其它 Slot 中旋出」的算法，直到這組 Pair 都位于頂層為止。

這一步的還原算法與下面的步驟相當接近，稍后一并介紹。

頂層同色與頂層順序

完成了前兩層的還原后，我們最后所需要處理的就是頂層的 8 個棱塊與角塊了。首先是頂面同色的步驟，將各塊調(diào)整到正確的朝向，實現(xiàn)頂面同色（一般采用白色作為底面，此時按照約定，黃色為頂面）：

而后是頂層順序的調(diào)整。這一步在不改變棱與角朝向的前提下，改變它們的排列順序，最終完成整個魔方的還原：

從前兩層的還原到頂層的還原步驟中，都有大量的魔方公式規(guī)則可供匹配使用。如何將這些現(xiàn)成的規(guī)則應用到還原算法中呢？我們可以使用規(guī)則驅(qū)動的方式來使用它們。

規(guī)則驅(qū)動設(shè)計

了解編譯過程的同學應該知道，語法分析的過程可以通過編寫一系列的語法規(guī)則來實現(xiàn)。而在魔方還原時，我們也有大量的規(guī)則可供使用。一條規(guī)則的匹配部分大概是這樣的：

在頂面同色過程中，滿足上述 "pattern" 的頂面，可以通過 U L U' R' U L' U' R 的步驟來還原。類似地，在還原頂層順序時，規(guī)則的匹配方式形如這樣：

滿足這條規(guī)則的頂層狀態(tài)可以通過該規(guī)則所定義的步驟求解：R2 U' R' U' R U R U R U' R。這樣一來，只需要實現(xiàn)對規(guī)則的匹配和執(zhí)行操作，規(guī)則的邏輯就可以完全與代碼邏輯解耦，變?yōu)榭膳渲玫?JSON 格式數(shù)據(jù)。用于還原前兩層的一條規(guī)則格式形如：

{
  match: { [E]: topEdge(COLOR_F, E), [SE]: SE_D_AS_F },
  moves: "U (R U' R')"
}
復制代碼

頂層同色的規(guī)則格式形如：

{
  match: { [NW]: L, [NE]: R, [SE]: R, [SW]: L },
  moves: "R U R' U R U' R' U R U U R'"
}
復制代碼

頂面順序的規(guī)則格式形如：

{
  match: { [N]: W, [W]: [E], [E]: N },
  moves: "R R U' R' U' R U R U R U' R"
}
復制代碼

這里的 NW / E / SE 是筆者的實現(xiàn)中基于九宮格東西南北方向定位的簡寫。在實現(xiàn)了對規(guī)則的自動匹配和應用之后，CFOP 中后面三步的實現(xiàn)方式可以說大同小異，主要的工作集中在一些與旋轉(zhuǎn)相關(guān)的 mapping 處理。

規(guī)則的自測試

在整個還原過程中，一共有上百條規(guī)則需要匹配。對于這么多的規(guī)則，該如何保證它們的正確性呢？在 TDD 測試驅(qū)動開發(fā)的理念中，開發(fā)者需要通過編寫各種繁冗的測試用例來實現(xiàn)對代碼邏輯的覆蓋。但在魔方領(lǐng)域，筆者發(fā)現(xiàn)了一種優(yōu)雅得多的性質(zhì)：任何一條規(guī)則本身，就是自己的測試用例！如這條規(guī)則：

{
  match: { [N]: W, [W]: [E], [E]: N },
  moves: "R R U' R' U' R U R U R U' R"
}
復制代碼

我們只需要將 moves 中的每一步順序顛倒地輸入初始狀態(tài)的魔方，就可以用這個狀態(tài)來驗證規(guī)則是否能夠匹配，以及魔方是否能基于該規(guī)則還原了。這個性質(zhì)使得我很容易地編寫了下面這樣簡單的代碼，自動驗證每條輸入規(guī)則的正確性：

const flip=moves=> moves.map(x=> x.length > 1 ? x[0] : x + "'").reverse()

OLL.forEach(rule=> {
  const rMoves=flip(rule.moves)
  const cube=new Cube(null, rMoves)
  if (
    matchOrientationRule(cube, rule) &&
    isOrientationSolved(cube.move(rule.moves))
  ) {
    console.log('OLL test pass', rule.id)
  } else console.error('Error OLL rule match', rule.id)
})
復制代碼

在這個支持自測試的規(guī)則匹配算法基礎(chǔ)上，求解魔方的全部步驟就這樣計算出來了 :)

成果與后記

經(jīng)過半個多月業(yè)余時間的折騰，筆者實現(xiàn)了一個非常小巧的魔方求解模擬器 Freecube。它支持三階魔方狀態(tài)的渲染和逐步求解，還提供了旋轉(zhuǎn)與求解的 API 可供復用。由于它沒有使用任何第三方依賴并使用了各種力求精簡的「技巧」，因而它的體積被控制在了壓縮后 10KB 內(nèi)。歡迎移步 GitHub 觀光 XD

Freecube 案例地址：https://ewind.us/h5/freecube/

Freecube 是筆者在很多地方忙里偷閑地實現(xiàn)的：咖啡廳、動車、公交車甚至飯桌上……即便寫不了代碼的場合，也可以拿平板寫寫畫畫來設(shè)計它。它的靈感來自于 @youngdro 神奇的吉他和弦算法博文，

https://juejin.im/post/5b2627d051882574ac7848a4

另外感謝大佬的指點和某人對 README 文檔的審校 XD

Github地址：https://github.com/doodlewind/freecube

原地址：https://juejin.im/post/5b837c0b51882542d950efb4