游戏求解算法（Buttonia，熄灯变体）
我正在尝试为游戏算法创建可解函数。 基本上是一个针对给定游戏返回 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
此处讨论的解决方案：使用自定义运算符进行高斯消除
越来越近。 几乎准备好发布完整的解决方案：反转二进制网络
I am trying to create a solvability function for a game algorithm. Basically a function that returns true or false for a given game it if is solvable or not.
The game is Buttonia.com (which does not implement the algorithm as yet), a type of lights-out game. Basically You have a grid of buttons, each of which, when pressed, will change the state of some of it's neighbors. Currently I generate a random game configuration and then apply heuristics as far as possible. The rest is decided by brute force search.
My progress so far was to create a system of equations to model the game. As each button needs to change state an odd number of times to end up in a down state, It's equation would be this:
button_A = 1 - (button_1 + button_2 + ... + button_X) % 2
Where button_1 through button_X are the states of the buttons with an effect on button_A. Some buttons may be immediately resolved, if they are not dependent on others. For the rest, I try one configuration until I get a conflict and then back track.
Currently this algorithm is practical for smaller configurations of games. I've tested it from 3x3 games up to sizes of 10x10. Where 6x6 is near an upper limit for practical play.
The equations hugely cut down the search space from brute-force, making it practical. There might be a purely mathematical way of solving the system of equations.
Sample 3x3 game in ascii (from 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
Solution, press these: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)
Equations for this game:
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
Potential solution:
Changing the mathematical functions to avoid the need for the modulus lets us move the terms on the left side to the right, creating the neat matrix setup we need for the Gaussian method. So the first two equations would respectively convert to:
-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
Discussed solution here: Gaussian Elimination with custom operators
Getting closer. Almost ready to post full solution: Inverting binary networks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
这看起来几乎像一个线性方程组（模 2 除外），因此您可能能够采用一种常规技术来解决这些问题 - 例如，以矩阵形式减少系统的行 （维基百科）。
This looks almost like a system of linear equations (except the mod 2), so you might be able to adapt one of the normal techniques for solving those - e.g. row reduction of the system in matrix form (wikipedia).
由于这不是一个有时间限制的问题（好吧，假设它可以在不到一天的时间内完成），我可能会进行深度有限的广度优先搜索，在一个级别上采取每个可能的移动，然后执行每个移动每一步都遵循。
虽然会很慢，但几乎肯定能找到答案（如果有的话）！
As this is not a time-limited problem (well, assuming it can be done in less than a day), I would probably go for a depth-limited breadth-first search, taking each possible move on a level and then each move that follows on from each move.
It will be slow, however it is almost guaranteed to find an answer, if there is one!
假设您建立了一个方程组并尽可能地求解它们，但有些行最终在方程的左侧全为 0（我将方程表示为增广矩阵）
假设您尝试求解 Z2 环中的系统（实际上，对于这个特定示例而言，这意味着唯一的变化是 1+1=0，其他一切保持不变...因此，我们唯一需要的运算符是 XOR）最终得到以下矩阵：
正如您在本例中看到的，第 4 行全为 0，这意味着我们还没有得到答案。 不过，可以这样想：一行全 0 意味着该变量不会影响解。 这实际上是一个糟糕的词语选择...它只是意味着它们可以具有任何值（我们很幸运，因为所有值都意味着 1 或 0，与实数不同...所以这意味着我们有 2该系统的解决方案）。
原因如下：此时您需要知道的是，最右边的列仍然包含适合您的游戏的有效解决方案。 我们以第一行为例。 它是这么说的，
但我们知道按钮 3 可以是任何东西（因为第 3 行全是 0）。 此时按钮 3 为 0（此时第 3 行最右边的列为 0），所以现在我们知道这意味着
我们知道 Button_0 为 1。因此在这个系统中即使我们无法直接找出Button_3，我们仍然有一个有效的解决方案。
上面生成的矩阵足以检查可解性。 如果一行全部包含 0，那么它本质上是在说明，
或者，为了更好地形象化其工作原理
（这是有道理的），系统仍然有效。 然而，如果我们遇到除了最右边的位之外全是 0 的行，即
这就是说
这是不可能的，因此我们现在知道系统无法解决，因为我们无法解决这样的不可能情况。
因此，简而言之，尝试尽可能地求解方程，如果您无法准确找出某些变量是什么，请不要担心，只要您在任何时候都没有遇到我刚刚提到的不可能的行提到那么游戏是可以解决的。
但是如果我们想要系统的最短解决方案怎么办？ 在这里我们必须检查所有可能的解决方案。 我们的button_3 可以是任何值，因此这意味着第3 列中的任何1 都意味着找到它的行受button_3 的影响。 因此，假设我们想检查使用 button_3 的解决方案是否会更短。 我们创建另一个矩阵，但现在将 button_3 设置为 1（因为我们之前已经确定它可以是任何内容，并且其中已经有 0，所以现在我们检查 1）。 我们现在最终得到以下矩阵：
我们尽可能地减少它，现在最终得到这个矩阵：
这仍然是一个有效的解决方案，但是我们可以看到该解决方案更长（需要按 3 次按钮，而不是按 2 次） ）因此我们丢弃它。 我们必须对我们找到的行设置为全 0 到 1 的每个排列执行此操作。因此，如果我们有 x 行全 0，则系统有 x^2 个解决方案，我们必须检查所有这些解决方案。
Suppose you built a system of equations and solved them as best you could, but some rows ended up with all 0's on the left hand side of the equation (I'm representing the equations as an augmented matrix)
Suppose you tried to solve the system in the Z2 ring (which in practical terms for this particular example means that the only change is that 1+1=0, else everything remains the same... ergo the only operator we need is XOR) and ended up with the following matrix:
As you can see in this example, the 4th row is all 0, meaning that we haven't got an answer for it. However think of it this way: a row of all 0 means that that variable does not affect the solution. That's actually a poor choice of words... it just means that they can have any value (and we're in luck here, since all values means 1 or 0, unlike in real numbers... So this means that we have 2 solutions for this system).
Here's why: what you need to know at this point is that the rightmost column still contains a valid solution for your game. Let's take the first line for example. It says that
but we know that button 3 can be anything (since line 3 is all 0s). At this point button 3 is 0 (the rightmost column on row 3 is 0 at this point) so now we know it means
so we know for a fact that button_0 is 1. Therefore in this system even though we couldn't directly find out button_3, we still have a valid solution.
The matrix generated above is enough to check for solvability. If a row contains all 0s then it is essentially saying that
or, to better visualize why this works,
which makes sense, the system is still valid. If however we encounter a row that is all 0s except the rightmost bit, i.e.
that would be saying
which is impossible therefore we now know that the system cannot be solved, since we cannot solve an impossible situation like this.
Therefore in a nutshell, try and solve the equation as best you can, don't worry if you cannot exactly find out what some of the variables are, as long as you don't encounter, at any point, the impossible row I just mentioned then the game is solvable.
But what if we want the shortest solution to the system? Here we'll have to examine all possible solutions. We have button_3 that can be any value, so that means that any 1 in column 3 means that the row in which it is found, is affected by button_3. So suppose we want to check if the solution using button_3 will be shorter. We create another matrix, but set button_3 to 1 now (since we established earlier that it could be anything, and we already had a 0 in there, so now we check for 1). We now end up with the following matrix:
We reduce that as much as we can and now end up with this matrix:
This is still a valid solution, however we can see that the solution is longer (requiring 3, instead of 2 button presses) therefore we discard it. We have to do this for every permutation of setting the rows we found as all 0s to 1. Therefore if we have x rows that were all 0s, then the system has x^2 solutions, and we have to check all of them.
这是 F2 上的线性方程组，该域包含两个元素 0 和 1。
您可以像普通线性方程一样求解它，但必须进行模 2 的算术。
编辑：
这种情况下的线性代数的工作原理与实数完全相同，只是您必须替换以下运算：
加法和减法变为异或，即 0 + 0 = 0、0 + 1 = 1、1 + 1 = 0。
乘法变为 AND：0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1
除法只能除以 1：0 / 1 = 0, 1 / 1 = 1 .
方程中的所有系数和未知数的可能值为 0 或 1。
因此模数不会被应用到除了您写的方程之外，它隐含在操作中。
如果你的方程组不可解，你会得到一个方程 0 = 1，这显然是不可解的。
This is a system of linear equations over F2, the field containing the two elements 0 and 1.
You can solve it just like normal linear equations, but you have to do the arithmetic modulo 2.
Edit:
Linear algebra for this case works exactly like for real numbers, except that you have to replace the operations:
Addition and subtraction become exclusive or, i.e. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.
Multiplication becomes AND: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1
Division is only possible by one: 0 / 1 = 0, 1 / 1 = 1.
All the coefficients in your equations and the possible values of unknowns are either 0 or 1.
So the modulo is not slapped on the outside of the equations like you wrote, it is implicit in the operations.
If your system of equations is not solvable you'll get an equation 0 = 1, which is obviously not solvable.
与其从随机状态开始，为什么不通过翻转随机开关来生成起始位置，即从已解决的状态向后工作到起始状态。 这样你就只会生成可解决的谜题。
Instead of starting with a random state, why not generate the starting position by flipping random switches, i.e. work backwards from a solved state to a starting state. That way you only generate solvable puzzles.