Python中查找数独隐藏单数的有效方法

Question

我正在写一个类似人类策略的数独解算器。我编写了两种方法来查找方框上的隐藏单体，即检查是否只有一个单元格可供放置在方框中（“隐藏”表示即使单元格本身有更多的候选单元格）

我对列表使用以下结构：board[9][9]存储从1到9的放置编号，如果没有放置编号，则存储0。possibles[9][9][9]存储给定单元格的候选，如果该候选已被删除，则为0。因为我也在用Pygame编写GUI，所以我不希望从possibles中删除元素，因此，如果单元格只有数字5作为候选，那么可能的列表是possibles[i][j] = [0, 0, 0, 0, 5, 0, 0, 0, 0]

以下是隐藏的单一方法：

def hidden_singles(board, possibles):
    # CHECK BOX
    print("method 1")
    hiddenSinglesPos_box = []
    t0 = time.time()
    iterations = 0
    # iterate over each cell in the board
    for i, row in enumerate(board):
        for j, bnum in enumerate(row):
            # if the cell already has a placed number, skip
            if bnum != 0:
                continue

            # get box index
            ii = 3 * (i // 3)
            jj = 3 * (j // 3)

            # reduce the candidate list of cell to only non-zeros
            p = [_ for _ in possibles[i][j] if _ != 0]

            # for each candidate, check the box for a hidden single !?!?
            for k, pnum in enumerate(p):
                count = 0
                for ibox in range(ii, ii + 3):
                    for jbox in range(jj, jj + 3):
                        # skip again if the cell within the box has a placed number
                        if board[ibox][jbox] != 0:
                            continue
                        iterations += 1
                        if possibles[ibox][jbox][pnum - 1] != 0:
                            count += 1
                if count == 1:
                    hiddenSinglesPos_box.append([i, j, pnum])
    deltaT = time.time() - t0
    print(deltaT)
    print(f"Iterations: {iterations}")
    print(f"{len(hiddenSinglesPos_box)} hidden singles")
    print(hiddenSinglesPos_box)

值得一提的是，在调用此方法之前，我已经通过选中行、列和框排除了明显的非候选项

这是可行的，它可以通过大约1000次迭代找到隐藏的单曲，但肯定可以改进。我注意到，一旦找到第二个匹配项，我就可以从搜索框中删除一个候选项。例如，如果框中的第一个单元格有候选者[1,2,3]，第二个单元格有[1,2,4]，则无需为第二个单元格检查候选者1和2（但我不知道如何在不过度复杂的情况下进行检查）。我确实访问了每个董事会单元，因为我发现这样不仅可以跟踪盒子中隐藏的单个董事的存在，还可以跟踪其坐标

我是Python和编码的初学者，所以我接受关于这种方法或关于一般结构以及如何存储电路板、可能性等的建议

Answer 1

你有一个有趣的问题。要获得“更少”的迭代，请使用抽象集。这使得解释器调用编译的例程（大部分用c编写），而不是解析复杂的python逻辑

board = [
    [0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 7, 0, 0, 0, 0, 0, 0],
    [0, 0, 8, 6, 5, 4, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
]

fullSet = list(range(1, len(board)+1))
zero = set([0])

def findPossibles(board):
    result = [None] * len(board)
    for y in range(len(board)):
        result[y] = [None] * len(board[0])
        for x in range(len(board[0])):
            result[y][x] = fullSet.copy()

    for y, row in enumerate(result):
        for x, e in enumerate(row):
            if board[y][x] != 0:
                e = [0] * 9
            for i in range(len(board)):
                num = board[i][x]
                if num != 0: e[num-1] = 0
            for i in range(len(board[0])):
                num = board[y][i]
                if num != 0: e[num-1] = 0
    return result

def findSingles(board, possibles):
    result = []

    for y in range(3):
        for x in range(3):
            taken = set()
            # collect quadrant values
            for iy in range(y*3, y*3+3):
                for ix in range(x*3, x*3+3):
                    taken.add(board[iy][ix])

            # find hidden singles
            for iy in range(y*3, y*3+3):
                for ix in range(x*3, x*3+3):
                    res = set(possibles[iy][ix]) - taken - zero
                    if len(res) == 1:
                        result.append((ix, iy, list(res)[0]))
    return result

import time

t0 = time.time()
possibles = findPossibles(board)
singles = findSingles(board, possibles)
print(time.time() - t0)
print(singles) # [(1, 7, 9)]

处理隐藏单体的代码应该进行大约162次迭代

编辑

我提出了这个算法，使用字典收集象限内一个数字的所有可能位置。然后收集只有一个可能位置的。我还改进了findPossibles的外部复杂性，并用集合替换列表。我们可以在注释中进一步讨论代码

board = [
    [9, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 9, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 7, 9, 0, 0, 0, 0, 0],
    [0, 0, 8, 6, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 9, 0, 0]
]

fullSet = set(range(1, len(board)+1))

def findPossibles(board):
    sz = len(board)
    br = range(sz)
    result = [None] * sz
    for y in br:
        result[y] = [None] * sz
        for x in br:
            result[y][x] = fullSet.copy()

    for y, row in enumerate(board):
        taken = set(row)
        for x in br:
            result[y][x] -= taken

    for x in br:
        taken = set()
        for y in br:
            taken.add(board[y][x])
        for y in br:
            result[y][x] -= taken
    
    for y in range(3):
        for x in range(3):
            taken = set()
            rx = x * 3
            ry = y * 3
            
            for iy in range(ry, ry+3):
                for ix in range(rx, rx+3):
                    taken.add(board[iy][ix])

            for iy in range(ry, ry+3):
                for ix in range(rx, rx+3):
                    result[iy][ix] -= taken

    return result

def findSingles(possibles):
    result = []
    for y in range(3):
        for x in range(3):
            table = {i:[] for i in fullSet}
            rx = x * 3
            ry = y * 3

            for iy in range(ry, ry+3):
                for ix in range(rx, rx+3):
                    for p in possibles[iy][ix]:
                        table[p].append((ix, iy))

            for p in table:
                if len(table[p]) == 1:
                    result.append(table[p][0] + (p,))

    return result

import time

t0 = time.time()
possibles = findPossibles(board)
singles = findSingles(possibles)
print(time.time() - t0)
print(singles) # [(1, 7, 9)]

编辑2

为了改进方法findPossibles，我们应该为已经放置了数字的单元格中的候选对象分配一个空集

def findPossibles(board):
    sz = len(board)
    br = range(sz)
    result = [None] * sz
    for y in br:
        result[y] = [None] * sz
        for x in be:
            # check if this board cell is empty
            if board[y][x] == 0:
                result[y][x] = fullSet.copy()
            else:
                result[y][x] = set()