32-伪代码详解

5.5.4　伪代码详解

（1）约束函数

在第t行放置第t个皇后时，第t个皇后与前t−1个已放置好的皇后不能在同一列或同一斜线。如果有一个成立，则第t个皇后不可以放置在该位置。

x[t]==x[j]表示第t个皇后和第j个皇后位置在同一列，t−j==fabs(x[t] −x[j]) 表示第t个皇后和第j个皇后位置在同一斜线。fabs是求绝对值函数，使用该函数要引入头文件#include。

bool Place(int t) //判断第t个皇后能否放置在第i个位置
{
     bool ok=true;
     for(int j=1;j<t;j++) //判断该位置的皇后是否与前面t-1个已经放置的皇后冲突
     {
         if(x[t]==x[j]||t-j==fabs(x[t]-x[j]))//判断列、对角线是否冲突
         {
               ok=false;
               break;
         }
     }
     return ok;
}

（2）按约束条件搜索求解

t表示当前扩展结点在第t层。如果t>n，表示已经到达叶子结点，记录最优值和最优解，返回。否则，分别判断n（i=1，…，n）个分支，x[t]=i；判断每个分支是否满足约束条件，如果满足则进入下一层Backtrack(t+1)；如果不满足则考查下一个分支（兄弟结点）。

void Backtrack(int t)
{
     if(t>n)  //如果当前位置为n,则表示已经找到了问题的一个解
     {
          countn++;
          for(int i=1; i<=n;i++) //打印选择的路径
            cout<<x[i]<<" ";
          cout<<endl;
          cout<<"----------"<<endl;
     }
     else
          for(int i=1;i<=n;i++) //分别判断n个分支,特别注意i不要定义为全局变量,否则递归调用有问题
          {
               x[t]=i;
               if(Place(t))
                    Backtrack(t+1); //如果不冲突的话进行下一行的搜索
          }
}