# 2022s パズルの解答を求める

# 1次元配列で表現された盤面 (0は空白を表す)
# 問題文の「図1 問題例」を再現しています
board = [
    2, 0, 1, 0, 9, 0, 7, 0, 0,
    0, 4, 0, 2, 0, 0, 3, 0, 0,
    5, 0, 0, 0, 0, 8, 0, 2, 9,
    0, 9, 0, 6, 7, 0, 2, 0, 0,
    6, 0, 0, 3, 0, 5, 0, 0, 4,
    0, 0, 7, 0, 4, 9, 0, 1, 0,
    7, 6, 0, 9, 0, 0, 0, 0, 3,
    0, 0, 9, 0, 0, 6, 0, 4, 0,
    0, 0, 4, 0, 1, 0, 6, 0, 0
]

MAX_BOARD = 81

# 表1の補助関数を再現
def div(n, m):
    return n // m  # 整数で割った商

def mod(n, m):
    return n % m   # 割った余り

# 図6：横1行の重複チェック
def row_ok(n, x):
    row_top = div(x, 9) * 9  # 空欄 [オ]
    for i in range(9):       # 0から8までループ
        if board[row_top + i] == n:  # 空欄 [カ]
            return False
    return True

# 図6：縦1列の重複チェック
def column_ok(n, x):
    column_top = mod(x, 9)   # 空欄 [キ]
    for i in range(9):       # 0から8までループ
        if board[column_top + 9 * i] == n:  # 空欄 [ク]
            return False
    return True

# 図6：3×3の枠内の重複チェック
def frame_ok(n, x):
    frame_top = x - mod(div(x, 9), 3) * 9 - mod(x, 3)  # 空欄 [ケ]
    for i in range(3):       # 0から2までループ
        for j in range(3):   # 0から2までループ
            if board[frame_top + 9 * i + j] == n:
                return False
    return True

# 表1：すべての重複チェックを実行する関数
def check_ok(n, x):
    # すべてのチェックで重複がない(True)場合のみTrueを返す
    if row_ok(n, x) and column_ok(n, x) and frame_ok(n, x):
        return True
    return False

# 表1：盤面の内容を9×9の形に出力する関数
def print_board():
    for i in range(9):
        # 9マスごとに区切って表示
        row = board[i * 9 : (i + 1) * 9]
        print(" ".join(map(str, row)))
    print("-" * 20)

# 図5：関数 solve(x)
def solve(x):
    # 終了条件：すべてのマス（0〜80）をチェックし終えた場合
    if x > MAX_BOARD - 1:
        print_board()  # 解答を出力する
        exit()         # メインプログラムの処理を終了する
    else:
        # 対象のマスが空白でない（すでに数字がある）場合
        if board[x] != 0:  # 空欄 [ア]
            solve(x + 1)   # 次の探索：空欄 [イ]
        else:
            # 1〜9の数字を順にマスに入れる
            for n in range(1, 10):  # range(1, 10)は1から9まで
                if check_ok(n, x):  # 空欄 [ウ]
                    board[x] = n    # 数字を仮置き
                    solve(x + 1)    # 次の探索：空欄 [イ]
                    board[x] = 0    # 再帰から戻った場合のマスの初期化：空欄 [エ]

# 図4：メインプログラム
def main():
    # 盤面はすでに大域変数として初期化されているものとします
    solve(0)  # 盤面の左上端のマスを示す添字0を引数として呼び出す

# プログラムの実行
if __name__ == "__main__":
    main()