回溯法(一)——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 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

译文 | 与TensorFlow的第一次接触 第三章:聚类

前一章节中介绍的线性回归是一种监督学习算法,我们使用数据与输出值(标签)来建立模型拟合它们。但是我们并不总是有已经打标签的数据,却仍然想去分析它们。这种情况下,...

3646
来自专栏编程

扣丁学堂浅谈Python视频教程之random模块详解

今天扣丁学堂小编给大家详细介绍一下关于Python视频教程之random模块详解,,首先用于生成伪随机数之所以称之为伪随机数,是因为真正意义上的随机数(或者随机...

20910
来自专栏智能算法

深度学习三人行(第2期)---- TensorFlow爱之再体验

上一期,我们一起学习了TensorFlow的基础知识,以及其在线性回归上的初体验,该期我们继续学习TensorFlow方面的相关知识。学习的路上,我们多多交流,...

32310
来自专栏灯塔大数据

每周学点大数据 | No.39单词共现矩阵计

No.39期 单词共现矩阵计算 Mr. 王:这里还有一个很典型的例子——单词共现矩阵计算。 这个例子是计算文本集合中词的共现矩阵。我们设 M 是一个 N×N...

3865
来自专栏mwangblog

开始使用Octave

1334
来自专栏深度学习与计算机视觉

TensorFlow 组合训练数据(batching)

在之前的文章中我们提到了TensorFlow TensorFlow 队列与多线程的应用以及TensorFlow TFRecord数据集的生成与显示,通过这些操作...

2927
来自专栏超智能体

YJango:TensorFlow中层API Datasets+TFRecord的数据导入

2. 对接性:TensorFlow中也加入了高级API (Estimator、Experiment,Dataset)帮助建立网络,和Keras等库不一样的是:这...

43222
来自专栏CreateAMind

keras doc 9 预处理等

用以生成一个batch的图像数据,支持实时数据提升。训练时该函数会无限生成数据,直到达到规定的epoch次数为止。

752
来自专栏数据小魔方

左手用R右手Python系列——因子变量与分类重编码

今天这篇介绍数据类型中因子变量的运用在R语言和Python中的实现。 因子变量是数据结构中用于描述分类事物的一类重要变量。其在现实生活中对应着大量具有实际意义的...

3055
来自专栏IMWeb前端团队

word-break 和 word-wrap 的区别

本文主要要介绍的是 CSS 中 word-break: break-all 和 word-wrap: break-word 的区别,虽然这两个属性都有使用过,但...

1917

扫描关注云+社区