关掉订单的游戏

Question

这个问题是基于经典熄灯游戏的变体。

参见 SO 帖子：[https://stackoverflow.com/questions/19795973/lights-out-game-algorithm]

参见博文：[https://www.keithschwarz.com/interesting/code/?dir=lights-out]

然而，这种变体为您提供了一个 NxN 板，切换同一行和同一列（而不是相邻）中的所有灯，目标是打开所有灯（而不是关闭），并且灯只能如果当前处于关闭状态，则切换。

根据那篇文章和博客，我几乎可以立即通过高斯消元法找出游戏中哪些灯泡需要切换（特别是对于小 N），但问题是找到需要切换的灯的有效序列如果当前处于关闭约束状态，则仅切换一盏灯。简单地根据高斯消除的解决方案找到需要切换的所有灯光排列将是 O(M!)要改变的灯的数量。我想过做一些启发式的尝试切换灯，使得该行和列中的最多灯当前处于打开状态，因为它会因此在之后将最多灯留在关闭状态，但我让它运行了在 24x24 网格上一个小时，它无法找到有效的序列。

我知道我已经正确设置了高斯消除，因为如果我切换结果告诉我的每个灯泡并且我不注意灯需要关闭的约束，它会导致所有的网格灯泡亮着。

如果有任何帮助，我附上了我目前拥有的代码。 我试图解决的原始问题的链接是：[https://research.ibm.com/haifa/ponderthis/challenges/April2023.html]

import numpy as np

def switch(grid, row, col):
    grid[row, :] ^= True
    grid[:, col] ^= True
    grid[row, col] ^= True

grid_24x24 = '''
    000001000000000001110011
    110100010110101000010011
    011101110000001101001110
    000110111000110101101100
    101101011010010011101010
    111000100101110100101000
    110001011100000000000101
    100000010001100000000010
    000110010010110110101001
    011101101011111011100000
    011000101010111011111100
    100011110010000100100111
    000111010010100010001110
    011001010001001111110101
    110001000010111000100000
    000000101100101000101001
    111001010010010011110110
    100000110001111111011010
    110100000011100100110010
    101000110111001110010000
    110000000010011100100101
    111111011011111100010101
    000000000110101011100000
    110001111100000011001111
    '''

rows = grid_24x24.strip().split('\n')
grid_24x24_bool = np.array([list(map(int, row.strip())) for row in rows], dtype=bool)
grid_24x24_int = np.array([list(map(int, row.strip())) for row in rows], dtype=int)


def lights_out(grid):
    n = len(grid)
    A = np.zeros((n**2, n**2), dtype=int)  
    b = np.ones(n**2, dtype=int)         

    for i in range(n):
        for j in range(n):
            k = i * n + j
            A[k, k] = 1 
            for l in range(n):
                A[k, i*n+l] = 1
                A[k, l*n+j] = 1

    b *= np.array(grid).flatten()

    for j in range(n**2):
        i = j
        while i < n**2 and A[i, j] == 0:
            i += 1
        if i == n**2:
            continue  

        A[[i, j], :] = A[[j, i], :]
        b[[i, j]] = b[[j, i]]

        for i in range(j+1, n**2):
            if A[i, j] == 1:
                A[i, :] = (A[i, :] + A[j, :]) % 2
                b[i] = (b[i] + b[j]) % 2

    x = np.zeros(n**2, dtype=int)
    for j in range(n**2-1, -1, -1):
        if A[j, j] == 1:
            x[j] = b[j]
            for i in range(j):
                b[i] = (b[i] + A[i, j] * x[j]) % 2

    solution = np.logical_not(x.reshape((n, n))).astype(int).tolist()
    return solution

solution = lights_out(grid_24x24_int)


def heuristic(grid, bulbs):
    rowSums = np.sum(grid, axis=1)
    colSums = np.sum(grid, axis=0)
    sums = rowSums + colSums
    return sorted(bulbs, key=lambda x: sums[x[0]] + sums[x[1]] - (100 if grid[x[0]][x[1]] else 0), reverse=True)

def solve(grid, bulbs, path):
    if len(bulbs)==0:
        print(path)
        return True
    bulbs = heuristic(grid, bulbs)
    for idx,(i,j) in enumerate(bulbs):
        if grid[i][j]:
            break
        switch(grid,i,j)
        bulbs.pop(idx)
        path.append((i,j))
        if solve(grid,bulbs,path):
            return True
        switch(grid,i,j)
        bulbs.append((i,j))
        path.pop()
    return False

bulbs = [(i,j) for (i,j),e in np.ndenumerate(solution) if e]
solve(grid_24x24_bool, bulbs, [])