計算所有可能的行組合滿足其行約束在一個非圖中

Question

所以基本上我問的是完全一樣的，這個人問一年前：Calculation of all possible mutations of a nonogram被關閉不明，但我不明白爲什麼這將是。

回顧確切的問題。在nonograms行和列可填寫不同的方式，必須滿足收縮。作爲一個例子，如果一行具有約束[2,3,2]和長度10，則意味着必須填充2個新單元格，然後是空白，然後是3個前景，空白，最後是2個前景。

所有可能的組合將被：

[2,3,2]：XX XXX _ _ _ XX
[2,3,2]：XX XXX _ _ _ XX
[2 1,3,2]：XX _ _ _ XXX XX
[2,3,2]：_ _ XX XXX XX _

我想到它會很容易創建計算所有可能的組合爲一般功能任何行長和約束，但我整個週末都在嘗試這個，這讓我瘋狂！很感謝任何形式的幫助。

Answer 1

我建議你認爲這是一個組合的問題：

鑑於約束[2,3,2]，你基本上要具備以下條件：
xx，_，xxx，_，xx。
剩下的問題是你在哪裏放置你的空間。由於你有3組x s，你有4個地方可以放置它們。你的例子顯示在第三組之後放置唯一可用空間，第二組在第一組之後，在第一組之前。

總而言之，計算出您有多少空閒空間（n = total length - number of x s - (number of sets - 1)）。現在使用組合101來計算將k相同空格放入n可能位置的所有組合。一旦你有了名單 - 你很好走。