algorithm - 计算满足非图行约束的所有可能的行组合

Question

基本上我要问的和这个人一年前问的完全一样:Calculation of all possible mutations of a nonogram由于不清楚而关闭，但我不明白为什么会这样。

重述确切的问题。在非图中，行和列可以用不同的方式填充，但必须满足限制条件。

例如，如果一行有约束 [2,3,2] 且长度为 10，则意味着必须填充 2 个相邻的单元格，然后是一个空白，然后是 3 个相邻的单元格，一个空白，最后是 2 个相邻的单元格。

所有可能的组合将是:

[2,3,2] : x x _ x x x _ x x _
[2,3,2] : x x _ x x x _ _ x x
[2,3,2] : x x _ _ x x x _ x x
[2,3,2] : _ x x _ x x x _ x x

我原以为创建一个通用函数来计算任何行长度和约束的所有可能组合会很容易，但我整个周末都在尝试这个，这让我发疯了!非常感谢任何帮助。

Answer 1

我建议您将此视为一个组合问题:

给定约束 [2,3,2]，您基本上必须具备以下条件:
xx, _, xxx, _, xx.
剩下的问题是你把剩下的空间放在哪里。因为您有 3 组 x，所以您有 4 个地方可以放置它们。您的示例显示将唯一可用空间放在第三组之后，第二组之后，第一组之后和第一组之前。

总而言之，计算出您有多少个可用空间(n = 总长度 - 数量x - (组数 - 1) )。现在使用组合数学 101 找出将 k 个相同空格放入 n 可能位置的所有组合。一旦你有了 list - 你就可以开始了。