我正在用Python和Pygame制作我的第一款游戏，我必须创造一个二进制谜题。
我正面临一个问题，生成一个解决网格与这些条件:
-
每个方框应该包含一个0或1。
-
每个数字旁边或下面不允许有两个以上相等的数字。
-
每一行和每一列应该包含相等数量的0和1。
-
每一行唯一，每一列唯一。因此，任何行不能完全等于另一行，任何列不能完全等于另一列。
我试过像
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]]
但是我不知道如何添加我想让这个网格不那么随机的条件。
对于直接的解决方案，基本上没有办法绕过对这些约束进行编码。一旦你编写好代码，试着回溯:试着在第一个单元格中放一个0，并检查约束条件。如果满足约束条件，则递归到下一个单元格，并在那里尝试0。
如果违反了约束，并且您已经尝试了正方形上所有可能的值，那么在此过程中的某个假设一定是无效的，因此撤销最近放置的0或1，弹出调用堆栈并返回到前一个索引以尝试下一个可能的值。这种回溯可能会解开所有的动作，但如果棋盘是可解的，它最终会找到一个解决方案。这是一种优化的蛮力，它会停止探索不可能的位置。
这基本上与解决数独最直接的方法相同，但具有不同的约束和每个正方形的不同值(更少，但更多的正方形)。从头开始生成已解决的棋盘与使用几个预填充值解决一个棋盘之间的唯一区别是，您跳过了具有预填充值的方块。这是一个微不足道的区别。看看这个gif，它说明了回溯算法的工作原理。
研究数独解决方法可以为特定领域的改进提供更深入的想法，一旦你有了一个基本的回溯方法，你可以应用于这个谜题，以获得速度的提高。即使没有任何特定领域的知识，回溯方法也可以是多线程/多处理的，以提高速度，每个工作者从搜索根处的第一个正方形的前几个顶级值的特定配置开始。
顺便说一下，在空板上遵循此方法是确定的，因此每次您都会得到相同的填充板。如果你想要一个非确定性的结果，你可以随机化沿途的选择，甚至是访问方块的顺序。
您可以通过排列满足约束3(每行/列的0和1数量相等)的预填充网格来改进回溯方法，但它基本上仍然是回溯(堆栈帧的粒度改变-现在它是一行而不是一个单元的可能配置)，并且纯粹是一种优化，所以我将从逐单元的方法开始。
也就是说，我会避免盲目地生成和测试随机配置。编写代码并不比回溯容易得多，因为您仍然需要编写代码并检查所有约束，并且非系统方法可能比系统方法花费更长的时间来找到解决方案。
如果你愿意使用外部工具，你可以将约束添加到现成的约束求解器中，如PuLP或Z3，它会吐出答案。
您可以创建像下面这样的初始解，它只满足条件1和条件3。
[1 ,1, 1, 0, 0 ,0]
[1 ,1, 1, 0, 0 ,0]
[1 ,1, 1, 0, 0 ,0]
[0 ,0, 0, 1, 1 ,1]
[0 ,0, 0, 1, 1 ,1]
[0 ,0, 0, 1, 1 ,1]
然后随机交换行和列。因为这些都不会违反第三个条件。
这个想法就是交换行或列，直到你找到一个有效的解决方案。