n皇后问题-回溯法求解[通俗易懂]

n皇后问题-回溯法求解[通俗易懂]n皇后问题-回溯法求解1.算法描述在n×n格的国际象棋上摆放n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。n皇后是由八皇后问题演变而来的。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

n皇后问题-回溯法求解

1.算法描述

在n×n格的国际象棋上摆放n个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

img1

n皇后是由八皇后问题演变而来的。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。

2.算法分析

随着计算机的普及和发展,以前人们无法解决的问题,计算机可以简单计算出来。而且思路十分清晰,那就是暴力求解,遍历所有情况,然后计算出解的个数。

2.1 回溯法

按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法

2.2 回溯法思路

用数组模拟棋盘,从第一行开始,依次选择位置, 如果当前位置满足条件,则向下选位置, 如果不满足条件,那么当前位置后移一位。

img2

img3

最后一个不满足,回溯到上一行, 选下个位置,继续试探。

其实并不需要一个n*n的数组,我们只需要一个n长度的数组来存位置。

表示方式: arr[i] = k; 表示: 第i行的第k个位置放一个皇后。这样一个arr[n]的数组就可以表示一个可行解, 由于回溯,我们就可以求所有解。

2.3 n皇后回溯求解

因为八皇后不能在同行,同列, 同斜线。

  1. 每一行放一个皇后,就解决了不在同行的问题。
  2. 在第i行的时候,遍历n列,试探位置。和之前所有行放的位置进行比较。
  3. 比较列:当前列col 不等于 之前 所有列。 即col != arr[i].
  4. 比较斜线, 因为不再同一斜率为1或者-1的斜线。(row – i) / (col – arr[i]) != 1 或 -1
    可以取巧用绝对值函数: abs(row-i) != abs(col-arr[i])

我们可以提取比较方法:

public boolean comp(int row, int col){ 
      //当前行和列
    for (int i = 0; i < row; i++)  //比较之前row -1 列。
    { 
   
      if(col == arr[i] || abs(row-i) != abs(col-arr[i]))  //如果在同一列,同一斜线
          return false;
    }
    return true;
}

比较函数写完后, 就只剩下回溯过程, 我们采用递归的方式回溯,比较好理解。

//当前层 row
for (int i = 0; i < n; i++){ 
   
  if(comp(row, i)){ 
   
    arr[row] = i;
    //同样方式遍历下一层。 row + 1
  }
}

2.4 时间复杂度

最坏的情况: 每一行有n种情况,有n行, 所以时间复杂度为O(n^n)。
但是由于回溯法会提前判断并抛弃一些情况,使得时间复杂度并没有想象中那么高。但是说是O(n!)也不太对,具体怎么算,暂时也不太清楚。(之前想当然了,此处有修正,多谢评论中的提醒。)

2.5 空间复杂度

因为只用了arr[n]的数组,也就是O(n).

3.代码实现

public class NQueen { 
   
    private int n;
    private long count;
    private int[] arr;
// private int nn;

    public NQueen(int n){ 
   
        this.n = n;
  // nn = (1 << n) - 1;
        count = 0;
        arr = new int[n];
    }


    /** * row col i arr[i] * @param row * @param col * @return */
    public boolean Check(int row, int col){ 
   
        for(int i = 0; i < row; i++){ 
   
            if(col == arr[i] || Math.abs(row - i) == Math.abs(col - arr[i])) //在同一列或者在同一斜线。一定不在同一行
                return false;
        }
        return true;
    }

    public void FindNQueen(int k) { 
   
        if (k == n) { 
      //求出一种解, count+1
            count++;
            return;
        }

        for (int i = 0; i < n; i++) { 
   
            if (Check(k, i)) { 
      //检查是否满足条件
                arr[k] = i;      //记录
                FindNQueen(k + 1);   //递归查找
            }
        }

    }

    public static void main(String args[]){ 
   
        NQueen nQueen = new NQueen(13);
        nQueen.FindNQueen(0);
        System.out.println(nQueen.count);
    }

}

4. 拓展,位运算+回溯法实现

虽然计算机算的很快,但是上诉方法实在是太慢了, java就更慢了。如何网上就有大佬给出了位运算求解。精妙的不行。

4.1 算法思路

