整合營銷服務商
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
晨 發自 凹非寺
量子位 報道 | 公眾號 QbitAI
魔方解不開了怎么辦，讓程序來幫你。
只需用攝像頭把魔方的六個面掃描一遍就能直接給出還原步驟。
即使你的魔方不是標準配色或房間的照明情況特殊也可以通過顏色校準模式來識別。
這款荷蘭小哥發布的3階魔方解算器“Qbr”已經在GitHub上開源。
小哥還貼心地把魔方公式中的步驟代號翻譯為人話，并且支持中文，可以直接按照描述操作。
中文是小哥自學的，他還給自己起了個中文名叫“金可明”。
解算結果大概是這樣的。
步驟數: 20
復原教程: B2 U2 F' R U D' L' B' U L F U F2 R2 F2 D' F2 D R2 D2
1. 將魔方的后面旋轉180°。
2. 將魔方的頂層旋轉180°。
3. 將魔方的前面向左旋轉90°。
...
20.將魔方的底層向右旋轉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運行時要注意每次運行前都要激活虛擬環境
$ source ./env/bin/activate
$ ./src/qbr.py操作也非常簡單，可以先按L鍵循環切換語言到中文，C鍵進入/退出顏色校準模式。
掃描模式下按空格鍵保存識別好的一個面，6個面都識別好之后按esc就可以在終端里看到結果了。
△沒有魔方只能拿照片測試一下
如果需要將結果翻譯成“人話”，則運行時加入參數“-n”即可。
解魔方的算法方面Qbr直接使用了開源的Kociemba算法庫，該算法可以在20步以內還原任意3階魔方。
那么問題來了，如何將攝像頭掃描的圖像輸入給算法呢？
Qbr使用開源的計算機視覺庫OpenCV。
首先將圖像灰度化，稍微做一下模糊，然后用邊緣檢測識別出魔方小面的邊緣。
把所有邊緣加粗，使屬于一個邊緣的多條線可以合并。
將邊緣疊加到原始圖像上，使用OpenCV的approxPolyDP函數識別出閉合區域。
再去掉一些多余的輪廓，就得到了魔方的所有小面。
金可明在此基礎上改進了形狀檢測算法，即使魔方小面帶有弧度、不是標準正方形也可以識別。
掃描好6個面后計算每個小面中顏色的平均值。
然后用CIDE2000算法計算出每個小面屬于哪種標準色。
最后按順序將顏色編碼合成為一個字符串就可以作為魔方算法的輸入了。
金可明的GitHub頁面
金可明出生于荷蘭，自學中文后來到中國留學。
除了Qbr外他還編寫過一個為代碼自動生成文檔的Vim插件，并用文檔生成器（Documentation Generator）的英文字母開頭給插件命名為“Doge”，獲得Github 500星好評。
作為程序員的他看到這個擰魔方只需要不到1秒的機器人后決定自己也要做一個。
△ Jay Flatland于2016年發布，0.9秒的成績打破了世界紀錄
現在軟件部分寫好了，讓我們期待他何時能做出機器人吧。
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 · 頭條號簽約
關注我們，第一時間獲知前沿科技動態
前幾天發布的視頻，有部分粉絲找我要，那就公開給大家下載吧。
部分軟件的源代碼沒有做保存，有的呢涉及違fa。也不給大家公開發布了。后期能免費分享的東西我都會毫無保留的給大家發布出來！
感謝關注。這段時間我將會在和西瓜視頻平臺，做一套完整的易語言簡單腳本開發系列視頻教程！
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/
方是個結構簡單而變化無窮的神奇玩具。那么如何在萬能的瀏覽器里模擬出魔方的無盡變換，又如何將其還原呢？下面讓我們一步步地來一探究竟吧。
拆解過魔方的同學可能知道，現實中魔方的內部結構包含了中軸、彈簧、螺絲等機械裝置。但當我們只是想要「模擬」它的時候，我們只需抓住它最顯著的性質即可——3x3x3 的一組立方體：
上圖演示了魔方最基本的思維模型。但光有這樣的感性認識還不夠：組成魔方的每個塊并非隨意安置，它們之間有著細微的區別：
將以上四種塊的數量相加，正好是 3^3=27 塊。對這些塊，你所能使用的唯一操作（或者說變換）方式，就是在不同面上的旋轉。那么，我們該如何標識出一次旋轉操作呢？
設想你的手里「端正地」拿著一個魔方，我們將此時面對你的那一面定義為 Front，背對的一面定義為 Back。類似地，我們有了 Left / Right / Upper / Down 來標識其余各面。當你旋轉某一面時，我們用這一面的簡寫（F / B / L / R / U / D）來標識在這一面上的一次順時針 90 度旋轉。對于一次逆時針的旋轉，我們則用 F' / U' 這樣帶 ' 的記號來表達。如果你旋轉了 180 度，那么可以用形如 R2 / U2 的方式表示。如下圖的 5 次操作，如果我們約定藍色一面為 Front，其旋轉序列就是 F' R' L' B' F'：
關于魔方的基礎結構和變換方式，知道這些就足夠了。下面我們需要考慮這個問題：如何設計一個數據結構來保存的魔方狀態，并使用編程語言來實現某個旋轉變換呢？
喜歡基于「面向對象」抽象的同學可能很快就能想到，我們可以為每個塊設計一個 Block 基類，然后用形如 CornerBlock 和 EdgeBlock 的類來抽象棱塊和角塊，在每個角塊實例中還可以保存這個角塊到它相鄰三個棱塊的引用……這樣一個魔方的 Cube 對象只需持有對中心塊的引用，就可以基于各塊實例的鄰接屬性保存整個魔方了。
上面這種實現很類似于鏈表，它可以 O(1) 地實現「給定某個塊，查找其鄰接塊」的操作，但不難發現，它需要 O(N) 的復雜度來實現形如「某個位置的塊在哪里」這樣的查找操作，基于它的旋轉操作也并不十分符合直覺。相對地，另一種顯得「過于暴力」的方式反而相當實用：直接開辟一個長度為 27 的數組，在其中存儲每一塊的顏色信息即可。
為什么可以這樣呢？我們知道，數組在基于下標訪問時，具有 O(1) 的時間復雜度。而如果我們在一個三維坐標系中定位魔方的每一個塊，那么每個塊的空間坐標都可以唯一地映射到數組的下標上。更進一步地，我們可以令 x, y, z 分別取 -1, 0, 1 這三個值來表達一個塊在其方向上可能的位置，這時，例如前面所定義的一次 U 旋轉，剛好就是對所有 y 軸坐標值為 1 的塊的旋轉。這個良好的性質很有利于實現對魔方的變換操作。
在約定好數據結構之后，我們如何實現對魔方的一次旋轉變換呢？可能有些同學會直接將這個操作與三維空間中的四階變換矩陣聯系起來。但只要注意到一次旋轉的角度都是 90 度的整數倍，我們可以利用數學性質極大地簡化這一操作：
在旋轉 90 度時，旋轉面上每個角塊都旋轉到了該面上的「下一個」角塊的位置上，棱塊也是這樣。故而，我們只需要循環交替地在每個塊的「下一個」位置賦值，就能輕松地將塊「移動」到其新位置上。但這還不夠：每個新位置上的塊，還需要對其自身六個面的顏色做一次「自旋」，才能將它的朝向指向正確的位置。這也是一次交替的賦值操作。從而，一次三維空間繞某個面中心的旋轉操作，就被我們分解為了一次平移操作和一次繞各塊中心的旋轉操作。只需要 30 余行代碼，我們就能實現這一魔方最核心的變換機制：
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))
// 調整每個塊的自旋朝向
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
}
復制代碼這個實現的效率應該不差：在筆者的瀏覽器里，上面的代碼可以支持每秒 30 萬次的旋轉變換。為什么在這里我們需要在意性能呢？在魔方的場景下，有一個非常不同的地方，即狀態的有效性與校驗。
熟悉魔方的同學應該知道，并不是隨便給每塊涂上不同顏色的魔方都是可以還原的。在普通的業務開發領域，數據的有效性和校驗常常可以通過類型系統來保證。但對于一個打亂的魔方，保證它的可解性則是一個困難的數學問題。故而我們在保存魔方狀態時，只有保存從六面同色的初始狀態到當前狀態下的所有變換步驟，才能保證這個狀態一定是可解的。這樣一來，反序列化一個魔方狀態的開銷就與操作步驟數量之間有了 O(N) 的關聯。好在一個實際把玩中的魔方狀態一般只會在 100 步之內，故而上面以犧牲時間復雜度換取數據有效性的代價應當是值得的。另外，這個方式可以非常簡單地實現魔方任意狀態之間的時間旅行：從初始狀態走到任意一步的歷史狀態，都只需要疊加上它們之間一系列的旋轉 diff 操作即可。這是一個很可靠的思維模型。
上面的實現中有一個特別之處：當坐標軸是 y 軸時，我們為旋轉方向進行了一次取反操作。這初看起來并不符合直覺，但其背后卻是坐標系定義的問題：如果你推導過每個塊在順時針變換時所處的下一個位置，那么在高中教科書和 WebGL 所用的右手坐標系中，繞 y 軸旋轉時各個塊的下一個位置，其交換順序與 x 軸和 z 軸是相反的。反而在 DirectX 的左手坐標系中，旋轉操作的正負能完全和坐標系的朝向一致。筆者作為區區碼農，并不了解這背后的對稱性是否蘊含了什么深刻的數學原理，希望數學大佬們解惑。
到此為止，我們已經基本完成了對魔方狀態的抽象和變換算法的設計了。但相信很多同學可能更好奇的是這個問題：在瀏覽器環境下，我們該如何渲染出魔方呢？讓我們來看看吧。
在瀏覽器這個以無數的二維矩形作為排版原語的世界里，要想渲染魔方這樣的三維物體并不是件查個文檔寫幾行膠水代碼就可以搞定的事情。好在我們有 WebGL 這樣的三維圖形庫可供差遣（當然了，相信熟悉樣式的同學應該是可以使用 CSS 來渲染魔方的，可惜筆者的 CSS 水平很菜）。
由于魔方思維模型的簡單性，要渲染它并不需要使用圖形學中紋理、光照和陰影等高級特性，只需要最基本的幾何圖形繪制特性就足夠了。正因為如此，筆者在這里只使用了完全原生的 WebGL API 來繪制魔方。籠統地說，渲染魔方這樣的一組立方體，所需要的步驟大致如下：
在前文中，我們設計的數據結構使用了長度為 27 的數組來存儲 [-1, -1, -1] 到 [1, 1, 1] 的一系列塊。在一個三重的 for 循環里，逐個將這些塊繪制到屏幕上的邏輯大概就像前面看到的這張圖：
需要注意的是，并不是越接近底層的代碼就一定越快。例如在最早的實現中，筆者直接通過循環調用來自（或者說抄自）MDN 的 3D 立方體例程來完成 27 個小塊的渲染。這時對于 27 個立方體區區不足千個頂點，60 幀繪制動畫時的 CPU 占用率都可能跑滿。經過定位，發現重復的 CPU 與 GPU 交互是一個大忌：從 CPU 向 GPU 傳遞數據，以及最終對 GPU 繪圖 API 的調用，都具有較大的固定開銷。一般我們需要將一幀中 Draw Call 的數量控制在 20 個以內，對于 27 個立方體就使用 27 次 Draw Call 的做法顯然是個反模式。在將代碼改造為一次批量傳入全部頂點并調用一次 drawElements 后，即可實現流暢的 60 幀動畫了 :)
在實現基本的渲染機制后，魔方整體的旋轉效果可以通過對模-視矩陣做矩陣乘法來實現。模-視矩陣會在頂點著色器由 GPU 中對每一個頂點并行地計算，得到頂點變換后的 gl_Position 位置。但對于單個面的旋轉，我們選擇了先在 CPU 中計算好頂點位置，再將其傳入頂點緩沖區。這和魔方旋轉動畫的實現原理直接相關：
我們首先需要設計用于渲染一幀的 render API。考慮到魔方在繪制時可能存在對某個面一定程度的旋轉，這個無狀態的渲染 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)
}
復制代碼而對單個面的旋轉過程中，我們可以使用瀏覽器的 requestAnimationFrame API 來實現基本的時序控制。一次調用 animate 的旋轉返回一個在單次旋轉結束時 resolve 的 Promise，其實現如下：
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)
})
}
復制代碼在實現了單次旋轉后，如何支持連續的多次旋轉呢？本著能偷懶就偷懶的想法，筆者對上面的函數進行了不改動已有邏輯的遞歸化改造，只需要在原函數入口處加入如下幾行，就可以使支持傳入數組為參數來遞歸調用自身，并在傳入的連續動畫數組長度為 1 時作為遞歸的出口，從而輕松地實現連續的動畫效果：
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] // 繼續已有邏輯
復制代碼到這里，一個可以供人體驗的魔方基本就可以在瀏覽器里跑起來了。但這還不是我們最終的目標：我們該怎么自動還原一個魔方呢？
魔方的還原算法在學術界已有很深入的研究，計算機在 20 步之內可以解出任意狀態的魔方，也有成熟的輪子可以直接調用。但作為一個（高中時）曾經的魔方業余愛好者，筆者這里更關注的是「如何模擬出我自己還原魔方的操作」，故而在這里我們要介紹的是簡單易懂的 CFOP 層先算法。
在開始前，有必要強調一個前文中一筆帶過的概念：在旋轉時，魔方中心塊之間的相對位置始終不會發生變化。如下圖：
因此，在魔方旋轉時，我們只需關注角塊和棱塊是否歸位即可。在 CFOP 層先法中，歸位全部角塊和棱塊的步驟，被分為了逐次遞進的四步：
讓我們依次來看看每一步都發生了什么吧。
這一步可以說是最簡單也最難的，在此我們的目標是還原四個底部棱塊，像這樣：
對一個完全打亂的魔方，每個目標棱塊都可能以兩種不同的朝向出現在任意一個棱塊的位置上。為什么有兩種朝向呢？請看下圖：
這是最簡單的一種情形，此時直接做一次 R2 旋轉即可使紅白棱塊歸位。但下面這種情況也是完全合法的：
這時由于棱塊的朝向不同，所需的步驟就完全不同了。但總的來說，構成十字所需的棱塊可能出現的位置總是有限的。拆解分類出所有可能的情形后，我們不難使用貪心策略來匹配：
這個最簡單的策略很接近語法分析中向前看符號數量為 1 時的算法，不過這里不需要回溯。實現機制可以抽象如下：
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
}
復制代碼這個實現原理并不復雜，其代價就是過小的局部最優造成了較多的冗余步驟。如果同時觀察 2 個甚至更多的棱塊狀態并將其一并歸位，其效率顯然能得到提升（這時的實現難度也是水漲船高）。作為對比，一流的魔方玩家可以在 7 步內完成十字，但這個算法實現卻需要 20 步左右——不過這里意思已經到了，各位看官就先不要太苛刻啦。
這里的目標是在底部十字完成的基礎上，完成底部兩層所有塊的歸位。我們的目標是實現這樣的狀態：
這個步驟中，我們以 Slot 和 Pair 的概念作為還原的基本元素。相鄰的十字之間所間隔的一個棱和一個角，構成了一個 Slot，而它們所對應的兩個目標塊則稱為一個 Pair。故而這個步驟中，我們只需要重復四次將 Pair 放入 Slot 中的操作即可。一次最簡單的操作大概是這樣的：
上圖將頂層的一對 Pair 放入了藍紅相間的 Slot 中。類似于之前解十字時的情形，這一步中的每個棱塊和角塊也有不同的位置和朝向。如果它們都在頂層，那么我們可以通過已有的匹配規則來實現匹配；如果它們在其它的 Slot 中，那么我們就遞歸地執行「將 Pair 從其它 Slot 中旋出」的算法，直到這組 Pair 都位于頂層為止。
這一步的還原算法與下面的步驟相當接近，稍后一并介紹。
完成了前兩層的還原后，我們最后所需要處理的就是頂層的 8 個棱塊與角塊了。首先是頂面同色的步驟，將各塊調整到正確的朝向，實現頂面同色（一般采用白色作為底面，此時按照約定，黃色為頂面）：
而后是頂層順序的調整。這一步在不改變棱與角朝向的前提下，改變它們的排列順序，最終完成整個魔方的還原：
從前兩層的還原到頂層的還原步驟中，都有大量的魔方公式規則可供匹配使用。如何將這些現成的規則應用到還原算法中呢？我們可以使用規則驅動的方式來使用它們。
了解編譯過程的同學應該知道，語法分析的過程可以通過編寫一系列的語法規則來實現。而在魔方還原時，我們也有大量的規則可供使用。一條規則的匹配部分大概是這樣的：
在頂面同色過程中，滿足上述 "pattern" 的頂面，可以通過 U L U' R' U L' U' R 的步驟來還原。類似地，在還原頂層順序時，規則的匹配方式形如這樣：
滿足這條規則的頂層狀態可以通過該規則所定義的步驟求解：R2 U' R' U' R U R U R U' R。這樣一來，只需要實現對規則的匹配和執行操作，規則的邏輯就可以完全與代碼邏輯解耦，變為可配置的 JSON 格式數據。用于還原前兩層的一條規則格式形如：
{
match: { [E]: topEdge(COLOR_F, E), [SE]: SE_D_AS_F },
moves: "U (R U' R')"
}
復制代碼頂層同色的規則格式形如：
{
match: { [NW]: L, [NE]: R, [SE]: R, [SW]: L },
moves: "R U R' U R U' R' U R U U R'"
}
復制代碼頂面順序的規則格式形如：
{
match: { [N]: W, [W]: [E], [E]: N },
moves: "R R U' R' U' R U R U R U' R"
}
復制代碼這里的 NW / E / SE 是筆者的實現中基于九宮格東西南北方向定位的簡寫。在實現了對規則的自動匹配和應用之后，CFOP 中后面三步的實現方式可以說大同小異，主要的工作集中在一些與旋轉相關的 mapping 處理。
在整個還原過程中，一共有上百條規則需要匹配。對于這么多的規則，該如何保證它們的正確性呢？在 TDD 測試驅動開發的理念中，開發者需要通過編寫各種繁冗的測試用例來實現對代碼邏輯的覆蓋。但在魔方領域，筆者發現了一種優雅得多的性質：任何一條規則本身，就是自己的測試用例！如這條規則：
{
match: { [N]: W, [W]: [E], [E]: N },
moves: "R R U' R' U' R U R U R U' R"
}
復制代碼我們只需要將 moves 中的每一步順序顛倒地輸入初始狀態的魔方，就可以用這個狀態來驗證規則是否能夠匹配，以及魔方是否能基于該規則還原了。這個性質使得我很容易地編寫了下面這樣簡單的代碼，自動驗證每條輸入規則的正確性：
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)
})
復制代碼在這個支持自測試的規則匹配算法基礎上，求解魔方的全部步驟就這樣計算出來了 :)
經過半個多月業余時間的折騰，筆者實現了一個非常小巧的魔方求解模擬器 Freecube。它支持三階魔方狀態的渲染和逐步求解，還提供了旋轉與求解的 API 可供復用。由于它沒有使用任何第三方依賴并使用了各種力求精簡的「技巧」，因而它的體積被控制在了壓縮后 10KB 內。歡迎移步 GitHub 觀光 XD
Freecube 案例地址：https://ewind.us/h5/freecube/
Freecube 是筆者在很多地方忙里偷閑地實現的：咖啡廳、動車、公交車甚至飯桌上……即便寫不了代碼的場合，也可以拿平板寫寫畫畫來設計它。它的靈感來自于 @youngdro 神奇的吉他和弦算法博文，
https://juejin.im/post/5b2627d051882574ac7848a4
另外感謝大佬的指點和某人對 README 文檔的審校 XD
Github地址：https://github.com/doodlewind/freecube
原地址：https://juejin.im/post/5b837c0b51882542d950efb4
*請認真填寫需求信息，我們會在24小時內與您取得聯系。
