• 主页
  • tags
  • 所有文章
所有文章 友链 关于我

  • 主页
  • tags
  • 所有文章

n皇后

2018-07-02
阅读量

文章导航

× 文章目录
  1. 1. n皇后问题-回溯法求解
    1. 1.1. 1.算法描述
    2. 1.2. 2.算法分析
      1. 1.2.1. 2.1 回溯法
      2. 1.2.2. 2.2 回溯法思路
      3. 1.2.3. 2.3 n皇后回溯求解
      4. 1.2.4. 2.4 时间复杂度
      5. 1.2.5. 2.5 空间复杂度
    3. 1.3. 3.代码实现
    4. 1.4. 4. 拓展,位运算+回溯法实现
      1. 1.4.1. 4.1 算法思路
      2. 1.4.2. 4.2代码实现
      3. 1.4.3. 4.3 算法分析
    5. 1.5. 5. 展望

n皇后问题-回溯法求解


1.算法描述

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

pic

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

2.算法分析

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

2.1 回溯法

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

2.2 回溯法思路

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

pic

pic

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

其实并不需要一个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])

我们可以提取比较方法:

1
2
3
4
5
6
7
8
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;
}

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

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

2.4 时间复杂度

递归n行, 每次循环 n 列, 比较 0~n-1 次。
n * n * (n - 1) / 2.
也就是 O(n^3). 哇塞,真暴力。

2.5 空间复杂度

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

3.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//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. 时间复杂度,遍历n行, 每行n列. O(n^2). emmm 快了不少。
  2. 空间复杂度,只用了几个变量, O(1).

5. 展望

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

  • 算法
  • 回溯
  • 算法

扫一扫,分享到微信

微信分享二维码
http简史-互联网浪潮中的重要角色
wordpress使用 Font Awesome 图标在 Firefox 中不显示问题
  1. 1. n皇后问题-回溯法求解
    1. 1.1. 1.算法描述
    2. 1.2. 2.算法分析
      1. 1.2.1. 2.1 回溯法
      2. 1.2.2. 2.2 回溯法思路
      3. 1.2.3. 2.3 n皇后回溯求解
      4. 1.2.4. 2.4 时间复杂度
      5. 1.2.5. 2.5 空间复杂度
    3. 1.3. 3.代码实现
    4. 1.4. 4. 拓展,位运算+回溯法实现
      1. 1.4.1. 4.1 算法思路
      2. 1.4.2. 4.2代码实现
      3. 1.4.3. 4.3 算法分析
    5. 1.5. 5. 展望
Like Issue Page
No Comment Yet
Login with GitHub
Styling with Markdown is supported
Powered by Gitment
© 2023 Pan yiwen
本站访客数人次
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链
  • 关于我

tag:

  • c语言
  • 算法
  • 协议
  • ajax
  • jsp
  • 九大内置对象
  • java并发
  • json
  • 回溯
  • 随笔
  • 面试题
  • tomcat

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 浅析tomcat原理

    2023-07-24

    #tomcat

  • java-AbstractQueuedSynchronizer(AQS)

    2018-11-17

    #java并发

  • 商汤java实习生面试题

    2018-09-09

    #面试题

  • servlet中destory方法的误解

    2018-07-09

    #随笔

  • ubuntu16.04科学上网

    2018-07-08

    #随笔

  • http简史-互联网浪潮中的重要角色

    2018-07-05

    #协议

  • n皇后

    2018-07-02

    #算法#回溯

  • wordpress使用 Font Awesome 图标在 Firefox 中不显示问题

    2018-06-26

  • 堆排序

    2018-05-26

    #算法

  • C语言_07 内存

    2018-03-20

    #c语言

  • C语言_06 指针

    2018-03-19

    #c语言

  • C语言_05 函数详解

    2018-02-11

    #c语言

  • C语言_04 三种程序结构 顺序, 选择(分支), 循环结构

    2018-02-06

    #c语言

  • C语言03_构造类型 数组, 结构体, 共用体, 枚举类型介绍

    2018-02-04

    #c语言

  • C语言02_基本数据类型

    2018-02-04

    #c语言

  • C语言01_介绍+helloworld

    2018-02-02

    #c语言

  • 笔记:jsp的九大内置对象和四大作用域

    2018-01-29

    #jsp#九大内置对象

  • 互联网协议-简单理解和介绍

    2018-01-27

    #协议

  • 笔记: AJAX

    2018-01-25

    #ajax

  • JavaScript笔记: JSON

    2018-01-25

    #json

  • Goodbye 2017

    2017-12-30

  • 我的blog
  • 我的github
Hello World!
2018