我们不再用数组来存储位置,而是用一个整数k,k一开始等于0. 不是普通的0.我们也不比较了,直接用两个整数l和r 记录在斜线在当前行不能走的位置。如果是n皇后, 那么用一个整数
nn = 1 << n 表示结束。

举个栗子吧: 8皇后问题。

初始化 那么我们就变成二进制的角度来看这些初始化的数据吧。

k = 00000000, l = 00000000, r = 00000000; nn = 11111111; (<- 8个0 8个1)

  1. k: 每个位置i的0表示没有皇后,1表示在第i个位置放了一个皇后。
  2. l: 0表示之前所有的列中放的皇后斜率为-1的线上没有涉及这个位置, 1 表示涉及到了,不能放皇后
  3. r: 同l, 所有斜率为1的线涉及的位置。

l和r的实现:

比如k = 00110001. 我要在第4个为位置放一个皇后, 假设l和r都没有涉及这个位置。

那么这个位置x= 00001000.

  1. k = (k & x) = 00111001.
  2. l = (l & x) << 1.
  3. r = (r & x) >> 1.

假设l = 00110001, r = 00100010.下一行,l表示斜率为-1不能放的位置, 那么第i+1行 l 中所有为1的数字都需要向左移动一位,r需要向右移动一位。 l & x 也就是加上当前选中的位置一起移动。

4.2代码实现

   //k 当前已走了多少个位置。 l 左斜线不能走的位置, r 右斜线不能走的位置。
   public void FindNQueen(int k, int l, int r){ 
   
       if(k == nn){ 
   
           count++;
           return;
       }

       int z = nn & (~(k | l | r));  //能走的位置, 和nn取并可以去掉前面多余的1
       while(z != 0){ 
   
           int index = z & (~z+1);   //最右边的一个1, 即要放皇后的位置。
           z -= index;   //去掉这个位置。

           FindNQueen(k | index, (l|index)<<1, (r|index)>>1);   //查找下一个。
       }


   }

4.3 算法分析

  1. 时间复杂度,应该同上分析一致,去掉但是少了检查的for循环,应该是O(n!)
  2. 空间复杂度,只用了几个变量, O(1).

5. 展望

其实还有其他方式和更快的方式求解,比如位运算+多线程, 还有号称时间复杂度为O(1),利用数学公式的构造法求解。扶我起来,我要继续学。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187371.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • AD18 net class设置「建议收藏」

    AD18 net class设置「建议收藏」今天使用AD18画原理图,想把天线相关网络归属为一类以便方便进行PCB规则设置。在原理图中设置NetClass,可省去在PCB阶段再重新分配NetClass。点击设置→指示→参数设置,调取参数设置符合。将参数设置符合放在要设定的网络上,查看参数设置符合的属性在label中可以重新命名原理图上显示的名称,在Class中点击add,即可新增NetClass,并需要对其进行命名。再将符合复…

  • 什么是PV,UV。

    什么是PV,UV。

  • SAP Fiori refreshSecurityToken

    SAP Fiori refreshSecurityTokenCreatedbyWang,Jerry,lastmodifiedonMar26,2015要获取更多Jerry的原创文章,请关注公众号”汪子熙”:

    2022年10月27日
  • 3D机房效果图制作|创建步骤过程分步简述[通俗易懂]

    3D机房效果图制作|创建步骤过程分步简述[通俗易懂]三维机房效果图创建过程步骤,制作教程原创文章发布,多年实战经验简述:A:客户提供机房布置方案规划图之后,先沟通好,例如角落里是七氟丙烷柜,右侧是精密空调,后边是UPS配电柜,冷通道是双排还是单排的,这个要搞清楚,不然后边修改就麻烦了。B:思路理清之后就可以整理CAD图纸了,删除辅助线,标注尺寸,地面和墙面填充,删除多余线条,然后复制好整理的图纸。机房整体鸟瞰角度效果图案例C:打开三维软件,用脚本粘贴刚才的图纸,一键归零合并冻结。D:确定好角度,这个需要反复测试几十次,看了网上很多的.

  • 线程理论知识

    一、什么是线程线程:顾名思义,就是一条流水线工作的过程,一条流水线必须属于一个车间,一个车间的工作过程是一个进程所以,进程只是用来把资源集中到一起(进程只是一个资源单位,或者说资源集合),而线程才

  • struts2拦截器不起作用「建议收藏」

    struts2拦截器不起作用「建议收藏」为什么拦截器不起作用

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号