题解 | #Sudoku#

1、找到第一个为0为坐标，开始尝试求解
def find_zero(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return i, j
    return None

2、判断输入的value是否正确，即 按行、按列、按区域：值的范围[1,9],且不能重复
def is_valid(board, val, row, col):
    for i in range(9):
        if board[i][col] == val:
            return False

    for j in range(9):
        if board[row][j] == val:
            return False

    row_start = 3 * (row // 3)
    col_start = 3 * (col // 3)
    row_end = row_start + 3
    col_end = col_start + 3
    for x in range(row_start, row_end):
        for y in range(col_start, col_end):
            if board[x][y] == val:
                return False
    return True
3、全局遍历并实现回溯
def dfs(board):
    bl = find_zero(board)
    if not bl:
		# 没有空白了，表示数据填完了
        return True
    else:
        r, c = bl
	# 从第一个空白开始尝试，尝试值为[1,9]
    for val in range(1, 10):
        if is_valid(board, val, r, c):
			# 如果val满足条件，就更新
            board[r][c] = val
			# 递归开始填充后面的空白，如果全部填完则结束，返回True
            if dfs(board):
                return True
			# 否则，回溯数据
            board[r][c] = 0
	# 循环结束，没有满足条件的，则返回False
    return False


def main():
    board = []
    for i in range(9):
        line_s = [int(x) for x in input().split()]
        board.append(line_s)
	# 能完成则输出
    if dfs(board):
        for item in board:
            print(" ".join([str(x) for x in item]))
    else:
        print('ERROR')

main()