//by?ngl
#include???
#include???
#include???
????????
int?bushu[8][8];	//?bushu[i][j]表示騎士到達棋盤上位置（ij）的行走步數
int?x??y?;			//記錄騎士所在位置的x、y坐標
int?count=0;		//記錄騎士周游列國的方法數
int?movexy[8][2]={{-21}??{-12}??{12}??{21}?{2-1}??{1-2}??{-1-2}??{-2-1}};???//騎士在當前位置可以選擇行走的8個位置

void?output（）???//搜索到葉結點時，找到一種騎士周游列國的方法，輸出騎士行走路徑的8*8矩陣
{???
	cout<<“方法“<????for（int?i?=?0?;?i?????{??
		for（int?j?=?0?;?j?			printf（“%4d“??bushu[i][j]）;??
????????cout<????}???????????
????system（“pause“）;????//由于騎士周游列國有很多種行走方法，每輸出一種方法等待鍵盤輸入再輸出另一種方法，
						//這里不調用system（“pause“）結果輸出很快，會看不清楚??
}???

void?knight（int?k）??????//遞歸回溯法解騎士周游列國問題
{???????????????????????????
	if（k?==?64）		????//搜索到葉結點時，找到一種騎士周游列國的方法
	{??
		count++;		//方法數自增1
		output（）;		//輸出騎士行走路徑的8*8矩陣
????????return;?????????????
????}???

	//搜索子樹
????for（int?i?=?0?;?i?????{?????????
		int?r?=?x?+?movexy[i][0];???//騎士選擇第i個位置行走
????????int?c?=?y?+?movexy[i][1];???
????????if（r?>=?0?&&?r?=?0?&&?c?????????{???
????????????x?=?r?;?
			y?=?c;???
????????????bushu[r][c]?=?k?+?1;	//解空間樹樹中第k層結點的步數為k+1
????????????knight（k+1）;			//搜索子樹?
????????????bushu[r][c]?=?0;????????//往上回溯時，恢復相關值
????????????x?=?r?-?movexy[i][0];???
????????????y?=?c?-?movexy[i][1];???
????????}?????????????????????????????????
	}?????
}???
????????
int?main（）???
{???????
	for（int?i?=?0?;?i?		for（int?j?=?0?;?j?			bushu[i][j]?=?0;???
????bushu[0][0]=1;???//以（00）為起點的周游路線。????
	
????cout<<“其實初始位置為（00）“<		<<“數字代表的是第幾步:\n“<????knight（1）;		//由于騎士的初始位置已經確定了，所以回溯算法調用knight（1）

	system（“PAUSE“）;

	return?0;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????2144??2010-12-15?19:17??騎士周游列國\program\騎士周游列國.cpp

?????文件???????3475??2010-12-15?19:19??騎士周游列國\program\騎士周游列國.dsp

?????文件??????33792??2010-12-15?19:19??騎士周游列國\program\騎士周游列國.ncb

?????文件???????1219??2010-12-15?19:19??騎士周游列國\program\騎士周游列國.plg

?????文件??????48640??2010-12-15?19:19??騎士周游列國\program\騎士周游列國.opt

?????文件????????549??2010-12-15?19:19??騎士周游列國\program\騎士周游列國.dsw

?????文件????1972736??2010-12-15?19:20??騎士周游列國\騎士周游列國.doc

?????目錄??????????0??2010-12-15?19:16??騎士周游列國\program

?????目錄??????????0??2010-12-15?19:16??騎士周游列國

-----------?---------??----------?-----??----

??????????????2062555????????????????????9