回溯法——以皇后摆放问题为例

回溯法——以皇后摆放问题为例

回溯法(98条消息) (新手向)递归与回溯算法学习(一)——n位逐位整除数_TripleGold.的博客-CSDN博客

算法思想:

(通用的解题法)穷举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现不满足求解条件时就回退,尝试其他路径

回溯法的解题步骤:

  1. 针对给定问题确定问题的解空间树,至少包含问题的一个解或者最优解

  2. 确定结点的扩展搜索规则

  3. 以深度优先搜索解空间树,并采取剪枝手段。

框架:

 

  1. 非递归回溯框架

     int x[n]    //x存放解向量,全局变量
     void backtrack(int n){
      int i = 1; //根节点的层次为1
      while(i>=1){ //尚未回溯到头
      if(ExistSubNode(t)){ //当前结点存在子节点
      for(j=下界;j<=上界;j++){ //对于子集树,j从0到1循环
      x[i]取一个可能的值;
      if(constraint(i)&&bound(i)){ //x[i]满足约束条件和界限函数
      if(x是一个可行的解)
      输出x;
      else i++; //进入下一个层次
      }
      }
      }
      else i--; //不存在子节点,返回上一层
      }
     }
  2. 递归回溯框架

     int x[n]
     void backtrack(int i){
      if(i>n) //搜索叶子结点,输出一个可行解
      输出结果;
      else{
      for(j=下界;j<=上界;j++){ //用j枚举i所有可能的路径
      x[i] = j; //产生一个可能的解分量
      ...
      if(constraint(i)&&bound(i))
      backtrack(i+1) //满足约束条件继续下一层
      }
        }
     }
     result = []
     def backtrack(路径, 选择列表):
        if 满足结束条件:
            result.add(路径)
            return
             
        for 选择 in 选择列表:
            做选择
            backtrack(路径, 选择列表)
            撤销选择
     

例题:皇后摆放问题:

题目描述

国际象棋的棋盘可以看做是一个 8 × 8 的矩阵,上面每一个格子仅能放一枚棋子,现在给出一个 8 × 8 的由 0 和 1 组成的矩阵,代表象棋棋盘,1 代表当前位置放置了一个皇后,0 则代表什么都没有放,上面有 n(n 为小于 8 的正整数)个位置已经放上了皇后棋子(相互之间不冲突,合理摆放),现在另外给你 8 - n 个皇后,问你有多少合理的摆法。

输入描述

一个 8 × 8 的由 0 和 1 组成的矩阵。

输出描述

一个整数,为摆放的种类数。

样例输入

 1 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0

样例输出

 4

问题分析

判断某位置是否可以摆放皇后

假设i行j列处已摆放上一个皇后,则下面摆放的皇后(x,y)则不能在i行和j列(即x!=i && y!=j),且不能在已摆放皇后对角线上(即abs(x-i)!=abs(y-j))。

搜索算法

通过初始化,我们可以知道哪些位置有了皇后。通过一个路径数组path[9]来记录(1~8)行哪一列有皇后。还未探索到的行,数组赋值0。

用回溯法,从第一行开始往下,测试1~8列是否能够摆放,能则继续往下探索,不能则返回上一层。

AC代码:

 #include<iostream>
 #include<cstring>
 #include<cmath>
 using namespace std;
 
 int path[9];
 //判断某位置是否可以摆放皇后
 bool pd(int x){
     for(int i=1;i<=8;i++){
         if(path[i]!=0 &&i!=x && (path[i]==path[x] || abs(i-x)==abs(path[i]-path[x]))){
             return false;
        }
    }
     return true;
 }
 //搜索算法
 void backtrace(int x,int &sum){
     if(x==9){
         sum++;
         return;
    }
     if(!path[x]){
         for(int i=1;i<=8;i++){
 
             path[x] = i;
             if(pd(x)) backtrace(x+1,sum);
             path[x] = 0;
        }
    }
     else backtrace(x+1,sum);
 }
 
 int main(){
     int x,sum = 0;
     memset(path,0,sizeof(path));
     for(int i=1;i<9;i++){
         for(int j=1;j<9;j++){
             cin>>x;
             if(x==1){
                 path[i]=j;
            }
        }
    }
     backtrace(1,sum);
     cout<<sum<<endl;
     return 0;
 }
 

原文地址:https://www.cnblogs.com/chanxe/archive/2022/05/18/16284950.html