# 2018s ナイトの巡歴問題
#1. 番兵を考えたプログラム
# --- 定数とグローバル変数の定義 ---
M = 4 # 盤面の行数 (テスト用に4x3を使用)
N = 3 # 盤面の列数

# ナイトの移動量（インデックス1〜8を使用するため、先頭にダミーの0を配置）
dv = [0, -2, -1,  1,  2,  2,  1, -1, -2]
dh = [0,  1,  2,  2,  1, -1, -2, -2, -1]

m = M
n = N
printFlag = 0

# 【番兵の配置】
# 盤面サイズを拡大（上下左右に2マスずつの余白 ＝ +4マス）
# 添字を1始まりに合わせるための+1と合わせて、+5のサイズを確保
# 初期値はすべて範囲外を示す「1」で埋める
board = [[2] * (N + 5) for _ in range(M + 5)]

# ナイトが移動できる本来の範囲（3〜m+2行、3〜n+2列）だけ未訪問を示す「0」にする
for v in range(3, m + 3):
    for h in range(3, n + 3):
        board[v][h] = 0

# --- 関数 printBoard ---
def printBoard():
    # 印刷範囲を 3 から m+2, n+2 に変更 (設問3 (1) の対応)
    for v in range(3, m + 3):
        row = ""
        for h in range(3, n + 3):
            # 見やすいように2桁でフォーマットして出力
            row += f"{board[v][h]:2d} "
        print(row)
    print("-" * 15)

# --- 再帰関数 search ---
def search(i, v, h):
    global printFlag

    # 【効率化】
    # 盤面範囲内かのチェック(if v>=1 かつ v<=m など)が削除されています。
    # 外側には番兵(1)が敷き詰められているため、はみ出しても下の判定で自動ブロックされます。

    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                   # 移動順序を取り消す（バックトラック）

# --- メインプログラム ---
def main():
    global printFlag
    printFlag = 0

    # 探索のスタート位置を (3, 3) に変更 (設問3 (2) の対応)
    search(1, 3, 3)

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

if __name__ == "__main__":
    main()