时间戳

首页 > 解决方案 > 在 Python 中查找数独隐藏单曲的有效方法

python - 在 Python 中查找数独隐藏单曲的有效方法

问题描述

我正在编写一个具有类人策略的数独求解器。我写了一些方法来在一个盒子上找到隐藏的单曲，也就是说，检查是否只有一个单元格可供给定的候选人放置在盒子里（“隐藏”意味着即使单元格本身有更多的候选人） .

我对列表使用以下结构：board[9][9]存储从 1 到 9 的放置数字，如果没有放置数字，则存储 0。存储给定单元格的possibles[9][9][9]候选者，如果候选者已经被淘汰，则为 0。由于我也在使用 Pygame 编写 GUI，possibles因此我不喜欢从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)

值得一提的是，在调用这个方法之前，我已经通过勾选row、col和box，剔除了明显的非候选。

这很有效，它找到了大约 1000 次迭代的隐藏单曲，但它肯定可以改进。我注意到，一旦找到第二个匹配项，我就可以从框搜索中删除候选人。例如，如果框中的第一个单元格有候选 [1, 2, 3] 而第二个单元格有 [1, 2, 4]，则不需要检查第二个单元格的候选 1 和 2（我会不知道如何做到这一点而不会使一切过于复杂）。我确实访问了每个板单元，因为这是我发现的方式，不仅可以跟踪盒子中隐藏单的存在，还可以跟踪它的坐标。

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

标签： pythonlistsudoku

解决方案

你有一个有趣的问题。要获得“更少”的迭代，请使用集合之类的抽象。这使得解释器调用编译的例程（主要用 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()

推荐阅读