回溯法(一)——n皇后问题

问题描述

在一个n*n的棋盘上放置皇后,要求:一个皇后的同一行、同一列、同一条对角线上不允许出现其他皇后。请给出所有的放置方案。

算法思路

思路很简单,由于每行每列不能出现两个皇后,因此每行只能放一个皇后,那么第i行中皇后究竟应该放哪儿呢?我们可以从第i行第一列开始依次向后逐格判断,看看若放在当前位置是否会冲突,若不冲突,则继续考虑下一行,若冲突,则继续向后移动一格,再判断。 若i行所有的位置都不满足,则回溯,将i-1行皇后的位置往后移动,直到找到一个合理的位置,再继续从前往后寻找i行的位置。

示例

求解4皇后问题。

  1. 寻找第一行插入点:首先将Q放置a[0][0],无冲突;
  2. 寻找第二行插入点:a[1][0]、a[1][1]均冲突,a[1][2]可行;
  3. 寻找第三行插入点:发现所有格子都冲突,此时要发生回溯!
  1. 回到第二行,继续向后寻找插入点,找到a[1][3];
  2. 寻找第三行插入点:a[2][1]
  3. 寻找第四行插入点:发现所有位置都冲突,则回溯!
  1. 寻找第三行插入点:发现全都冲突,则继续回溯;
  2. 寻找第二行插入点:发现全都冲突,则继续回溯;
  3. 寻找第一行插入点:a[0][1];
  4. 寻找第二行插入点:a[1][3];
  5. 寻找第三行插入点:a[2][0];
  6. 寻找第四行插入点:a[3][2],此时找到一种方案。

数据结构

result数组:存储结果集。

  • 下标表示行号;
  • result[i]表示第i行皇后的列号。

代码实现

/**
 * N皇后问题
 * @param n 矩阵规模
 * @param i 行号
 * @param result 皇后的结果集(下标表示行号,值表示列号)
 */
void NQueen( int n, int i, int[] result ){
   for( int j=0; j<n; j++ ){
        if ( canPlace(n,i,j,result) ){
            result[i] = j;
            if ( i==n-1 ) {
                printResult(result);
            }
            else {
                NQueen(n,i+1,result);
            }
        }
   } 
}

/**
 * 判断第i行第j列能不能放
 * @param n 矩阵规模
 * @param i 行号
 * @param j 列号 
 * @param result 皇后的结果集(下标表示行号,值表示列号)
 */
private boolean canPlace(int n, int i, int j, int[] result){
    for( int z=0; z<i; z++ ){
        // 判断列号是否相同、是否在对角线上(长、宽是否相等)
        if ( j==result[z] || (i-z)==Math.abs(j-result[z]) )
            return false;
    }
    return true;
}

/**
 * 打印结果集
 * @param result 结果集
 */
private void printResult(int[] result){
    for( int i=0; i<result.length; i++ ){
        System.out.println("第"+i+"行,第"+result[i]+"列"); 
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python科学计算扩展库numpy中的广播运算

首先解答上一个文章Python扩展库numpy中的布尔运算中的问题,该题答案为[111, 33, 2],题中表达式的作用是按列表中元素转换为字符串后的长度降序排...

2768
来自专栏尾尾部落

希尔排序【Shellsort】

希尔排序是基于插入排序的以下两点性质而提出改进方法的: – 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 – 但插入排序一般来说...

713
来自专栏数据结构与算法

n皇后问题

1295 N皇后问题  时间限制: 2 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descripti...

2676
来自专栏有趣的Python

python分布式爬虫搜索引擎实战-2-深度优先和广度优先

深度优先和广度优先 目录: 网站的树结构 深度优先算法和实现 广度优先算法和实现 网站url树结构: 分层设计 子域名: bogbole.com - blo...

37811
来自专栏窗户

Scheme来实现八皇后问题(2)

  上一章讲了用1~n的排序来表示n皇后的解,然后通过枚举1~n所有的排列、判定谓词过滤所有排列得到最终的所有解。

963
来自专栏nnngu

Hibernate的继承映射

对象模型示例: ? 继承映射的实现方式有以下三种: (一)每棵类继承树一张表 (二)每个类一张表 (三)每个子类一张表 (一)每棵类继承树一张表 关系模型如下:...

2584
来自专栏尾尾部落

[剑指offer] 二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

732
来自专栏null的专栏

挑战数据结构和算法面试题——左旋转字符串

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题是常见的旋转字符串的问题,解决的方法是两步旋转的方法...

30310
来自专栏田云专栏

virtualdom diff算法实现分析

这两个月接触下vue ,花了两天时间了解了下vue的virtualdom实现,记录下学习心得。

3655
来自专栏图形学与OpenGL

实验4 类初步

 注:本次实验有可能会安排在校内http://acm.hpu.edu.cn/contest.php进行。

682

扫码关注云+社区