原题传送门

1. 题目描述

2. Solution

1、思路
从上到下，从左到右遍历，每个空位置。在第一个空位置，随便填一个合法的数字，递归在填充后续空位置。如果，期间出现没有数字可以填的话，就回退到上一个位置，换下一个数字，继续。

import sys

if sys.platform != "linux":
    file_in = open("input/HJ44.txt")
    sys.stdin = file_in

board = [list(map(int, line.strip().split())) for line in sys.stdin]


def is_valid(board, row, col, num):
    block_row = (row // 3) * 3
    block_col = (col // 3) * 3
    for i in range(9):
        if board[i][col] == num or board[row][i] == num or board[block_row + i // 3][block_col + i % 3] == num:
            return False
    return True


def solve(board, row, col):
    for i in range(row, 9):
        for j in range(col, 9):
            if board[i][j] != 0:
                continue
            for num in range(1, 10):
                if is_valid(board, i, j, num):
                    board[i][j] = num
                    if solve(board, i, j + 1):
                        return True
                    board[i][j] = 0
            return False
        col = 0
    return True


def main():
    solve(board, 0, 0)
    for rows in board:
        for row in rows:
            print(row, end=" ")
        print()


if __name__ == '__main__':
    main()