1.　　问题描述

在一个n*n的棋盘上，一个放在棋盘上某个位置的马是否可以恰好访问每个方格一次，并且回到起始位置上？

2.　　回溯法的一般思路

深度优先搜索，若寻找到满足要求的解，则输出；否则推回上一层往下一个方向搜索。

3.　　求解问题的回溯算法描述

对于当前所在位置（x，y），依次枚举n个方向搜索，直到找到一组可行解为止。使用剪枝有3处：第一、使用Warnsdorff s rule，枚举当前解得时候优先选择下一步可行步数最少的方向；第二、若第一点中的方向存在不止一个，则优先选择离中心位置较远的方向；第三、每次都从中心点开始出发，求出一条合法路径后再平移映射回待求路径。

4.　　算法实现的关键技巧

在棋盘较大的时候，使用递归会使得函数暴栈，故应当使用非递归方法实现。程序实现时应细心记录清楚当前状态在栈顶。

-1 Descr iption of the problem

On the board a n* n chessboard, a horse of a location can be just visit each square once and return to the starting position?

The general idea of backtracking

The depth-first search, to find solutions to meet the requirements, then output　Otherwise, push back on the layer down a direction to search.

3 backtracking algorithm for solving the problem described

Sequentially enumeration for the current location (x, y) of the n-th direction search until it finds a set of feasible solutions so far. 3: use pruning first, Warnsdorff s rule, enumerate the current direction when Select Next feasible steps at least　Second, if the first point in the direction of the existence of more than one, the Select from the center the direction of the remote location　each time starting from the center point of departure, the unknown path mapped back to the pan and then obtained a legitimate path.

Algorithm key skills

In the checkerboard larger when using the recursive ma