n皇后 回溯

回溯思想

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 我个人的理解就是不断地去尝试，满足条件便一直深入下去尝试，直到出现不满足的情况时或则得到答案时便返回上一层

n皇后

n皇后问题就是在n*n的棋盘上放置n个皇后，使得n个皇后两两之间不能进行攻击（即每两个皇后不可以在同一行，同一列，在同一斜线上（斜率为1的斜线））

问题解析

n皇后问题就是依次将每个皇后放在棋盘的某个位置，每次放置时要判断这个位置是否可以放置皇后，判断方式就是对已放置的皇后的坐标进行对比并且验证将要放置的皇后是否满足互不攻击的条件。

代码

int a[100] 下标代表行，存储着列号

代码语言：javascript复制

bool pd(int row,int col)
{
   for(int i=0;i<row;i  )
   {
       if(a[i]==col||abs(i-row)==abs(col-a[i]))    //判断该位置是否可以放置皇后
           return false;
   }
   return true;
}

在回溯的过程我使用的是递归的方式

代码语言：javascript复制

void getResult(int row)
{
    if(row==n)      //说明前n-1行都放置了皇后，就确定了一个方案
    {
         all  ;
    }
    else{
      for(int i=0;i<n;i  )       
      {
          if(pd(row,i))          //判断成功说明该位置可以放置皇后，并且进行下一行的判断

          {
              a[row]=i;
              getResult(row 1);
          }
      }
    }
}

大致的思想就是一行一行进行放置皇后，这样可以保证每个皇后都不在同一个行，这样在判断放置的位置是否合理时，只需判断是否与已放置的皇后是否在一列或者在一斜线。这样一行行的判断下去，直到所有的可能都被遍历完，就得到了结果。

递归 搜索 算法 存储 遍历

0 人点赞