完成数独的算法 python_数独（Sudoku）问题的Python实现

以下是一个数独求解器的Python实现，基于回溯算法：

def solve_sudoku(board):
    """
    :type board: List[List[str]]
    :rtype: void Do not return anything, modify board in-place instead.
    """
    def is_valid(row, col, val):
        # check row
        for i in range(9):
            if board[row][i] == val:
                return False
        # check column
        for i in range(9):
            if board[i][col] == val:
                return False
        # check sub-box
        box_row, box_col = row // 3 * 3, col // 3 * 3
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == val:
                    return False
        return True
    
    def backtrack(row, col):
        if col == 9:
            row += 1
            col = 0
        if row == 9:
            return True
        if board[row][col] != '.':
            return backtrack(row, col+1)
        for val in range(1, 10):
            if is_valid(row, col, str(val)):
                board[row][col] = str(val)
                if backtrack(row, col+1):
                    return True
                board[row][col] = '.'
        return False
    
    backtrack(0, 0)

使用方法：

board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
         ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
         ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
         ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
         ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
         ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
         ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
         ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
         ['.', '.', '.', '.', '8', '.', '.', '7', '9']]
solve_sudoku(board)
print(board)

输出结果：

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