#!/usr/bin/python3
# -*- coding:utf-8 -*-



"""
递归回溯法：也叫做试探法，按优选条件向前搜索，
当搜索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择，

"""

import sys
import time

SIZE = 5
total = 0

def print_board(board):
    for row in board:
        for col in row:
            print(str(col).center(4),end = '')
        print()

def patrol(board,row,col,step=1):
    if row >=0 and row < SIZE and col >=0 and col < SIZE and board[row][col]==0:
        board[row][col] = step
        if step == SIZE*SIZE:
            global total
            total +=1
            print(f"第{total}种走法：")
            print_board(board)
        patrol(board,row - 2,col - 1,step + 1)
        patrol(board,row - 1,col - 2,step + 1)
        patrol(board,row + 1,col - 2,step + 1)
        patrol(board,row + 2,col - 1,step + 1)
        patrol(board,row + 2,col + 1,step + 1)
        patrol(board,row + 1,col + 2,step + 1)
        patrol(board,row - 1,col + 2,step + 1)
        patrol(board,row - 2,col + 1,step + 1)
        board[row][col] = 0

def main():
    board = [[0]*SIZE for _ in range(SIZE)]
    patrol(board,SIZE-1,SIZE-1)

if __name__=='__main__':
    main()
