curr_y = curr_y + var_y[last_direction]; 
chessboard[curr_x][curr_y] = step; 
step = step + 1; 
// 這個方向被記錄下一位置(這時已經為(curr_x, curr_y))的direction數組中。 
direction[curr_x][curr_y] = last_direction; 
// last_direction的值已經被記錄，這時置為MAX_DIR表示當前位置為新推進的位置 
last_direction = MAX_DIR; 
} 
BOOLEAN KNIGHT::tourist(int start_x, int start_y) 
{ 
init_chessboard(); 
set_start(start_x, start_y); 
do { 
if (select_direction()) forward(); 
else backward(); 
} while (!back_to_start() && !is_end()); 
if (back_to_start()) return FALSE; 
else return TRUE; 
} 
void KNIGHT::init_direction() 
{ 
var_x[0] = 2; var_y[0] = 1; 
var_x[1] = 1; var_y[1] = 2; 
var_x[2] = -1; var_y[2] = 2; 
var_x[3] = -2; var_y[3] = 1; 
var_x[4] = -2; var_y[4] = -1; 
var_x[5] = -1; var_y[5] = -2; 
var_x[6] = 1; var_y[6] = -2; 
var_x[7] = 2; var_y[7] = -1; 
} 
void KNIGHT::init_chessboard() 
{ 
int x, y, dir; 
for (x = 0; x < width; x = x + 1) { 
for (y = 0; y < width; y = y + 1) { 
chessboard[x][y] = 0; 
} 
} 
} 
int main() 
{ 
int width = 8; 
KNIGHT knight(width); 
int start_x, start_y; 
cout << "\nProgram begin...\n"; 
start_x = 4; start_y = 4; 
if (knight.tourist(start_x, start_y)) { 
knight.print(); 
}else { 
cout << "\nHave not found the solution for: "; 
cout << "Start: <" << start_x << ", " << start_y << ">, "; 
cout << "Width: " << width << "\n"; 
} 
return 1; 
} 

l 騎士游歷問題的快速解
上面求解騎士游歷問題的程序效率比較低，對于8×8的棋盤將花費相當長一段時間。為此我們可以在選擇當前步的可能路線時增加一些啟發式規則，使得這個選擇從某種意義下來說是比較好的，從而加速問題的求解過程。 
對于騎士游歷問題一個啟發式規則是，在選擇當前步的方向時去選擇滿足下面條件的方向，當按這個方向推進到下一位置時，這個位置所可以再選擇的方向最少。也就是說在當前位置優先選一個走起來比?quot;艱難"的方向來推進。加入這種啟發式規則之后，從運行的效果看，在求解的過程中幾乎不回溯。 
為了使用這個啟發式規則，我們首先要修改上面的成員函數select_direction()。這時在每個位置選擇方向時不再是按照一定的順序來選擇，為了避免在回溯時重復選擇方向，必需記住在某個位置哪些方向已經選擇過了，我們使用三維數組cannot來記住這件事情，當其值為TRUE時表示某個位置的某個方向已經試探過了，為FALSE表示沒有試探過。當從當前位置回溯到上一位置是，要先把當前位置所有方向的cannot值置為FALSE，因為下一次再到達這個位置時所有方向需要重新試探。 
為了研究加入啟發式規則的效果，要求保留上面不使用啟發式規則的程序，這樣我們從KNIGHT類派生出一個類FAST_KNIGHT來支持快速求解騎士游歷問題。在這個類中增加數組cannot，并且只需要重新定義select_direction(), backward()和forward()就可以了。需要重新定義backward()和forward()是因為在這兩個成員函數中需要維護數組cannot的值。其它成員函數不用作任何的修改。我們在KNIGHT類中已經將這幾個成員函數定義為虛函數，以便在成員函數tourist()中動態地選擇這些函數來調用。讀者需要學習完第八章多態性之后才能充分理解動態綁定的含義。 
在下面程序中，我們只給出類FAST_KNIGHT的定義，讀者很容易修改演示程序以使用類FAST_KNIGHT來求解騎士游歷問題。 

程序三：快速求解騎士游歷問題的程序 

