求解騎士游歷問題 
顯然求解騎士游歷問題的每一步就是馬在棋盤上走的一步。在每一步馬需要選擇一個方向進(jìn)行游歷，這時記住解的每一步需要記住兩件事： 
1.當(dāng)前步的行列位置 
2.當(dāng)前步已經(jīng)試探過哪些方向了，以便回溯回來時能夠選擇一個新的方向進(jìn)行試探 
所以使用兩個數(shù)組，數(shù)組board記住棋盤的每個位置是在馬的第幾步到達(dá)的，這反映了問題的解，即第幾步到哪個位置。數(shù)組direction記住在棋盤的某個位置已經(jīng)試探過的方向，每個位置有八個方向，可按某種順序?qū)Π藗€方向編號，然后在每個位置按編號順序試探方向。 
在確定數(shù)據(jù)結(jié)構(gòu)之后，同樣需要確定下面幾個問題： 
1.怎樣的狀態(tài)是初始狀態(tài)。 
2.怎樣選擇當(dāng)前步可能的路線 
3.怎樣表示向前推進(jìn)一步 
4.怎樣回溯及清除當(dāng)前步的痕跡 
顯然初始狀態(tài)是棋盤的每個位置都置為第0步到達(dá)（即還沒有到達(dá)），每個位置都還沒有選擇任何方向（可賦值MAX_DIR(=8)表示沒有選擇方向）。 
選擇當(dāng)前步可能的路線就是在當(dāng)前位置選擇一個方向來游歷下一步。在選擇的時候同樣需要區(qū)分是從第0個方向開始考慮還是從上一次的下一個方向開始考慮。為了方便從下一個方向開始考慮，實際上數(shù)組direction在某一位置(curr_x, curr_y)的值記住的是從上一位置選擇了哪個編號的方向而到達(dá)的，這樣容易回溯到上一位置，而且容易在回溯到上一位置之后從下個一方向重新試探。 
向前推進(jìn)一步則要根據(jù)所選擇的方向推進(jìn)到下一位置，記住到下一位置所選擇的方向，下一位置是第幾步到達(dá)的，然后增加步數(shù)。 
回溯一步則要標(biāo)記當(dāng)前位置沒有到達(dá)過（將到達(dá)的步數(shù)置為0），根據(jù)上一步到當(dāng)前位置的所選擇的方向（這個方向是記錄當(dāng)前位置所對應(yīng)的direction數(shù)組中）而回溯到上一位置，然后減少步數(shù)。 
下面程序用類KNIGHT來封裝數(shù)組board、direction、當(dāng)前位置(curr_x, curr_y)、當(dāng)前步數(shù)(step)，并且使用last_direction來記住上一位置到當(dāng)前位置所選擇的方向。為了方便計算選擇一個方向后從當(dāng)前推進(jìn)到下一位置，使用數(shù)組var_x和var_y來記住每個方向在x方向和y方向的改變值。這個類中提供的方法的含義與類QUEEN類似。為節(jié)省篇幅起見，我們將類的界面、實現(xiàn)及演示放在了同一文件。

///////////////////////////////////////////////////////////////////////
程序二：求解騎士游歷問題的程序 

