骑士遍历2.c

骑士遍历算法！是图论和遍历算法的结合！是说一个骑士的路程算法！

求解骑士游历问题 
显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历，这时记住解的每一步需要记住两件事： 
1.当前步的行列位置 
2.当前步已经试探过哪些方向了，以便回溯回来时能够选择一个新的方向进行试探 
所以使用两个数组，数组board记住棋盘的每个位置是在马的第几步到达的，这反映了问题的解，即第几步到哪个位置。数组direction记住在棋盘的某个位置已经试探过的方向，每个位置有八个方向，可按某种顺序对八个方向编号，然后在每个位置按编号顺序试探方向。 
在确定数据结构之后，同样需要确定下面几个问题： 
1.怎样的状态是初始状态。 
2.怎样选择当前步可能的路线 
3.怎样表示向前推进一步 
4.怎样回溯及清除当前步的痕迹 
显然初始状态是棋盘的每个位置都置为第0步到达（即还没有到达），每个位置都还没有选择任何方向（可赋值MAX_DIR(=8)表示没有选择方向）。 
选择当前步可能的路线就是在当前位置选择一个方向来游历下一步。在选择的时候同样需要区分是从第0个方向开始考虑还是从上一次的下一个方向开始考虑。为了方便从下一个方向开始考虑，实际上数组direction在某一位置(curr_x, curr_y)的值记住的是从上一位置选择了哪个编号的方向而到达的，这样容易回溯到上一位置，而且容易在回溯到上一位置之后从下个一方向重新试探。 
向前推进一步则要根据所选择的方向推进到下一位置，记住到下一位置所选择的方向，下一位置是第几步到达的，然后增加步数。 
回溯一步则要标记当前位置没有到达过（将到达的步数置为0），根据上一步到当前位置的所选择的方向（这个方向是记录当前位置所对应的direction数组中）而回溯到上一位置，然后减少步数。 
下面程序用类KNIGHT来封装数组board、direction、当前位置(curr_x, curr_y)、当前步数(step)，并且使用last_direction来记住上一位置到当前位置所选择的方向。为了方便计算选择一个方向后从当前推进到下一位置，使用数组var_x和var_y来记住每个方向在x方向和y方向的改变值。这个类中提供的方法的含义与类QUEEN类似。为节省篇幅起见，我们将类的界面、实现及演示放在了同一文件。

///////////////////////////////////////////////////////////////////////
程序二：求解骑士游历问题的程序 

