使用回溯法解决八皇后问题

回溯法的一般思想是：

 

为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

 

可以把回溯的探索看成是一种树的生长与遍历。在探索的过程中如果满足条件，就生成新的子节点，如果不满足，就退回到该节点的父结点。

 

在这里，我定义了一个简单的回溯树类，用defined成员函数来检查是否满足探索的条件，满足则用down生成该节点的子节点，否则，用up回退到它的父结点；最后用print打出搜索结果。这几个函数针对不同的问题需要不同的实现方式

                    

#ifndef _TREE
#define _TREE
const int N=8; //N Queen
class tree
   { int level;
     public:
       tree();
       int defined(int k);
       void up();
       void down(int k);
       void print();
       };
#endif

八皇后：在 8 * 8 格的棋盘上放置彼此不受攻击的 8 个皇后.按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，问有多少种放法？

这个问题就可以用回溯法来解决。

可以把第一个皇后的放法认为是回溯树的第一层，第二个皇后的放法第二层，。。。，这样就形成多棵回溯树。

大体思路是：当第一个皇后放在N个位置时，第二个从1到8依次检查是否和上层节点是否在一行，一列或一斜线上。如果是，则略过该位置，到下一层，继续这样做。

有很多问题都可以这样解：比如排列（得到所有可能的排列），组合，迷宫等等

附上源代码

tree.cpp

#include "tree.h"
#include "iostream.h"
int stack[N+1]={0};
int flag1[N+1]={0};
int flag2[2*N+1]={0};
int flag3[2*N+1]={0};
tree::tree()
  { level=1; }
int tree::defined(int k)
{
   if (k>N||k<1) return 0;
   else
     if (k>=level) return(!flag1[k]&&!flag3[k+level]&&!flag2[k-level]);
     else
     return(!flag1[k]&&!flag3[k+level]&&!flag2[level-k+N]);
}
void tree::down(int k)
{
    stack[level]=k;
    flag1[k]=1;
    if (k>=level) flag2[k-level]=1;
    else flag2[N+level-k]=1;
    flag3[k+level]=1;
    level++;
}
void tree::up()
{
   level--;
   flag1[stack[level]]=0;
   if (stack[level]>=level) flag2[stack[level]-level]=0;
   else flag2[level-stack[level]+N]=0;
    flag3[stack[level]+level]=0;
}
void tree::print()
{
   for (int i=1;i<level;i++) cout<<" "<<stack[i]<<" ";
   cout<<"\n";
}
     

eight.cpp

include "tree.h"
#include "iostream.h"
void main(void)
{int a[N+1];
 int l;
 int k=0;
 tree xtree;
 for (int i=1;i<=N;i++) a[i]=1;
 l=1;
 while (l)
 {
     if (xtree.defined(a[l]))
     {
         xtree.down(a[l]);l++;
     }
     else
     {
        a[l]++;
        if (a[l]>N)
         {
             xtree.up();a[l]=1;l--;a[l]++;
         }
     }
     if (l>N)
     {
         xtree.print();k++;
         xtree.up();l--;
     a[l]++;
     }
 }
cout<<"the total number is "<<k<<"\n";
}