對腳本的建議，以解決彩色瓷磚匹配難題

Question

我有一個遊戲，我試圖設計一個腳本來找到解決方案。我使用Python，因爲這是我最熟悉的。

這裏的要點是，遊戲是由5個不同顏色的瓷磚組成的10×14板。機制是你可以選擇任何一組2個或更多相同顏色的水平或垂直軸上的對象（對角線不計數）。那個小組將會消失，上面的所有瓷磚都會掉下來取代他們的位置。如果某列完全沒有圖塊，則任何剩餘的圖塊右側的列將向左移動以填充間隙。您通過清除董事會並且不會遺留任何瓷磚而獲勝。

遊戲板的小例子，實際的一個是10×14

第一步 - 寫Python腳本尊重遊戲規則。相當簡單。

我的瓷磚顏色映射到數值，創建這樣一個矩陣：

test_game_board = [ 
    [2, 2, 2, 1, 1, 1, 5], 
    [2, 2, 2, 3, 3, 1, 5], 
    [3, 2, 4, 5, 3, 3, 5], 
    [3, 3, 4, 5, 5, 3, 5], 
    [1, 1, 1, 1, 1, 3, 5], 
    [1, 1, 5, 5, 1, 4, 4]] 

我分析矩陣，並找到相同顏色的所有連續的瓷磚和一切可能的舉措創建一個對象目前在董事會。

然後我有一段代碼給予某個符合條件的移動（請參閱稍後對拾取移動邏輯的評論），以更新遊戲板的副本並在需要的地方隨時隨地移動平鋪。

再次檢查棋盤以刷新符合條件的棋子列表，因爲棋子四處移動。

如果有符合條件的移動，則繼續選擇新移動。 如果找不到符合條件的舉動，我會檢查棋盤，看看是否輸了或贏得了比賽。 如果遊戲失敗，我重新開始並重置爲原始遊戲板佈局。

上面的表現似乎貫穿30-40步，並在大約0.0350秒內完成一次遊戲的單次嘗試。

第二步 - 採摘

我試過的動作序列的幾種方法：

• 隨機挑選一招每匝：運行腳本，幾小時後不是招」後，即使重複嘗試了數百萬次移動中的確切順序。

• 我試着衡量每次移動選擇多少個瓷磚並選擇較大的瓷磚所選擇的移動。

• 依次執行可能的操作。和隨機選項一樣，但是這樣我可以看到它正在取得某種進展。我已經嘗試在備用機器上運行幾天，它已經獲得了1500萬個序列，並且仍然沿着未知數量的全部可能移動距離不遠。

所以我想我的問題出在那裏，世界是，如果有人對我怎麼能設計一個算法，比我目前的暴力破解的方法解決這個以外的任何資源或想法。我可以在pastebin上發佈腳本，或者不想讓我的帖子膨脹超過它已經是：P

Answer 1

這是一個不是一個簡單的問題。）我認爲這個任務屬於NP-complete類，所以那裏解決這個問題並不容易。

你能做什麼？嘗試使用A* search。作爲一種啓發式方法，你可以嘗試選擇一些可以通過一個動作去除的元素（我不確定它是否正確/最優，你必須自己研究它）。

還有其他的方法，例如，constraint satisfaction，但我認爲這將是非常困難的解決你的難題。但是，請參閱Minizinc以獲取見解。我會以'以K步驟清空當前板卡'的形式生成任務？'。如果不是，請增加K並再次運行Minizinc。