骑士巡游问题

正在复习python，有人请教骑士巡游问题，就用python试着写了一个。开始没考虑优化的问题，因为python递归的次数限制，程序在大棋盘上屡屡崩溃；还有一个是速度太慢，于是进行了优化。

优化的原理很简单，就是将当前位置上的下一个可能位置（最多八个）按照其下一个可能位置的总数从小到大排列。这话有点绕人，这样说吧，当前位置上可能有零到八个可选位置，零只能回退，一个没得选，其他情况下，考虑将这些位置的按照其下一个可选位置总数排序，少的在前面，优先遍历。

import time
from functools import cmp_to_key

WIDTH = 8
HEIGHT = 8
chess_board = [[0 for i in range(WIDTH)] for j in range(HEIGHT)]
jump = [[1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2]]
finished = False


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return str(self.x) + ', ' + str(self.y)


def show():
    for row in chess_board:
        for column in row:
            print(column, end="\t")

        print()


def cmp_next(p1, p2):
    num1 = len(next_points(p1))
    num2 = len(next_points(p2))
    return num1 - num2


def next_points(p):
    points = list()
    for i in range(len(jump)):
        x = p.x + jump[i][0]
        y = p.y + jump[i][1]

        if 0 <= x < WIDTH and 0 <= y < HEIGHT and chess_board[x][y] == 0:
            points.append(Point(x, y))

    return points


def traversal_chess_board(row, column, step):
    global finished

    chess_board[row][column] = step
    ps = next_points(Point(row, column))
    ps.sort(key=cmp_to_key(cmp_next))

    for i in range(len(ps)):
        if chess_board[ps[i].x][ps[i].y] == 0:
            traversal_chess_board(ps[i].x, ps[i].y, step + 1)
    ps.clear()

    if step < WIDTH * HEIGHT and not finished:
        chess_board[row][column] = 0
    else:
        finished = True


if __name__ == '__main__':
    start_row = input('输入出发点坐标x: ')
    start_column = input('输入出发点坐标y: ')

    start_time = time.time()
    traversal_chess_board(int(start_row), int(start_column), 1)
    stop_time = time.time()
    show()
    print("运行时间： ", (stop_time - start_time))