基于軟件的魔方解算器

第一步很簡單，我們給魔方的一面拍照

第 1 步 - 初始照片

?

?

第二步是創(chuàng)建圖像的灰度副本并應(yīng)用抗噪濾鏡

第 2 步 - 帶抗噪濾波器的灰度

?

?

第三步是使用 Canny Edge Detection 找到圖像中的所有邊緣

第 3 步 - Canny 邊緣檢測

?

?

第四步是擴(kuò)大邊緣。我們想讓它們更厚，因?yàn)檫@樣更容易找到立方體的正方形。

第 4 步 - 擴(kuò)大邊緣

?

?

第五步是找到膨脹圖像中所有形狀的輪廓。在下圖中，藍(lán)線是圖像中的各種輪廓。紅線是每個輪廓的近似形狀。我們檢查紅線的所有形狀以找到看起來像正方形的那些（有四個角，每個角大約為 90 度，等等）。如果我們認(rèn)為輪廓是正方形，我們會將該輪廓顯示為綠色。

第 5 步 - 尋找輪廓

?

?

第六步去除非方形輪廓

第 6 步 - 刪除非正方形

?

?

第七步是去除巨大的輪廓。上圖中只有一個巨大的輪廓，它是圍繞著外邊緣的一個輪廓，幾乎囊括了整個圖像。

第 7 步 - 去除巨大的輪廓

?

?

第八步是去除矮輪廓，這些輪廓太小而不能成為魔方。

第 8 步 - 去除矮化輪廓

?

?

第九步也是最后一步是確定立方體的大小、立方體的邊界并移除立方體邊界外的任何輪廓

第 9 步 - 確定立方體大小和邊界

?

我們對所有六個面執(zhí)行上述步驟，并提取 5x5x5 魔方的所有 150 個正方形的 RGB 值。

?

軟件 - 立方體狀態(tài)的 RGB 值

我們現(xiàn)在需要獲取所有 150 個方塊的 RGB 值，并將每個方塊減少為六種顏色（白色、黃色、紅色、橙色、綠色和藍(lán)色）中的一種。這將為我們提供計算立方體的解所需的立方體狀態(tài)。

此圖像顯示從上一步圖像中提取的每個方塊的顏色。請注意，顏色有一些變化，并非所有白色方塊都是完全相同的白色，橙色和紅色有時看起來非常相似，等等。

原始 RGB 值

?

為了將每個 RGB 值減少到六種顏色（白色、黃色等）中的一種，我們將對顏色進(jìn)行排序。一旦對它們進(jìn)行排序，我們就可以輕松地將它們分成六組，大小相等，并為每組分配一個顏色名稱。

對人類來說，顏色分類很容易，但事實(shí)證明，對計算機(jī)來說，這是相當(dāng)具有挑戰(zhàn)性的。如果我們采用上面的顏色并簡單地按照它們的 RGB 值對它們進(jìn)行排序，我們將得到以下結(jié)果，您可以看到它根本不是按照您或我對這些顏色進(jìn)行排序的順序。

RGB排序

?

如果我們改為按 HSV（色調(diào)、飽和度、值）對它們進(jìn)行排序，排序會更好但仍然不正確：

HSV排序

?

經(jīng)過多次試驗(yàn)和錯誤后，我發(fā)現(xiàn)最好的方法是使用旅行推銷員算法對顏色進(jìn)行排序。你可以在這里看到我們可以將顏色分成六個干凈的組。

旅行推銷員

?

旅行商問題是一個著名的計算機(jī)科學(xué)問題。它要解決的問題是銷售員必須以最有效的順序訪問多個城市（根據(jù)總行進(jìn)距離）。

?

?

有很多庫和算法可以解決旅行商問題，我使用了tsp_solver python 庫。我們在 3D 中繪制 150 個 RGB 值，并使用旅行推銷員算法找到理想的訪問順序。旅行推銷員找到的順序提供了對顏色進(jìn)行排序的順序。在視覺上它看起來像這樣：在這里，您可以看到按旅行推銷員排序的所有邊緣部分（5x5x5 有兩組/邊緣軌道）。我們可以很容易地將它們分成六組，并為每組分配一個顏色名稱。

