如何開始編碼大腦的8益智遊戲，以計算最少的動作

Question

我設法解決這個問題與RNG蠻力大約需要4-5秒找到最佳的解決方案，即使工作網格是一個3×3。

我想知道我如何才能生成蠻力在沒有暴力的情況下發現的相同動作。

我會列出2個例子，並找到解決方案蠻力。我試圖分析解決方案，找出它爲什麼選擇他們，我什麼都不知道。

此遊戲的工作原理是利用在兩個方向（從右到左）

左到右循環旋轉做到這一點
If [a, b, c] then [b, c, a]
從右到左循環旋轉做到這一點
循環旋轉（左到右）和If [a, b, c] then [c, a, b]

遊戲數據可以說是這樣的（它可以是1至9中的任一置換）
例如
Data = 7, 2, 6, 1, 5, 4, 3, 8, 9

我可以通過8種不同的方式移動桌子上的棋子。
1）基於行的循環旋轉（從左到右）。
2）基於行循環旋轉（從右到左）。
3）基於列的頂部到底部。
4）根據列自下而上。
現在5到8不需要列或行，因爲它們是對角設置的。
5）從左上到右下（從左到右）。
6）從左上到右下（從右到左）。
7）右上角到左下角（從左到右）。
8）右上角到左下角（右到左）。

的數據被加載爲以下

• 007 | 002 | 006
• 001 | 005 | 004
• 003 | 008 | 009

解蠻力被迫：
1）。 [右上]到[左下]（右到左）
2）。從下到上，列：0
3）。從左到右，行：1

下面是解simlutated

1）。[右上]到[左下]（右到左）

• 007 | 002 |
• 001 | | 004
• | 008 | 009

2）。底部到頂部，列：0

• | 002 | 003
• | 006 | 004
• | 008 | 009

3）。從左到右排：1

• 001 | 002 | 003
• | |
• 007 | 008 | 009

下面是實施例2這需要6點移動到解決

• 009 | 008 | 007
• 006 | 005 | 004
• 003 | 002 | 001

解決方法：（6步）
1）。 [右上]到[左下]（右到左）
2）。從上到下，列：1
3）。從下到上，列：0
4）。 [左上]到[右下]（從左到右）
5）。從左到右，行：1
6）。從右到左，行：2

所以這是一個非常簡單的謎題，但找到高效的解決方案並不是一項簡單的任務。 有人可以指引我在正確的方向。

Answer 1

如果你想嘗試一些比BFS更好的東西（也許你想要畢業到14個難題或什麼東西），試試看啓發式搜索方法，如A *（發音爲A-星）。這些算法使用某種規則作爲評估哪些路徑可能成功的代理。在A *的情況下，最壞的情況是它會減少到廣度優先搜索。

具有挑戰性的部分是想出一個很好的啓發式使用。對於A *，您需要一種永不過高估計路徑的啓發式方法，只會低估。因此，通常可以通過想象最佳情況或放鬆對問題的限制來提出良好的啓發式方法。例如，如果你試圖找到從一個點到另一個點的最短路徑，點之間的直線距離是一個很好的啓發。在8拼圖的情況下，你需要某種度量標準，隨着你越來越接近解決這個難題而逐漸改善。

Answer 2

而不是使用您的隨機數發生器解決方案，更有條不紊。

A breadth first search（BFS）易於實施，並且可以保證您找到最佳解決方案。 BFS只是測試當前狀態的所有後續狀態，然後遞歸地測試所有這些狀態的所有後續狀態，直到找到解決方案。更直接地，BFS測試解決方案長度爲1的所有移動，然後測試解決方案長度爲2的所有移動等，直到找到解決方案。

天真的實現有多次測試相同位置的下降，但是您可以通過在搜索中存儲所有以前的狀態及其深度並跳過存儲值低於當前值的任何重複深度。 BFS有很多改進，但對於這個遊戲的簡單性（只有9個狀態），用更復雜的算法看不出有多少改進。