電子發燒友網>電子資料下載>電子資料>基于軟件的魔方解算器

基于軟件的魔方解算器

2513695 2023-07-06 | zip | 0.17 MB | 次下載 | 免費

普通下載普通下載

資料介紹

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

第 1 步 - 初始照片

第二步是創建圖像的灰度副本并應用抗噪濾鏡

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

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

第 3 步 - Canny 邊緣檢測

第四步是擴大邊緣。我們想讓它們更厚，因為這樣更容易找到立方體的正方形。

第 4 步 - 擴大邊緣

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

第 5 步 - 尋找輪廓

第六步去除非方形輪廓

第 6 步 - 刪除非正方形

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

第 7 步 - 去除巨大的輪廓

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

第 8 步 - 去除矮化輪廓

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

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

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

軟件 - 立方體狀態的 RGB 值

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

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

原始 RGB 值

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

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

RGB排序

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

HSV排序

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

旅行推銷員

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

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

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

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

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

軟件 - 計算解決方案

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

為什么？

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

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

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

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

如何？

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

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

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

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