# 2018s ナイトの巡歴問題
#1. 基本プログラム（設問1・設問2の完成版）
#図3～図5の擬似コードと、空欄 [ア]～[キ] の解答をそのままPythonに翻訳したコードです

# --- 定数とグローバル変数の定義（表1, 表2より） ---
M = 4 # 盤面の行数 (テスト用に4x3を使用)
N = 3 # 盤面の列数

# ナイトの移動量（[ア]=2, [イ]=-2 を反映）
# 添字1〜8を使うため、先頭(インデックス0)にダミーの0を入れています
dv = [0, -2, -1,  1,  2,  2,  1, -1, -2]
dh = [0,  1,  2,  2,  1, -1, -2, -2, -1]

m = 0
n = 0
board = []
printFlag = 0

# --- 図4: 解答を印字する関数 ---
def printBoard():
    for v in range(1, m + 1):
        row = ""
        for h in range(1, n + 1):
            # 見やすいように2桁でフォーマットして出力
            row += f"{board[v][h]:2d} "
        print(row)
    print("-" * 15)

# --- 図3: ナイトを次のマスへ移動させる再帰関数 ---
def search(i, v, h):
    global printFlag
    if v >= 1 and v <= m:
        if h >= 1 and h <= n:
            if board[v][h] == 0:                  # 通過したマスを判定する
                board[v][h] = i                   # 移動順序を記録する

                if i == m * n:                    # [ウ] 記録した移動順序が M×Nに等しい場合
                    printBoard()                  # 解答を印字する
                    printFlag = 1
                else:
                    for j in range(1, 9):
                        # [エ], [オ], [カ] 次の移動先を調べる
                        search(i + 1, v + dv[j], h + dh[j])

                board[v][h] = 0                   # [キ] 移動順序を取り消す

# --- 図5: メインプログラム ---
def main():
    global m, n, board, printFlag
    m = M
    n = N

    # board[][]を初期化する (添字1〜M, 1〜Nを使うためサイズを+1しています)
    board = [[0] * (N + 1) for _ in range(M + 1)]

    printFlag = 0
    search(1, 1, 1) # 移動順序1, 行1, 列1 からスタート

    if printFlag == 0:
        print("解答がありません。")

if __name__ == "__main__":
    main()