將n×n板切成n個連接的n-minos的最快實現

Question

我試圖創建一個讓玩家用n個連接的n-minos拼湊n×n個網格的難題（定義：連接的n 1×1塊，例如每個俄羅斯方塊都是4分鐘）。然而，儘管看起來對於人類來說足夠簡單，但首先產生一種切斷電網的方法證明是一種挑戰。

例如板

對於人，產生這樣的解決方案是一個相對容易的任務通過遞歸以下以下邏輯/僞代碼：

：start_of_recursion：

• 從一個隨機的「最少連接」部分開始（結束，角落，連接到它的成員最少的邊緣部分）作爲起始迷你模塊

  ：start_of_recursion：

  • 使一個在隨機提供方向從隨機片在當前美濃
    • 如果「生長」在結果「分隔」剩餘板「成長」 （如果分隔的區域不是n的倍數），嘗試其他位置和方向
      • 如果所有位置和方向已被嘗試，則恢復到之前的電路板配置（應該不是真實的LY發生）
  • 如果尺寸爲N已達到，退出遞歸

  ：end_of_recursion：

• ，如果董事會已經充滿，退出遞歸

：end_of_recursion：

執行此例程似乎會生成解決方案生成的O（n^2）方法，但是條件檢查證明對於計算機來說確實非常昂貴。爲了確定板子是否連接，人類只需檢查剩餘區域內的任何「間隙」，並以幾乎O（1）的方式處理一個簡單的非重疊圖形，而我的代碼實現需要「從圖表上的一點傳播到鄰近地區，並在傳播完成後檢查是否有任何點位於到達範圍之外（最好是O（n））。由於每次在最內層迭代中執行該檢查，因此它將複雜性退化爲O（n ^（3+））問題，並且變得非常低效。

有沒有一種方法來檢查類似於人類認知的「差距」？或者這個問題可以從根本上想到並簡化爲一個更容易讓計算機解決的問題？

Answer 1

你的問題聽起來像是bin packing problem的變種。我會通過約束滿足方法來解決這個問題。下面我將使用Minizinc僞代碼。

電路板由單元組成，每個單元可以從幾個顏色變成一種顏色。我們可以如下表示：

int: rows; 
int: cols; 
int: colors_num; 

array [1...colors_num] of int: colors; 
array [1..rows,1..cols] of var colors: board; 

接下來，我們添加約束。例如，如果一個小區具有顏色A然後ATLEAST 1個相鄰小區必須有相同的顏色A：

constraint forall (c in colors) (
    if board[i, j] == c then 
    at_least (1, [board[i-1, j], board[i+1, j], board[i, j-1], board[i,j+1]], c) 
    else 
    true 
    endif 

可以描述所有的允許/禁止的形狀，約束或使用一些其他的智能方法引入可能削減。

約束滿意度應該是多比你的遞歸方法更有效率。然而，這並不是非常具有可擴展性 - 如果你想爲一塊巨大的棋盤（數百或數千個單元/顏色）生成一款遊戲，需要花費相當多的時間和記憶來生成迷你遊戲。