A *算法和遊戲

Question

我正試圖在lisp中實施掃雷解決程序。我知道這不是罕見的問題，但我沒有找到任何可以幫助我的文章。在開始時，我有一個雷區作爲輸入數字在未被覆蓋的領域。算法應該在找到所有地雷後完成。因此，在每一步我都要檢查我可以放入我的礦區列表中的哪些字段，並從我的未開採字段列表中選擇一個字段並將其打開。稍後我會檢查是否已完成開採字段的列表，如果是，則算法已完成。我將不勝感激任何幫助。我不要求提供源代碼，但我需要好的想法。我沒有遇到過這類問題。

---

我必須使用A *算法。而且我不需要打開所有未打開的區域......我需要找到所有開採區域的位置。當然，它必須是最簡單的路徑。當我找到所有采礦場的位置算法完成。所以，再一次，我需要找到所有打開字段數量最多的開採字段。當然，我需要一個啓發式算法，這將有助於選擇所有安全未拆封區域之一。 並且在每次開放之後需要確定安全未打開域的列表。所以我需要調用main函數，該函數將檢查我是否找到所有挖掘的字段，如果沒有，那麼所有安全相鄰的未打開的字段都需要添加到路徑列表中。並且將選擇具有最佳啓發式的路徑

Answer 1

您不需要A *算法;其目的是在圖中找到最短路徑（例如地圖中兩個地方之間的最短路徑，或者解決難題的最小路徑）。您可能會想要使用一種稱爲回溯的技術。

只要有未打開的字段，選擇一個未打開的字段旁邊的一個打開的字段，並暫時將其標記爲一個地雷。然後，查看與前一個相鄰的未打開的字段以及打開的字段，並將該標記標記爲礦山，如果這不與相鄰的數字相抵觸 - 如果是，則將其標記爲安全的。繼續。最後，你會看到所有未開封的田地，包圍當前的區域，並找到了一種可能的方式來標記田地安全或不安全。然而，這是基於幾次猜測，所以現在你需要回到最後一個猜測的領域，然後做出相反的猜測，然後再次向前移動以獲得另一個可能的標誌組合。然後，更進一步，修改你的猜測，等等。這可以用遞歸非常整齊地實現。最終，你將會收集可能的旗幟組合。如果您可以在所有可能的標誌組合中找到安全的字段，請打開該字段。否則，請選擇儘可能多的標誌組合中安全的字段。

Answer 2

我在大學第一年實施了掃雷解決方案，所以我可以給你一些提示。 （這不是使用A *算法）

1. 重要 - 並非所有位置都是可解的。

2. 對於先進困難（複雜=需要一些時間，考慮所有可能將100個地雷放置在30x30場中），整個礦場的回溯有點複雜。

3. 您可以在本地解決所有問題，就像人類解決掃雷問題一樣。這個潛力是給用戶提示如何繼續而不是解決所有問題。

例子：

1. 有一個單獨的雷區地方，你的解決
2. 找到所有有一個解決的（數量/已知礦）細胞足夠接近未解細胞（2小區的距離）
3. 對於每個這樣的細胞，以中心細胞爲5x5的鄰域，找到每種可能性（回溯）並檢查可能性是否有共同之處（礦/非礦），如果是，您可以檢查地雷和揭露非地雷。
4. 重複，而你可以發現的東西。
5. 當你無法發現任何東西並且剩餘地雷的數量足夠小時，你可以嘗試在整個領域進行回溯。

我希望我記得正確，我做了一些證明，爲什麼5x5的面積足以檢查，但它已經快10年了。