// 文件：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: 設(shè)置初始狀態(tài) 
KNIGHT(int width); 
// FUNCTION: 用比較直觀的方式打印問題的解 
// REQUIRE: 必須先調(diào)用了成員函數(shù)tourist() 
void print(); 
// FUCTION: 根據(jù)馬的起始位置(start_x, start_y)使用回溯算法求騎士游歷問題的一個解 
// REQUIRE: (start_x, start_y)必需在所設(shè)置的棋盤寬度范圍內(nèi) 
BOOLEAN tourist(int start_x, int start_y); 
protected: 
// FUNCTION: 初始化記錄所選方向的數(shù)組，將每個值置為MAX_DIR 
void init_direction(); 
// FUNCTION: 初始化記錄馬在第幾步到位每個位置的數(shù)組，將每個值置為0 
void init_chessboard(); 
// FUNCTION: 設(shè)置初始狀態(tài)，包括初始化方向數(shù)組和棋盤數(shù)組，并設(shè)置馬的初始位置 
void set_start(int x, int y); 
// FUNCTION: 在當(dāng)前位置選擇一個方向以推進(jìn)到下一位置 
// RETURN: 如果可選擇一個方向推進(jìn)則返回TRUE，否則返回FALSE 
// NOTE: 將該函數(shù)定義為虛函數(shù)，以便下面快速游歷的類來重定義該函數(shù)而產(chǎn)生動態(tài)綁定 
virtual BOOLEAN select_direction(); 
// FUNCTION: 從當(dāng)前位置回溯到上一位置 
// NOTE: 將該函數(shù)定義為虛函數(shù)，以便下面快速游歷的類來重定義該函數(shù)而產(chǎn)生動態(tài)綁定 
virtual void backward(); 
// FUNCTION: 從當(dāng)前位置推進(jìn)到下一位置 
// NOTE: 將該函數(shù)定義為虛函數(shù)，以便下面快速游歷的類來重定義該函數(shù)而產(chǎn)生動態(tài)綁定 
virtual void forward(); 
// FUNCTION: 判斷馬是否能夠走向位置(x, y)。 
// RETURN: 如果馬已經(jīng)到過該位置，或該位置超出棋盤范圍返回FALSE，否則返回TRUE 
BOOLEAN is_legal(int x, int y); 
// FUNCTION: 判斷是否回溯到初始狀態(tài) 
// RETURN: 如果步數(shù)回到第1步則表示回到初始狀態(tài)而返回TRUE，否則返回FALSE 
BOOLEAN back_to_start(); 
// FUNCTION: 判斷是否游歷完所有位置 
// RETURN: 如果步數(shù)等于棋盤格子數(shù)則表示游歷完所有位置而返回TRUE，否則返回FALSE 
BOOLEAN is_end(); 
// 下面兩個數(shù)組用來記住選擇某個方向后，推進(jìn)到下一位置時x方向和y方向的值的變化 
int var_x[MAX_DIR]; 
int var_y[MAX_DIR]; 
// 記錄馬第幾步到達(dá)某個位置的棋盤數(shù)組 
int chessboard[MAX_WIDTH][MAX_WIDTH]; 
// 記錄馬在某個位置是在上一位置選擇第幾個方向到達(dá)的 
int direction[MAX_WIDTH][MAX_WIDTH]; 
int width; // 棋盤寬度 
int curr_x, curr_y; // 馬的當(dāng)前位置 
int step; // 已經(jīng)游歷的步數(shù) 
int last_direct
ion; // 上一位置到當(dāng)前位置所選的方向 
}; 
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表示當(dāng)前位置是一個新的位置，在新推進(jìn)到某個位置(curr_x, curr_y)時， 
// direction[curr_x][curr_y]會記錄上一位置到(curr_x, curr_y)時所選擇的方向，這時 
// last_direction置為MAX_DIR用來標(biāo)記該位置是新推進(jìn)的位置。 
if (last_direction == MAX_DIR) last_direction = 0; 
else last_direction = last_direction + 1; 
while (last_direction < MAX_DIR) { 
// 看下一步推進(jìn)到哪個位置是合法的，如果合法則選擇該方向。 
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]; 
// 根據(jù)這個方向回溯到上一位置，同時回溯到上一位置之后，在上一位置再試探時應(yīng)該從 
// last_direction+1的方向開始。參看成員函數(shù)select_direction()。 
curr_x = curr_x - var_x[last_direction]; 
curr_y = curr_y - var_y[last_direction]; 
} 
void KNIGHT::forward() 
{ 
// 在推進(jìn)時last_direction是當(dāng)前位置所選擇的方向 
curr_x = curr_x + var_x[last_direction];