游戏解决算法(buttonia,lights out variant)

这是F上的线性方程组。 _二 ,包含两个元素0和1的字段。

你可以像解一般的线性方程一样解它,但是你必须做算术模2。

编辑: 在这种情况下,线性代数的工作原理与实数完全相同,只是必须替换运算:

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

• 乘法变为和:0*0=0,0*1=0,1*1=1

• 除法只能有一个:0/1=0,1/1=1。

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

所以这个模并不像你写的那样,贴在方程的外面,它隐含在运算中。

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

不要从随机状态开始,为什么不通过翻转随机开关来生成起始位置,即从求解状态向后工作到起始状态。这样你只会产生可解的谜题。

这看起来像是一个线性方程组(除了mod 2),因此您可能能够采用一种常规的方法来解决这些问题,例如矩阵形式的系统行约简。 (wikipedia) .

由于这不是一个时间限制的问题(好吧,假设可以在不到一天的时间内完成),我可能会先进行深度有限的广度搜索,在一个级别上进行每个可能的移动,然后在每个移动之后进行每个移动。

它会很慢,但是如果有答案的话,几乎可以保证找到答案!

假设您构建了一个方程组,并尽可能地解决了它们,但有些行最后在方程的左侧出现了所有的0(我将这些方程表示为一个增广矩阵)。 假设您试图解决z2环中的系统(在这个特定示例中,实际情况下这意味着唯一的变化是1+1=0,否则一切都保持不变……因此,我们唯一需要的运算符是xor),最后得到以下矩阵:

1001 1
0100 1
0011 0
0000 0

正如您在这个例子中看到的,第4行全部是0,这意味着我们还没有得到它的答案。但是这样想:一行全部为0表示该变量不会影响解决方案。事实上,这是一个糟糕的词汇选择…它只是意味着它们可以有任何值(我们在这里很幸运,因为所有值都意味着1或0,与实数不同…所以这意味着我们有两个解决方案。

原因如下:此时您需要知道的是,最右边的列仍然包含适合您的游戏的有效解决方案。以第一行为例。它说

button_0 + button_3 = 1

但是我们知道按钮3可以是任何东西(因为第3行都是0)。此时,按钮3为0(此时第3行最右边的列为0),因此我们现在知道它的意思

button_0 + 0 = 1

所以我们知道,按钮0是1。因此,在这个系统中,即使我们不能直接找到按钮_3,我们仍然有一个有效的解决方案。

上面生成的矩阵足以检查可解性。如果一行包含所有0,那么它本质上就是说

nothing = nothing

或者,为了更好地形象化这项工作的原因,

0x = 0

这是合理的,系统仍然有效。如果我们遇到一行0 除了 最右边的位,即

0000 1

那就是说

0x = 1

这是不可能的,因此我们现在知道这个系统是无法解决的,因为我们无法解决这样一个不可能的情况。

因此简而言之,尽可能地解出这个方程,不要担心如果你不能准确地找出其中的一些变量是什么,只要你在任何时候都没有遇到我刚才提到的不可能的行,那么这个游戏是可以解决的。

但是如果我们想要 最短的 系统解决方案?在这里,我们将检查所有可能的解决方案。我们有可以是任何值的button_3,这意味着第3列中的任何1都意味着找到它的行受button_3的影响。所以假设我们想检查使用按钮3的解决方案是否会更短。我们创建了另一个矩阵,但是现在将button_3设置为1(因为我们之前已经确定它可以是任何东西,并且我们已经在其中有了0,所以现在我们检查1)。现在我们得到以下矩阵:

1001 1
0100 1
0011 0
0001 1

我们尽可能地减少这个值,最后得到这个矩阵:

1000 0
0100 1
0010 1
0001 1

这仍然是一个有效的解决方案,但是我们可以看到解决方案更长(需要3次,而不是2次按键),因此我们放弃了它。我们必须对每一个排列都这样做,将找到的行设置为0到1。因此,如果我们有x行都是0,那么系统就有x^2解决方案,我们必须检查所有这些解决方案。