回溯（backtracking）：
有“通用解题法”之称。用它可以系统地搜索问题的所有解。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过对以该节点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略继续搜索。
八皇后问题：
问题描述：在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
#include <iostream>
#include <cmath>
#define N 8
using namespace std;
int a[8];//皇后每行每列有且只能有一个，所以用a[i]代表第i个皇后(在第i行)放在第a[i]列
int cnt=1;//记录解的序号
void search(int m);
int canPlace(int row ,int col);
void printResult();
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
search(0);
return 0;
}
void search(int m)
{
if(m>=N)printResult();
else
{
int i;
for(i=0;i<N;i++)//枚举8列
{
if(canPlace(m,i))
{
a[m]=i;
search(m+1);
}
a[m]=0;
}
}
}
int canPlace(int row ,int col)
{
int i;
for(i=0;i<row;i++) //皇后肯定不会同行，a[i]==col检查是否同列，abs(i-row)==abs(a[i]-col)检查是否同对角线，如果同对角线，行差和列差的绝对值应该相等。
{
if(a[i]==col||abs(i-row)==abs(a[i]-col))return 0;
}
return 1;
}
void printResult()
{
int i,j;
cout<<"No "<<cnt<<":"<<endl;
for(i=0;i<N;++i)
{
for(j=0;j<a[i];++j)
{
cout<<".";
}
cout<<"A";
j++;
for(;j<N;++j)
{
cout<<".";
}
cout<<endl;
}
cnt++;
}
下面给出4皇后回溯过程：
以及八皇后回溯过程（树太深，所以把时间设置的很快，大家看个热闹就行,感受一下计算机的力量)：
0-1背包问题：
问题描述：在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。
#include <iostream>
#define MAX 10
using namespace std;
int n;//物品个数
int c;//背包容量
int maxValue;//记录所选物品最大价值
int w[MAX];//物品重量数组
int v[MAX];//物品价值数组
int a[MAX];//a数组存放当前物品的选择情况
//a[i]=0表述不选第i个物品，a[i]=1表示选择第i个物品
int result[100];
int cnt;
void init();
void readData();
void search(int m);
void checkMax();
void printResult();
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
cin>>n>>c;
while(n!=0||c!=0)
{
init();
readData();
search(0);
result[cnt]=maxValue;
cnt++;
cin>>n>>c;
}
printResult();
return 0;
}
void init()
{
maxValue=0;
int i;
for(i=0;i<MAX;++i)
{
w[i]=v[i]=a[i]=0;
}
}
void readData()
{
int i;
for(i=0;i<n;i++)
{
cin>>w[i];
}
for(i=0;i<n;i++)
{
cin>>v[i];
}
}
void search(int m)
{
if(m>=n)
checkMax();
else
{
a[m]=0;//不要该物品
search(m+1);
a[m]=1;//要该物品
search(m+1);
}
}
void checkMax()
{
int weight=0,value=0;
int i;
for(i=0;i<n;i++)
{
if(a[i]==1)
{
weight+=w[i];
value+=v[i];
}
if(weight<=c)
{
if(value>maxValue)
maxValue=value;
}
}
}
void printResult()
{
int i;
for(i=0;i<cnt;++i)
{
cout<<result[i]<<endl;
}
}
堡垒问题：
如图城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。
#include <iostream>
#define MAX 5
int n;
int a[MAX*MAX];
int maxnum;
using namespace std;
void search(int m);
int canPlace(int m);
void checkMax();
/*run this program using the console pauser or add your own getch, system("pause") or input loop*/
int main(int argc, char** argv) {
while(cin>>n&&n!=0)
{
maxnum=0;
char c;
int i;
for(i=0;i<n*n;++i)
{
cin>>c;
if(c=='.')a[i]=1;
else if(c=='X')a[i]=0;
}
search(0);
cout<<maxnum<<endl;
}
return 0;
}
void search(int m)
{
if(m>=n*n)checkMax();
else
{
search(m+1);
if(canPlace(m)==1)
{
a[m]=2;//放堡垒
search(m+1);
a[m]=1;//把堡垒拿掉
}
}
}
int canPlace(int m)
{
if(a[m]==0)return 0;
int row,col;
row=m/n;
col=m%n;
int i,j;
for(i=0;i<m;++i)
{
if(a[i]==2)
{
if(i/n==row)//同行有堡垒
{
int flag=0;
for(j=i+1;j<m;++j)
{
if(a[j]==0)flag=1;
}
if(flag==0)return 0;
}
if(i%n==col)//同列有堡垒
{
int flag=0;
for(j=col;j<m;j+=n)
{
if(a[j]==0)flag=1;
}
if(flag==0)return 0;
}
}
}
return 1;
}
void checkMax()
{
int i;
int cnt=0;
for(i=0;i<n*n;++i)
{
if(a[i]==2)cnt++;
}
if(cnt>maxnum)maxnum=cnt;
}
素数环问题：
问题描述：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
#include <stdio.h>
#include <cmath>
void search(int);
void init();
void printresult();
int isprime(int);
void swap(int,int);
int a[21];
int main()
{
init();
search(2);
}
int isprime(int num)
{
int i,k;
k=sqrt(num);
for(i=2;i<=k;i++)
if(num%i==0)
return(0);
return(1);
}
void printresult()
{
int i;
for(i=1;i<=20;i++)
printf("%3d",a[i]);
printf("\n");
}
void search(int m)
{
int i;
if(m>20)
{
if(isprime(a[1]+a[20])) //判断首尾是否满足要求
printresult();
return;
}
else
{
for(i=m;i<=20;i++) //注意i是从m开始的而不是m+1
{
swap(m,i);
if(isprime(a[m-1]+a[m]))
search(m+1);
swap(m,i);
}
}
}
void swap(int m, int i)
{
int t;
t=a[m];
a[m]=a[i];
a[i]=t;
}
void init()
{
int i;
for(i=0;i<21;i++)
a[i]=i;
}
迷宫问题：
问题描述：给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。
输入：多个测例。输入的第一行是一个整数n，表示测例的个数。接下来是n个测例，每个测例占21行，第一行四个整数x1，y1，x2，y2是起止点的位置（坐标从零开始），（x1，y1）是起点，（x2，y2）是终点。下面20行每行20个字符，’.’表示空格；’X’表示墙。
输出：每个测例的输出占一行，输出Yes或No。
#include <iostream>
using namespace std;
#define N 20//20*20的迷宫
int k=20,t=20;//行数和列数
int a[N][N];//1代表墙，0代表可走，2代表已经走过
int n;//测例个数
int startRow,startCol;//入口坐标
int endRow,endCol;//出口坐标
int flag=0;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void readData();
void search(int row,int col);
int canPlace(int row,int col);
void printResult();
int main(int argc, char** argv) {
cin>>n;
while(n--)
{
flag=0;
readData();
search(startRow,startCol);
printResult();
}
return 0;
}
void readData()
{
cin>>startRow>>startCol;
cin>>endRow>>endCol;
int i,j;
char c;
for(i=0;i<k;i++)
{
for(j=0;j<t;j++)
{
cin>>c;
if(c=='.')a[i][j]=0;
else if(c=='X')a[i][j]=1;
}
}
}
void search(int row,int col)
{
if((row==endRow)&&(col==endCol))
{
flag=1;
return;
}
else
{
int r,c;
a[row][col]=2;//标记已经走过的位置
r=row,c=col-1;//向左走
if(canPlace(r,c))search(r,c);
r=row,c=col+1;//向右走
if(canPlace(r,c))search(r,c);
r=row-1,c=col;//向上走
if(canPlace(r,c))search(r,c);
r=row+1,c=col;//向下走
if(canPlace(r,c))search(r,c);
}
}
int canPlace(int row,int col)//判断是否可走
{
if(row>=0&&row<k&&col>=0&&col<t&&a[row][col]==0)return 1;//不越界且可以走
else
return 0;
}
void printResult()
{
if(flag==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
农场灌溉问题：
问题描述：一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图，编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。
#include <iostream>
using namespace std;
int m, n;
struct Maze
{
char ch; //方块类型
int visited; //访问标记
int left, right, up, down; //连通线
}maze[100][100];
int dir[4][2] = {{1,0}, {-1,0}, {0,-1}, {0,1}}; //上下左右四个方向
bool Place(int x, int y, int nx, int ny)
{
//未越界且未被访问过
if(nx>0 && nx<=m && ny>0 && ny<=n && !maze[nx][ny].visited)
{
//向左
if(nx==x && ny==y-1 && maze[x][y].left && maze[nx][ny].right)
return true;
//向下
if(nx==x+1 && ny==y && maze[x][y].down && maze[nx][ny].up)
return true;
//向右
if(nx==x && ny==y+1 && maze[x][y].right && maze[nx][ny].left)
return true;
//向上
if(nx==x-1 && ny==y && maze[x][y].up && maze[nx][ny].down)
return true;
}
return 0;
}
void dfs(int x, int y)
{
maze[x][y].visited = 1;
for(int i = 0; i < 4; i++)
{
int nx = x+dir[i][0];
int ny = y+dir[i][1];
//将所有可联通的区域全部标记
if(Place(x, y, nx, ny))
dfs(nx, ny);
}
}
int main()
{
while(cin >> m >> n && (m!=-1 || n!=-1))
{
int cnt = 0;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
cin >> maze[i][j].ch;
//初始化
maze[i][j].visited = 0;
maze[i][j].down = 0;
maze[i][j].up = 0;
maze[i][j].right = 0;
maze[i][j].left = 0;
switch(maze[i][j].ch)
{
case'A': maze[i][j].left=1;
maze[i][j].up=1;
break;
case'B': maze[i][j].right=1;
maze[i][j].up=1;
break;
case'C': maze[i][j].left=1;
maze[i][j].down=1;
break;
case'D': maze[i][j].right=1;
maze[i][j].down=1;
break;
case'E': maze[i][j].up=1;
maze[i][j].down=1;
break;
case'F': maze[i][j].left=1;
maze[i][j].right=1;
break;
case'G': maze[i][j].left=1;
maze[i][j].right=1;
maze[i][j].up=1;
break;
case'H': maze[i][j].left=1;
maze[i][j].up=1;
maze[i][j].down=1;
break;
case'I': maze[i][j].left=1;
maze[i][j].right=1;
maze[i][j].down=1;
break;
case'J': maze[i][j].right=1;
maze[i][j].up=1;
maze[i][j].down=1;
break;
case'K': maze[i][j].left=1;
maze[i][j].right=1;
maze[i][j].up=1;
maze[i][j].down=1;
break;
}
}
//连通区域个数
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
if(maze[i][j].visited == 0) // 未被访问过
{
dfs(i, j);
cnt ++;
}
}
cout << cnt << endl;
}
return 0;
}
