为什么控制台卡在我在 python 中解决 9X9 数独板的最后一个函数上？

Question

我正在尝试编写一些代码来解决 python 中的一个简单的 9X9 数独游戏。卡在最后一个函数上：solve(board).

我的代码：

def check1D(A):
    miss = []
    for j in list(range(1,len(A)+1)):
        if j in A:
            continue
        else:
            miss.append(j)
    return(miss)

def check2D(B):
    return(check1D(B.flatten()))

def checkRow(board,x,y):
    return(check1D(board[x,:]))

def checkCol(board,x,y):
    return(check1D(board[:,y]))

def checkBox(board,x,y):
    ymin = (y//3)*3
    xmin = (x//3)*3
    return(check2D(board[xmin:xmin+3,ymin:ymin+3]))

上面的函数检查一维列表。 2D 展平阵列以应用 1D 检查。行、列使用一维检查来查找候选者。 Box 计算出 min/max 需要正确的 3X3 使用 2D 函数检查缺失数字。

def cand(board,x,y):
    list = []
    box = checkBox(board,x,y)
    row = checkRow(board,x,y)
    col = checkCol(board,x,y)
    for i in box:
        if i in row and i in col:
            list.append(i)
    if len(list) > 1:
        list = [0]
    elif not list:
        list.append(0)
    return(list)

def solve(board):
    while board.min() == 0:
        row = len(board[0,:])
        col = len(board[:,0])
        for i in range(row):
            for j in range(col):
                if board[i][j] == 0:
                    unique = cand(board,i,j)
                    board[i][j] = unique[0]
    return(board)

我检查了我所有的功能，它们似乎都能正常工作。 cand(board,x,y) 在列表中生成一个唯一的 candadite 或零。

控制台卡在用于二维数组的 B.flatten() 方法上。

这是我正在尝试解决的简单数独 9X9：

easy = np.array([
        [0,0,0,  3,7,0,  0,5,6],
        [5,0,0,  0,1,0,  9,7,0],
        [0,6,0,  9,8,0,  3,4,0],

        [0,0,7,  0,0,2,  0,8,0],
        [0,0,9,  0,3,0,  6,0,0],
        [0,5,0,  0,3,0,  6,0,0],

        [0,7,5,  0,6,9,  0,2,0],
        [0,4,8,  0,2,0,  0,0,5],
        [2,9,0,  0,5,8,  0,0,0]
        ])

感谢任何帮助。想了解我在最后一个函数中的循环有什么问题。谢谢

Answer 1

你的例子不能单独用那个方法解决。它陷入了一个无法找到更多唯一值的无限循环中。

卡住前的最后一局是：

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

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

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

easy中定义的数据不符合数独规则（即同一box/row/column中有多个相同的值，例如中间框中的3）。

此答案的其余部分使用以下内容对此进行补偿：

easy = np.array([
        [0,0,0,  3,7,0,  0,5,6],
        [5,0,0,  0,1,0,  9,7,0],
        [0,6,0,  9,8,0,  3,4,0],

        [0,0,7,  0,0,2,  0,8,0],
        [0,0,9,  0,3,0,  6,0,0],
        [0,5,0,  0,9,0,  7,0,0],

        [0,7,5,  0,6,9,  0,2,0],
        [0,4,8,  0,2,0,  0,0,5],
        [2,9,0,  0,5,8,  0,0,0]
        ])

除了检查 cand 中的唯一编号外，您还可以添加一些检查以查看是否只有一个值能够进入 line/column/box:

def cand(board,x,y):
    list = []
    box = checkBox(board,x,y)
    row = checkRow(board,x,y)
    col = checkCol(board,x,y)

    if len(box) == 1:
        return box

    if len(row) == 1:
        return row

    if len(col) == 1:
        return col

    for i in box:
        if i in row and i in col:
            list.append(i)
    if len(list) > 1:
        list = [0]
    elif not list:
        list.append(0)
    return(list)

这解决了棋盘：

[[9, 8, 1,   3, 7, 4,   2, 5, 6],
 [5, 3, 4,   2, 1, 6,   9, 7, 8],
 [7, 6, 2,   9, 8, 5,   3, 4, 1],

 [3, 1, 7,   6, 4, 2,   5, 8, 9],
 [8, 2, 9,   5, 3, 7,   6, 1, 4],
 [4, 5, 6,   8, 9, 1,   7, 3, 2],

 [1, 7, 5,   4, 6, 9,   8, 2, 3],
 [6, 4, 8,   7, 2, 3,   1, 9, 5],
 [2, 9, 3,   1, 5, 8,   4, 6, 7]]

您可能还应该检查 solve 中的循环是否在未更改任何值以处理程序陷入无限循环的情况下完成。

为什么控制台卡在我在 python 中解决 9X9 数独板的最后一个函数上？

Why is the console getting stuck on my last function to solve a 9X9 sudoku board in python?

python

arrays

function

sudoku