題目

• 馬踏棋盤(pán)算法，即騎士周游問(wèn)題。
• 將馬放在國(guó)際象棋的 8×8 棋盤(pán)的某個(gè)方格中，馬按走棋規(guī)則(馬走日字)進(jìn)行移動(dòng)。
• 每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部 64 個(gè)方格。

回溯問(wèn)題模型

特征

• 解組織成樹(shù)的形式
• 從根節(jié)點(diǎn)開(kāi)始進(jìn)行深度優(yōu)先遍歷
• 訪(fǎng)問(wèn)節(jié)點(diǎn)時(shí)進(jìn)行判斷，是否符合條件，符合就繼續(xù)，否則進(jìn)行回溯，此節(jié)點(diǎn)后的都不用訪(fǎng)問(wèn)(與暴力算法的區(qū)別，降低算法復(fù)雜度)

模型

代碼

• 代碼演示的是5*5的棋盤(pán)。
• 遞歸的出口為步數(shù)k=棋盤(pán)數(shù)M*M。
• 遞歸主函數(shù)就是對(duì)每一坐標(biāo)的8種走法進(jìn)行判斷。符合條件就調(diào)用遞歸函數(shù)。
• 然后回溯上一步。
• map變量ma記錄棋盤(pán)上的每一個(gè)坐標(biāo)是否走過(guò)。沒(méi)有走過(guò)的，將其坐標(biāo)加入map中，成為鍵，值記錄第幾步。

#include<iostream>
#include<map>
#include<iomanip> //出輸格式設(shè)定 
using namespace std;
struct Pos{//定義坐標(biāo)點(diǎn)int x;int y;Pos(int x,int y){this->x=x;this->y=y;}
}; 
int count=0;//記錄一共有多少種解法
void show(int M,map<Pos,int>& ma);
//馬的8種走法
Pos delta[]={Pos(-1,2),Pos(-1,-2),Pos(1,2),Pos(1,-2),Pos(2,1),Pos(2,-1),Pos(-2,1),Pos(-2,-1)};
//運(yùn)算符重載 
Pos operator+(Pos a,Pos b){return Pos(a.x+b.x,a.y+b.y);
}
//馬走的步法是否有效，如果出了格子表示bad，即為true
bool outOfBounds(int M,Pos p){if(p.x<0 || p.x>= M) return true;if(p.y<0 || p.y>= M) return true;return false;
}
//自定義變量Pos需要用map，則須重載<，確保Pos能比較大小 
bool operator< (Pos a,Pos b){if(a.x != b.x) return a.x < b.x;return a.y < b.y;
}
//bool operator<(const Pos& p) const{
//	if(this->x !=p.x) return this->x < p.x;
//	return this->y < p.y;
//}
bool f(int M,map<Pos,int>& ma,Pos p,int k){if(k==M*M){++count;cout<< count<<endl;show(M,ma);return true;} 		for(int i=0;i<8;i++){Pos p1=p+delta[i];if(outOfBounds(M,p1)) continue;if(ma.count(p1)) continue;ma[p1] = k+1;f(M,ma,p1,k+1);ma.erase(p1);}return false;
}
void show(int M,map<Pos,int>& ma){for(int i=0;i<M;i++){for(int j=0;j<M;j++){cout <<setw(3)<<ma[Pos(i,j)];}cout<<endl;}cout<<"********************"<<endl;
}
void horse(int M){map<Pos,int> ma;Pos p(0,0);ma[p]=1;f(M,ma,p,1); 		
}
int main(){horse(5);cout<<"總共有："<<count<<"種走法"; return 0;
}