哪種解決這種遊戲最好的方法是？

Question

今天晚上我試圖解決一個木拼圖，所以我想知道哪種方法是找到解決這種類型的問題programmaticaly的最佳途徑。

其目的是將一組固體（如三維中的俄羅斯方塊）組合在一起形成一個可行的形狀，考慮到這樣一個事實，只有當它們合適時纔可以將部件連接或滑入結構這種運動（忽略旋轉，只有90°轉彎）。

查看this圖片瞭解我的意思。

Answer 1

在我最新的CS類中，我們製作了一個通用的拼圖求解器，它通過將狀態表示爲C++中的對象來工作。每個對象都有一個方法來比較它表示的狀態與另一個狀態。這是用於memoization，以確定是否已經看到國家。每個狀態還有一種方法來生成可以從該狀態直接到達的狀態（即旋轉塊，放置塊，移動塊）。解算器通過維護一系列狀態來工作，從隊列的前面彈出一個狀態，檢查它是否是所需的狀態（即解決難題）。如果沒有，則檢查記憶（我們使用哈希集合）以查看狀態是否已經被看到。如果不是，則從當前狀態可達的狀態被生成並附加到隊列的後部。一個空隊列表示一個無法解決的難題。

概念化類似3D的東西很難，但這是計算機化拼圖解決方案的基本方法。

Answer 2

由於這是一個或多或少的小問題，因爲對於一臺計算機有少量的組合可能我會嘗試一個簡單的搜索算法。 我的意思是一個algorithm，它檢查每個可能的配置，並從這個配置的結果繼續，直到它結束在一個結束配置，在你的情況下多維數據集。

問題接踵而來就是要編寫一個能夠執行從一個狀態到另一個狀態的所有狀態檢查和轉換的程序。因爲您必須查看配置在物理上是否可行。

Answer 3

似乎是一個三維polyomino包裝問題的更容易的子集。關於這個問題有各種各樣的scholarly papers。

Answer 4

如果您想處理的難題是您已鏈接的照片中的問題，那麼只需在可能的解決方案樹中進行搜索，直到您找到自己的方式就可行了。

如果每個拼圖是連接在它們臉上的多個立方體，並且我將通過將每個拼塊裝入一個更大的立方體中來解決拼圖，每個邊緣上有4次作爲拼合立方體，然後我繼續如下。

聲明每個作品的任意立方體作爲其原點。觀察每個拼圖塊有24個可能的旋轉，原點立方體每個可能的面朝上的一個方向，圍繞該位置的垂直軸旋轉4次。

嘗試通過查找產生相同最後一塊的可能方位來甄別搜索空間，如果給定的旋轉，然後將原始立方體轉換爲該塊的其他立方體的任何一個導致完全相同的佔用作爲以前考慮的輪換量，從未來的考慮中剔除輪換量。

從包里拉出一塊。如果包內沒有碎片，那麼這是一個解決方案。循環通過溶液體積的每個單元格，並且每個單元格的被拉動的片段的每次旋轉。如果作品完全處於搜索範圍內，並且與其他作品沒有重疊，請進入本段。否則，請繼續下一個旋轉，或者如果沒有更多旋轉，請繼續到下一個單元，或者如果沒有更多單元，則返回沒有解決方案。

如果最後一段返回沒有解決方案，那麼這個難題是無法解決的。