python - 如何为二元拼图生成已解决的网格

Question

我正在使用 Python 和 Pygame 开发我的第一款游戏，我必须创建一个二进制拼图。

我在生成具有以下条件的已解决网格时遇到了问题：

1. 每个框应该包含一个零或一个。

2. 不允许在每个紧邻或下方的两个以上相等的数字。

3. 每一行和每一列都应该包含相同数量的零和一。

4. 每一行都是唯一的，每一列都是唯一的。因此，任何行不能完全等于另一行，任何列不能完全等于另一列。

我试过类似的东西

parents = []

unique_found = False
while not unique_found:
        candidate_array = np.random.choice([0, 1], size=(CELL,CELL))         
        if not any((candidate_array == x).all() for x in parents): 
          [(i, j) for i, j in enumerate(candidate_array)]
          unique_found = True
         
parents.append(candidate_array)   

它正在生成一个由 1 和 0 组成的随机网格：

[[0 0 0 1 0 1]
 [1 0 0 1 1 1]
 [0 0 0 0 1 0]
 [1 0 0 0 1 0]
 [0 1 1 1 1 1]
 [0 1 1 0 1 1]]

但我不知道如何添加我想让这个网格不那么随机的条件。

标签： pythonmatrixbinary

Answer 1

对于直接解决方案，基本上没有办法绕过对这些约束进行编码。完成编码后，尝试回溯：尝试在第一个单元格中输入 0 并检查约束。如果满足约束条件，则递归地进入下一个单元格并在那里尝试 0。

如果违反了约束并且您已经尝试了正方形上的所有可能值，那么沿途某处的假设之一肯定是无效的，因此撤消最近放置的 0 或 1，弹出调用堆栈并回溯到上一个索引来尝试下一个可能的值。这种回溯可能会解除所有的动作，但如果一个棋盘是可解的，它最终会找到一个解决方案。它停止探索不可能的位置的优化是蛮力的。

这与解决数独的最直接方法基本相同，但具有不同的约束条件和每平方不同的值（少得多，但更多的平方）。从头开始生成已解决的板与使用一些预填充值解决板之间的唯一区别是您跳过具有预填充值的方块。这是一个微不足道的区别。查看这个gif，它说明了回溯算法的工作原理。

研究数独求解可以为特定领域的改进提供更深入的想法，一旦你有一个基本的回溯方法工作，你就可以将其应用于这个难题以提高速度。即使没有任何特定领域的知识，回溯方法也可以是多线程/多处理的，以提高速度，每个工作人员从搜索根部第一个方块的前几个顶级值的特定配置开始。

顺便说一句，在空板上遵循此方法是确定性的，因此您每次都会得到相同的填充板。如果你想要一个非确定性的结果，你可以随机化沿途的选择，甚至是访问方块的顺序。

您可以通过置换满足约束 3（每行/列的 0 和 1 的数量相等）的预填充网格来改进回溯方法，但它仍然基本上是回溯（堆栈帧的粒度发生变化 - 现在它是一种可能的配置一行而不是一个单元格），并且纯粹是一种优化，所以我将从逐个单元格的方法开始。

也就是说，我会避免盲目地生成和测试随机配置。编写代码并不比回溯更容易，因为您仍然需要编写代码并检查所有约束，并且非系统方法可能比系统方法需要更长的时间才能找到解决方案。

如果您愿意使用外部工具，您可以将约束添加到现成的约束求解器（如PuLP或Z3 ）中，它会吐出答案。