题目

• 马踏棋盘算法，即骑士周游问题。
• 将马放在国际象棋的 8×8 棋盘的某个方格中，马按走棋规则(马走日字)进行移动。
• 每个方格只进入一次，走遍棋盘上全部 64 个方格。

回溯问题模型

特征

• 解组织成树的形式
• 从根节点开始进行深度优先遍历
• 访问节点时进行判断，是否符合条件，符合就继续，否则进行回溯，此节点后的都不用访问(与暴力算法的区别，降低算法复杂度)

模型

代码

• 代码演示的是5*5的棋盘。
• 递归的出口为步数k=棋盘数M*M。
• 递归主函数就是对每一坐标的8种走法进行判断。符合条件就调用递归函数。
• 然后回溯上一步。
• map变量ma记录棋盘上的每一个坐标是否走过。没有走过的，将其坐标加入map中，成为键，值记录第几步。

#include<iostream>
#include<map>
#include<iomanip> //出输格式设定 
using namespace std;
struct Pos{//定义坐标点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)};
//运算符重载 
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;
}