?

我們還通過 Traveling Salesman 對中心塊和角塊進(jìn)行排序，并為每個方塊分配六種顏色中的一種。您會注意到下圖中顏色不再變化，所有白色方塊完全相同，所有藍(lán)色方塊完全相同，等等。

?

到達(dá)這里需要做很多工作，但此時 CraneCuber 知道立方體的確切狀態(tài)。這使我們能夠計算出如何解決立方體的解決方案。

該軟件是開源的，可在 github 上獲取，網(wǎng)址為https://github.com/dwalton76/rubiks-color-resolver

軟件 - 計算解決方案

基于軟件的魔方解算器是一個很大的話題，學(xué)生們已經(jīng)完成了算法的博士學(xué)位，可以單獨(dú)解決 3x3x3。我將描述我最終是如何編寫我的求解器的，以及它是如何在較高層次上工作的，但要深入細(xì)節(jié)將超出本文檔的范圍（并且本文檔已經(jīng)很長了）。

為什么？

當(dāng)我開始使用 CraneCuber 時，我并沒有打算編寫自己的魔方求解器。有許多用于 2x2x2 和 3x3x3 立方體的開源解算器，但沒有那么多的人為 4x4x4 和更大的立方體編寫解算器。我能夠找到一個 4x4x4 的開源求解器，但那是井枯竭的地方。沒有任何用于 5x5x5、6x6x6 等的開源求解器 :( 我決定編寫自己的求解器，并牢記幾個目標(biāo)：

• 它將是開源的
• 它將是一個 NxNxN 求解器，這意味著它可以求解任何大小的立方體
• 它將能夠在最小的硬件上運(yùn)行，例如 Raspberry Pi

它花了大約 5 個月的時間來解決 4x4x4 和 5x5x5 問題，又花了 5 個月的時間來實(shí)現(xiàn) NxNxN！在過去的一年里，我繼續(xù)致力于解決方案，我已經(jīng)能夠減少計算解決方案所需的時間以及它找到的解決方案的長度。

我有信心說它是世界上唯一的開源 NxNxN 求解器，我為此感到非常自豪 :) 該求解器可在 github 上找到，網(wǎng)址為https://github.com/dwalton76/rubiks-cube-NxNxN-solver

如何？

基于軟件的魔方求解器的核心是一種稱為迭代深化 A*的算法。您經(jīng)常會看到它縮寫為 IDA*（發(fā)音為 IDA-star）。

魔方解算器必須解決的問題是找到將魔方從打亂狀態(tài)帶到??已解決狀態(tài)的一系列移動。我們可以編寫一個求解器，通過越來越長的移動序列進(jìn)行蠻力廣度優(yōu)先搜索，直到找到解決方案，但我們會在它完成之前很久就老死了。我們需要一種更智能、更快速的方法來找到解決方案！

IDA* 是一種算法，允許求解器在搜索解決方案時消除大量移動序列。它不能很好地求解 5x5x5 立方體，但它確實(shí)可以很好地求解立方體的某些子集，例如求解中心。一旦解決了中心問題，我們就可以再次使用 IDA* 來解決邊緣問題。這些被稱為“階段”。我們可以將求解立方體的問題分解為多個階段，然后使用 IDA* 求解每個階段。立方體越大，求解立方體所需的階段就越多。大多數(shù) 3x3x3 求解器使用兩個階段，而我的求解器使用七個階段來求解 5x5x5。

這是對基于軟件的魔方解算器如何工作的非常簡短的介紹。我寫了一篇關(guān)于這個主題的冗長博客文章，如果您對立方體求解器的工作原理感興趣，可以訪問http://programmablebrick.blogspot.com/2017/07/rubiks-cube-solver.html 。

結(jié)論

我希望你喜歡我的項目。我真的很喜歡它的工作 :) 對于這么長的關(guān)于它如何工作的文章，我深表歉意。項目的軟件方面涉及太多，我覺得我應(yīng)該給出一個深入的解釋。