// 文件：KNIGHT.CPP 
// 功能：使用回溯算法求解骑士游历问题
#include <iostream.h> 
#include <iomanip.h> 
enum BOOLEAN { 
TRUE = 1, 
FALSE = 0 
}; 
const int MAX_WIDTH = 30; 
const int MAX_DIR = 8; 
class KNIGHT { 
public: 
// FUNCTION: 设置初始状态 
KNIGHT(int width); 
// FUNCTION: 用比较直观的方式打印问题的解 
// REQUIRE: 必须先调用了成员函数tourist() 
void print(); 
// FUCTION: 根据马的起始位置(start_x, start_y)使用回溯算法求骑士游历问题的一个解 
// REQUIRE: (start_x, start_y)必需在所设置的棋盘宽度范围内 
BOOLEAN tourist(int start_x, int start_y); 
protected: 
// FUNCTION: 初始化记录所选方向的数组，将每个值置为MAX_DIR 
void init_direction(); 
// FUNCTION: 初始化记录马在第几步到位每个位置的数组，将每个值置为0 
void init_chessboard(); 
// FUNCTION: 设置初始状态，包括初始化方向数组和棋盘数组，并设置马的初始位置 
void set_start(int x, int y); 
// FUNCTION: 在当前位置选择一个方向以推进到下一位置 
// RETURN: 如果可选择一个方向推进则返回TRUE，否则返回FALSE 
// NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定 
virtual BOOLEAN select_direction(); 
// FUNCTION: 从当前位置回溯到上一位置 
// NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定 
virtual void backward(); 
// FUNCTION: 从当前位置推进到下一位置 
// NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定 
virtual void forward(); 
// FUNCTION: 判断马是否能够走向位置(x, y)。 
// RETURN: 如果马已经到过该位置，或该位置超出棋盘范围返回FALSE，否则返回TRUE 
BOOLEAN is_legal(int x, int y); 
// FUNCTION: 判断是否回溯到初始状态 
// RETURN: 如果步数回到第1步则表示回到初始状态而返回TRUE，否则返回FALSE 
BOOLEAN back_to_start(); 
// FUNCTION: 判断是否游历完所有位置 
// RETURN: 如果步数等于棋盘格子数则表示游历完所有位置而返回TRUE，否则返回FALSE 
BOOLEAN is_end(); 
// 下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化 
int var_x[MAX_DIR]; 
int var_y[MAX_DIR]; 
// 记录马第几步到达某个位置的棋盘数组 
int chessboard[MAX_WIDTH][MAX_WIDTH]; 
// 记录马在某个位置是在上一位置选择第几个方向到达的 
int direction[MAX_WIDTH][MAX_WIDTH]; 
int width; // 棋盘宽度 
int curr_x, curr_y; // 马的当前位置 
int step; // 已经游历的步数 
int last_direct
ion; // 上一位置到当前位置所选的方向 
}; 
KNIGHT::KNIGHT(int width) 
{ 
this->width = width; 
init_direction(); 
total_step = 0; 
} 
void KNIGHT::print() 
{ 
int x, y; 
cout << " +"; 
for (x = 0; x < width; x = x + 1) cout << "----+"; 
cout << '\n'; 
for (x = 0; x < width; x = x + 1) { 
cout << " |"; 
for (y = 0; y < width; y = y + 1) cout << setw(3) << chessboard[x][y] << " |"; 
cout << '\n'; 
cout << " +"; 
for (y = 0; y < width; y = y + 1) cout << "----+"; 
cout << '\n'; 
} 
} 
BOOLEAN KNIGHT::is_legal(int x, int y) 
{ 
if (x < 0 || x >= width) return FALSE; 
if (y < 0 || y >= width) return FALSE; 
if (chessboard[x][y] > 0) return FALSE; 
return TRUE; 
} 
BOOLEAN KNIGHT::back_to_start() 
{ 
if (step == 1) return TRUE; 
else return FALSE; 
} 
BOOLEAN KNIGHT::is_end() 
{ 
if (step > width * width) return TRUE; 
else return FALSE; 
} 
void KNIGHT::set_start(int x, int y) 
{ 
curr_x = x; curr_y = y; step = 1; 
chessboard[x][y] = step; step = step + 1; 
direction[x][y] = MAX_DIR; 
last_direction = MAX_DIR; 
} 
BOOLEAN KNIGHT::select_direction() 
{ 
int try_x, try_y; 
// last_direction为MAX_DIR表示当前位置是一个新的位置，在新推进到某个位置(curr_x, curr_y)时， 
// direction[curr_x][curr_y]会记录上一位置到(curr_x, curr_y)时所选择的方向，这时 
// last_direction置为MAX_DIR用来标记该位置是新推进的位置。 
if (last_direction == MAX_DIR) last_direction = 0; 
else last_direction = last_direction + 1; 
while (last_direction < MAX_DIR) { 
// 看下一步推进到哪个位置是合法的，如果合法则选择该方向。 
try_x = curr_x + var_x[last_direction]; 
try_y = curr_y + var_y[last_direction]; 
if (is_legal(try_x, try_y)) break; 
last_direction = last_direction + 1; 
} 
if (last_direction == MAX_DIR) return FALSE; 
else return TRUE; 
} 
void KNIGHT::backward() 
{ 
step = step - 1; 
chessboard[curr_x][curr_y] = 0; 
// 将last_direction置为上一位置到(curr_x, curr_y)所选择的方向 
last_direction = direction[curr_x][curr_y]; 
// 根据这个方向回溯到上一位置，同时回溯到上一位置之后，在上一位置再试探时应该从 
// last_direction+1的方向开始。参看成员函数select_direction()。 
curr_x = curr_x - var_x[last_direction]; 
curr_y = curr_y - var_y[last_direction]; 
} 
void KNIGHT::forward() 
{ 
// 在推进时last_direction是当前位置所选择的方向 
curr_x = curr_x + var_x[last_direction];