游戏求解算法(Buttonia,Lights-out变体)

Question

我正在尝试为游戏算法创建一个可解决性函数.基本上是一个函数,如果可以解决,它会为给定的游戏返回true或false.

该游戏是Buttonia.com(尚未实现该算法),这是一种熄灯游戏.基本上你有一个按钮网格,按下时,每个按钮都会改变它的某些邻居的状态.目前我生成随机游戏配置,然后尽可能应用启发式.其余的是由强力搜索决定的.

到目前为止,我的进步是建立一个方程系统来模拟游戏.由于每个按钮需要改变状态奇数次才能以向下状态结束,因此它的等式是这样的:

button_A = 1 - (button_1 + button_2 + ... + button_X)%2

其中button_1到button_X是按钮状态,对button_A有效.如果某些按钮不依赖于其他按钮,则可以立即解决这些按钮.其余的,我尝试一个配置,直到我遇到冲突,然后回溯.

目前,该算法适用于较小的游戏配置.我已经从3x3游戏测试了它,尺寸为10x10.其中6x6接近实际游戏的上限.

这些方程式大大减少了蛮力的搜索空间,使其变得实用.可能存在解决方程组的纯粹数学方法.

---

ascii中的3x3游戏示例(来自buttonia.com/?game=2964):

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

解决方案,按下这些:(0,0),(2,0),(1,2),(0,1),(1,1),(2,1)

这个游戏的等式:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

潜在解决方案

改变数学函数以避免模数的需要让我们将左侧的项移动到右侧,创建了高斯方法所需的整齐矩阵设置.所以前两个方程将分别转换为:

-1 = -1*B00 +  0*B10 +  0*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22
-1 =  0*B00 + -1*B10 + -1*B20 +  0*B01 +  0*B11 +  0*B21 +  0*B02 +  0*B12 +  0*B22

这里讨论的解决方案:使用自定义运算符进行高斯消除

越来越近.几乎准备好发布完整的解决方案:反转二进制网络

Answer 1

_{这是 F 2}上的线性方程组，该场包含两个元素 0 和 1。

您可以像普通线性方程一样求解它，但必须进行模 2 的算术运算。

编辑： 这种情况下的线性代数的工作方式与实数完全相同，只是您必须替换操作：

• 加法和减法变为异或，即 0 + 0 = 0、0 + 1 = 1、1 + 1 = 0。

• 乘法变为 AND：0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• 只能除以一：0 / 1 = 0, 1 / 1 = 1。

方程中的所有系数和未知数的可能值为 0 或 1。

因此，模数并不像您写的那样放在方程的外部，它是隐含在运算中的。

如果你的方程组不可解，你会得到一个方程 0 = 1，这显然是不可解的。