Skip to main content
 首页 » 编程设计

python之我如何进一步优化这个 "Lights Out"变体的求解器

2025年05月04日15hnrainll

我还在解决this problem ，取自当前的“Google Foobar”挑战。这是“熄灯”游戏的一种变体，在该游戏中，按下一盏灯会翻转同一行和同一列上每个灯的状态。

我之前尝试过 using a BFS ，这对 n > 6 来说太慢了，而我需要处理 2 < n < 16。我目前有一个程序可以处理除 13 和 15 之外的所有偶数 n 和所有奇数。这是它的作用:

  1. 我使用 strategy由 @Aryabhata 概述以找到某个系统 Ax = b 的特殊解决方案 x'，它可以与此问题的实例相关联(有关详细信息，请参阅 here)。

  2. 找到一个 base在 A 的零空间中，我计算 x' 的所有和加上基向量的线性组合。

  3. 这些和的集合是原始问题的所有解的集合，因此我可以通过蛮力找到达到最小值的解。

  4. 需要注意的是，对于 n 偶数，零空间是空的(A 是可逆的)，因此 x' 达到最小值，因为它是唯一的解决方案。如果 n 为奇数，则零空间的基中的向量数为 2n - 2，因此搜索空间的大小为 2^(2n - 2)，在最坏情况下为 2^28 (n = 15)。

这是我的程序:

from itertools import product 
 
 
MEMO = {} 
 
 
def bits(iterable): 
    bit = 1 
    res = 0 
    for elem in iterable: 
        if elem: 
            res |= bit 
        bit <<= 1 
    return res 
 
 
def mask(current, n): 
    if (current, n) in MEMO: 
        return MEMO[(current, n)] 
 
    result = 0 
    if current < n: 
        for j in xrange(n): 
            result += (2 ** ((current - 1)*n + j) + 2 ** (current*n + j)) 
    else: 
        for i in xrange(n): 
            result += (2 ** (i*n + current - n) + 2 ** (i*n + current - n + 1)) 
 
    MEMO[(current, n)] = result 
 
    return result 
 
 
# See: https://math.stackexchange.com/a/441697/4471 
def check(matrix, n): 
    parities = [sum(row) % 2 for row in matrix] 
    for i in xrange(n): 
        parities.append(sum([row[i] for row in matrix]) % 2) 
 
    return len(set(parities)) == 1 
 
 
def minimize(matrix, current, n): 
    if current == 0: 
        # See: https://stackoverflow.com/a/9831671/374865 
        return bin(matrix).count("1") 
    else: 
        return min(minimize(matrix ^ mask(current, n), current - 1, n), 
                   minimize(matrix, current - 1, n)) 
 
 
def solve(matrix, n): 
    result = [0 for i in xrange(n) for j in xrange(n)] 
 
    for i, j in product(xrange(n), repeat=2): 
        if matrix[i][j]: 
            for k in xrange(n): 
                result[i*n + k] ^= 1 
                result[k*n + j] ^= 1 
            result[i*n + j] ^= 1 
 
    if n % 2 == 0: 
        return sum(result) 
    else: 
        return minimize(bits(result), 2*n - 2, n) 
 
 
def answer(matrix): 
    n = len(matrix) 
 
    if n % 2 == 0: 
        return solve(matrix, n) 
    else: 
        if check(matrix, n): 
            return solve(matrix, n) 
        else: 
            return -1

我已经尝试过对其进行优化:例如，函数 bits 将矩阵编码为二进制数，而函数 mask 创建二进制掩码，用于将基的单个元素添加到 x'。那些掩码也被记住，因为它们经常使用，所以它们只计算一次。

然后使用成语 bin(n).count('1') 计算 1 的数量，即 should be最快的实现(我将其与 Kernighan 的经典实现进行了对比)。

那么，我还能做些什么来从我的程序中榨取更多的性能呢？以下是一些测试用例:

print answer([ 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 
]), 1 
 
print answer([ 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1], 
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] 
]), 14 
 
print answer([ 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 
]), 15 
 
print answer([ 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 
]), 14 
 
print answer([ 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
]), 15

编辑: 我通过了这一轮。此实现正确解决了 5 个测试用例中的 4 个，然后我暴力破解了第五个。我仍然对进一步的优化或不同的算法感兴趣!

编辑 2: This answer ，特别是 this paper证明这个特定问题是 NP-hard(第 3 节)，这暗示我们不应该寻找多项式算法。所以问题变成了:“我们可以获得的最佳指数是多少？”。

请您参考如下方法:

我尝试了关于线性代数的一切，因为它是 GF2，我认为我找不到多项式解。由于最大数量为 15，我将其进一步优化为大约 2^15。

对于偶数

因此，对于 n 是偶数，有一种比标准线性代数更快的方法。例如，如果你有这样的东西， 0000 0100 0000 0000 一个解决方案应该是(恰好翻转该点的行和列n次) 0100 1111 0100 0100 如果你想一想，如果你有一个点要翻转，你可以翻转行和列的每个点一次。 (如果这有意义的话)，那么很容易找到一个特定的解决方案。

如果我有这样的东西 0100 0010 0010 0000 一种解决方案可能是 1131 1221 1221 0120 由于翻转两次没有区别，解决方案可以简化为 1111 1001 1001 0100

然后是奇数

如果 n 是奇数，我只能想到搜索。然而，我们可以扩展 n -> n+1 使得问题的解决方案不应该包含最后一行和最后一列的翻转点。

如果您有 3x3 的东西，例如: 010 001 001 您总是可以尝试将解决方案扩展为: 010x 001x 001x xxxx 首先，您将确定 3 乘 3 中的所有点， 1111 1001+？ 1001 0100 在哪里 ？应该解决 000x 000x 000x xxxx 可以看到，无论怎么翻转，都无法满足，除非xxx是相同的位。并且可以尝试所有底部组合进行翻转，然后通过判断翻转是否得到最小行数1来判断右手侧翻转。

我真的不擅长解释事情，希望它足够清楚。


  文章来源：
  https://blog.windname.com/post/adbeca2b1.html
阅读延展