如何修正数独求解程序中的对角线唯一性检查逻辑？

需求描述 #

编写程序求解9阶数独谜题，空单元格用0表示，需满足以下规则：

• 主对角线（左上至右下）中的数字必须唯一；
• 副对角线（右上至左下）中的数字必须唯一；
• 每个3×3子网格中的数字必须唯一；
• 行和列允许数字重复。

问题现状 #

已编写的Python数独求解代码中，对角线唯一性检查逻辑存在错误，导致输出结果不符合约束要求，需要修正逻辑以确保对角线和3×3子网格内无重复数字。

尝试的代码 #

N = 9
def printing(arr):
    for i in range(N):
        for j in range(N):
            print(arr[i][j], end=" ")
        print()


def isSafe(grid, row, col, num):
    for x in range(9):
        if grid[x][x] == num:
            return False
    cl = 0
    for y in range(8, -1, -1):
        if grid[cl][y] == num:
            cl += 1
            return False
    startRow = row - row % 3
    startCol = col - col % 3
    for i in range(3):
        for j in range(3):
            if grid[i + startRow][j + startCol] == num:
                return False
    return True


def solveSudoku(grid, row, col):
    if (row == N - 1 and col == N):
        return True
    if col == N:
        row += 1
        col = 0
    if grid[row][col] > 0:
        return solveSudoku(grid, row, col + 1)
    for num in range(1, N + 1, 1):
        if isSafe(grid, row, col, num):
            grid[row][col] = num
            print(grid)  # 此处会打印大量中间状态，建议注释或删除
            if solveSudoku(grid, row, col + 1):
                return True
        grid[row][col] = 0
    return False

# 原代码缺失grid定义，需补充测试输入的grid
if (solveSudoku(grid, 0, 0)):
    printing(grid)
else:
    print("Solution does not exist")

测试输入 #

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

当前错误输出 #

8 3 7 0 4 2 1 2 4
5 0 6 1 8 6 3 6 7 
4 1 2 7 3 5 5 0 8 
2 8 3 5 4 8 6 0 5 
6 5 0 0 7 1 2 1 7 
1 4 7 3 2 6 8 4 3 
7 8 1 4 1 6 3 5 0 
6 2 3 7 3 5 7 4 2 
0 5 4 2 8 0 6 8 1

问题分析与修正方案 #

原代码核心问题 #

1. 主对角线检查逻辑错误：无论当前填充单元格是否在主对角线上，都遍历整个主对角线判断重复，导致大量合法数字被误判。
2. 副对角线检查逻辑错误：循环中找到第一个匹配数字就直接返回False，且cl +=1在return之前，实际只检查了副对角线第一个元素；同时未判断当前单元格是否在副对角线上就执行检查。

修正后的代码 #

N = 9
def printing(arr):
    for i in range(N):
        for j in range(N):
            print(arr[i][j], end=" ")
        print()


def isSafe(grid, row, col, num):
    # 仅当前位置在主对角线上时，检查主对角线重复
    if row == col:
        for x in range(N):
            if grid[x][x] == num:
                return False
    # 仅当前位置在副对角线上时，检查副对角线重复（9阶数独副对角线满足row+col=8）
    if row + col == N - 1:
        for x in range(N):
            if grid[x][(N-1)-x] == num:
                return False
    # 检查3×3子网格重复
    startRow = row - row % 3
    startCol = col - col % 3
    for i in range(3):
        for j in range(3):
            if grid[i + startRow][j + startCol] == num:
                return False
    return True


def solveSudoku(grid, row, col):
    if row == N - 1 and col == N:
        return True
    if col == N:
        row += 1
        col = 0
    if grid[row][col] > 0:
        return solveSudoku(grid, row, col + 1)
    for num in range(1, N + 1):
        if isSafe(grid, row, col, num):
            grid[row][col] = num
            if solveSudoku(grid, row, col + 1):
                return True
        grid[row][col] = 0
    return False

# 测试输入
grid = [
    [0, 3, 7, 0, 4, 2, 0, 2, 0],
    [5, 0, 6, 1, 0, 0, 0, 0, 7],
    [0, 0, 2, 0, 0, 0, 5, 0, 0],
    [2, 8, 3, 0, 0, 0, 0, 0, 0],
    [0, 5, 0, 0, 7, 1, 2, 0, 7],
    [0, 0, 0, 3, 0, 0, 0, 0, 3],
    [7, 0, 0, 0, 0, 6, 0, 5, 0],
    [0, 2, 3, 0, 3, 0, 7, 4, 2],
    [0, 5, 0, 0, 8, 0, 0, 0, 0]
]

if solveSudoku(grid, 0, 0):
    printing(grid)
else:
    print("Solution does not exist")

修正说明 #

1. 主对角线检查：增加row == col判断，仅当前单元格在主对角线上时，才遍历主对角线检查重复。
2. 副对角线检查：增加row + col == N -1判断，同时正确遍历整个副对角线所有元素。
3. 冗余处理：删除了中间网格打印代码，避免输出混乱。

验证结果 #

修正后的代码会输出满足所有约束的数独解，确保主副对角线、3×3子网格内无重复数字，行和列允许重复。

内容的提问来源于stack exchange，提问作者Racoon