试探回溯

排列问题的所有可能解，但是不同的是尽可能多的，尽可能早的排除一些解。 试探：从一个最初的选择出发，逐步增加解的长度，直到试探完所有的可能性。 回溯：试探中发现与目标不同，则这条路上接下来所有的解被排除，然后回到上一步，继续试探下一个可能的组合。

八皇后问题详解

问题

在国际象棋中，皇后的势力范围（横，竖，斜），怎样在n*n的棋盘上放置n个皇后，使她们不能相互攻击

思路

先将皇后放置在（0,0）的位置，尝试将皇后分配至每行，试探不同的列，如果发现冲突，则试探下一个列，如果下一行皇后无处可放，则回溯到上一行，然后将此行的皇后后移一列，直到放在第一行上的皇后走完所有的列（即试探完了所有的可能性）

代码实现

struct Queen { int x,y;//坐标 Queen(int xx=0,int yy=0):x(xx),y(yy){}; bool operator==(Queen const& q)const { return (x==q.x)||(y==q.y)||(x+y==q.x+q.y)||(x-y==q.x-q.y); //冲突（行，列，对角线） } bool operator!=(Queen const& q)const { return !(*this==q); } //不冲突 } void place(int N) //N行N列皇后有N个 { stack<Queen> solu; //存放部分解 Queen q(0,0); //第一个皇后从原点出发 int nsolu=0; //可行解的个数 while((q.x>0)!!(q.y<N)) //循环条件，皇后移动没有到第一行N（其实已经出界）列 { if(solu.size()>=N||q.y>=N) //行/列越界，回溯 { q=solu.pop(); //回溯到上一行 q.y++; //试探下一个 } else { while(N>q.y&&solu.find(q)>=0) //还有列可以试探&&此位置与已有皇后冲突 { q.y++; //下一个列 } if(N>q.y) //有可以放皇后的列 { solu.pop(q); if(solu.size()>=N) //试探出此解可行 nsolu++; //解的个数加一 q.x++;q.y=0; //进入下一行的第一个位置 } } } }