骑士游历问题算法的研究

惠燕，潘煜

（西安工业大学 计算机学院，陕西 西安 710032）

骑士游历问题是一个古老而著名的问题，问题的描述是：在8×8格的国际象棋棋盘上，象棋马能否从某个格子出发按照“马跳日”的规则跳遍所有64个格子最后再回到出发的那个格子?国际象棋中的马，英语为knight，恰好又意指中世纪西方世界的“骑士”，因此，这个问题又被称为 “骑士游历”问题。该问题即可以理解为国际象棋中的棋子在一个空棋盘内移动，问它能否经过六十四格并且只经过一次？骑士按“L”形路线移动，即在某方向前进两格，接着在与原方向垂直的方向上前进一格。

1 骑士游历问题模型的数学抽象

走的方向上相应的数据变化的确定[2-3]。

1.1 方向的研究

1.1.1 方向的分类

骑士游历的规则确定了骑士游历的方向。在国际象棋的棋盘里总共有8×8个格子，若使棋子“骑士”从任何一个格子开始，按照L形路线（在某方向前进两格，接着在与原方向垂直的方向上前进一格）移动方法，游历每一个格子，并且每个格子只允许被到达一次，则每次骑士可走的有8个方向的选择。图1是骑士将某一位置作为起始位置，继续按照在某方向前进2格，接着在与原方向垂直的方向前进1格的方式即所谓L形路线可走的8个方向的示意图。

骑士游历问题最初是由大数学家欧拉（Euler）在1759年开始研究的。定义1：给定无孤立结点图G，若存在一条路，经过图中每边一次且仅一次，该路称为欧拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路[1]。……