// 文件：FASTKNIGHT.CPP 
// 功能：使用回溯算法快速求解騎士游歷問題 
class FAST_KNIGHT: public KNIGHT { 
public: 
FAST_KNIGHT(int width); 
protected: 
// FUNCTION: 初始化cannot數組 
void init_cannot(); 
// FUNCTION: 在當前位置根據啟發式規則選擇一個方向以推進到下一位置 
// RETURN: 如果可選擇一個方向推進則返回TRUE，否則返回FALSE 
// NOTE: 重定義KNIGHT類的select_direction() 
virtual BOOLEAN select_direction(); 
// FUNCTION: 從當前位置回溯到上一位置，注意維持cannot數組 
// NOTE: 重定義KNIGHT類的backward() 
virtual void backward(); 
// FUNCTION: 從當前位置根據所選擇的方向推進到下一位置 
// NOTE: 重定義KNIGHT類的forward() 
virtual void forward(); 
// 用來記住某個位置某個方向是否已經試探過 
BOOLEAN cannot[MAX_WIDTH][MAX_WIDTH][MAX_DIR]; 
}; 
FAST_KNIGHT::FAST_KNIGHT(int width): KNIGHT(width) 
{ 
init_cannot(); 
} 
void FAST_KNIGHT::init_cannot() 
{ 
int x, y, dir; 
for (x = 0; x < width; x = x + 1) 
for (y = 0; y < width; y = y + 1) 
for (dir = 0; dir < width; dir = dir + 1) cannot[x][y][dir] = FALSE; 
} 
BOOLEAN FAST_KNIGHT::select_direction() 
{ 
int try_x, try_y, next_x, next_y; 
int dir_index, next_index; 
int min_dir, count; 
min_dir = MAX_DIR; last_direction = MAX_DIR; 
for (dir_index = 0; dir_index < MAX_DIR; dir_index = dir_index + 1) { 
// 選擇一個方向，使得根據該方向推進到下一位置時，在該位置可選的方向最少 
try_x = curr_x + var_x[dir_index]; 
try_y = curr_y + var_y[dir_index]; 
if (is_legal(try_x, try_y) && !cannot[curr_x][curr_y][dir_index]) { 
// 這個位置作為下一位置是合法，那么計算該位置可選的方向 
count = 0; 
for (next_index = 0; next_index < MAX_DIR; next_index++) { 
next_x = try_x + var_x[next_index]; 
next_y = try_y + var_y[next_index]; 
if (is_legal(next_x, next_y)) count = count + 1; 
} 
if (count < min_dir) { 
// 記錄具有最少可選方向的下一位置 
last_direction = dir_index; 
min_dir = count; 
} 
} 
} 
if (last_direction == MAX_DIR) return FALSE; 
else return TRUE; 
} 
void FAST_KNIGHT::backward() 
{ 
int dir; 
step = step - 1; 
chessboard[curr_x][curr_y] = 0; 
// 從位置(curr_x, curr_y)回溯，那么下一次再到達該位置時所有方向都需要重新試探 
for (dir = 0; dir < MAX_DIR; dir = dir + 1) cannot[curr_x][curr_y][dir] = FALSE; 
last_direction = direction[curr_x][curr_y]; 
curr_x = curr_x - var_x[last_direction]; 
curr_y = curr_y - var_y[last_direction]; 
} 
void FAST_KNIGHT::forward() 
{ 
// 該位置的這個方向已經試探過了 
cannot[curr_x][curr_y][last_direction] = TRUE; 
curr_x = curr_x + var_x[last_direction]; 
curr_y = curr_y + var_y[last_direction]; 
chessboard[curr_x][curr_y] = step; 
step = step + 1; 
direction[curr_x][curr_y] = last_direction; 
last_direction = MAX_DIR; 
} 

l 思考與提高 
在充分理解上述三個程序之后，讀者可進一步思考下述問題： 
1.上述求解八皇后問題的程序中數組board不是必須的，因為根據solution數組完全可算出哪個位置有皇后，修改上述程序使得不需要數組board而給出八皇后問題的所有解。 
2.思考快速求解騎士游歷問題中的啟發式規則為什么能夠使得在求解過程中幾乎不回溯。進一步類比該啟發式規則，考慮在求八皇后問題的一個解時可利用怎樣的啟發式規則以加速求解過程。 
3.使用回溯算法求解迷宮問題，自己給出迷宮問題的進一步陳述，設計所需要的數據結構，并細化上述回溯算法。 
4.理解上述快速求解騎士游歷問題的程序，體會在設計算法時的自頂向上分解、逐步求精的思想，進一步體會使用面向對象程序設計思想，特別是利用動態綁定的好處。