检查一系列二进制状态

Question

我想解释这一点最简单的方法就是用提克托的比喻。 tictactoe的板可以表示为一个二进制状态的2D数组

因此，电路板#可以显示为[[1,2,3]，[1,2,3]，[1,2,3]] 这个数组的每个索引都有一个二进制值（X或O） 所以要检查一个极化者是否赢了，你要检查一个获胜模式中的所有3个方块是否共享相同的状态

现在，在这个类比中，您可以硬编码获胜的解决方案，并让董事会独立检查，但在我的情况下，我不希望硬编码他们，因为我需要（最终）在运行时生成数组和模式。因此，目前我可以手动检查或硬编码，但我需要找到一种方法来检查这些模式没有硬编码的解决方案

下面是我目前拥有的最小数组，举个例子：

[[[1,a], [2,a], [3,a]],
 [[3,a], [1,a], [2,a]],
 [[1,a], [2,a], [3,a]]]

现在“A”是空白状态，它将被替换为“B”或“C”（或任何两个名称）和1, 2和；3指定“线”

显示这一点的视觉方式可以看作：

看看“线”是怎么交叉的？ 这个数组中的模式是：

• 水平方向任意3个
• 一条“线”上的任意3个（不是笔直向上和 向下）
• 以及第1行第1行、r2l2、r3l3和；r1l3级， r2l2、r3l1

在更大的数组中有更多的模式，但这是我能做的最简单的

有没有人能帮我找出一个解决方案来找到生成的模式，这样我就可以检查它们的状态了？ 我正在用python测试这个问题，但是我也可以用纯数学的解决方案

Answer 1

一种方法是逐行扫描网格，并在每个位置跟踪所有可能方向上的图案长度。在这种情况下，方向将为左上->；右下、右上->；左下，左->；沿着“线”。处理每个位置时，如果状态与else匹配，则将前一个模式的值增加1，并将值设置为0。在找到目标长度或网格已完全迭代时停止

下面是上面的一个简短示例，其中单元格具有二进制状态：

grid = [
    [[1, 0], [2, 0], [3, 1]],
    [[3, 1], [1, 0], [2, 0]],
    [[1, 0], [2, 0], [3, 1]]
]

def find(g, length):
    # Top left -> bottom right, top right -> bottom left
    # and left -> right lengths are stored here
    prev = [[0] * 3 for _ in xrange(len(g[0]))]
    # 'Line' length is stored here for efficiency
    prev_line = {}
    for row in grid:
        cur = []
        cur_line = {}
        for i in xrange(len(row)):
            tl = line = tr = left = 0
            if row[i][1] == 1:
                # Up left
                tl = 1 + (prev[i-1][0] if i else 0)
                # Line
                line = 1 + prev_line.get(row[i][0], 0)
                # Up right
                tr = 1 + (prev[i+1][1] if i < len(row) - 1 else 0)
                # Straight Left
                left = 1 + (cur[i-1][2] if i else 0)

            if any(x == length for x in (tl, line, tr, left)):
                return True
            cur.append([tl, tr, left])
            cur_line[row[i][0]] = line

        prev = cur
        prev_line = cur_line

    return False

find(grid, 3) # True