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

相关文章

来自专栏java、Spring、技术分享

Netty ByteBuf源码解读

  Netty里的ByteBuf主要用于发送或接收消息。在JDK里有相似功能的类java.nio.ByteBuffer。由于JDK在设计ByteBuffer A...

731
来自专栏Redis源码学习系列

Redis源码学习之字典

在字典结构体中,包含了一组字典函数(dictType),通过封装的方法处理对应的操作,通常在字典初始化的时候对其进行配置。

720
来自专栏人工智能LeadAI

算法 | 排序算法图形化比较:快速排序、插入排序、选择排序、冒泡排序

用Objective-C实现几种基本的排序算法,并把排序的过程图形化显示。其实算法还是挺有趣的 。 选择排序 冒泡排序 插入排序 快速排序 01 选择排序 以升...

2907
来自专栏鸿的学习笔记

Python写的Python解释器(二)

玩具解释器 首先从一个玩具解释器开始,这个微型解释器只能做加法,而且值包含了三个指令,这三个指令是:

652
来自专栏TungHsu

这或许是对小白最友好的python入门了吧——4,列表

有些时候我们要用python处理一系列元素,这个时候我们可以把这一系列元素放到列表中。比如我们考试科目。 请不要在此处直接复制代码! 在python中,列表用...

3226
来自专栏desperate633

LintCode N皇后问题题目分析代码

每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。

612
来自专栏牛肉圆粉不加葱

Spark的位置优先: TaskSetManager 的有效 Locality Levels

在Spark Application Web UI的 Stages tag 上,我们可以看到这个的表格,描述的是某个 stage 的 tasks 的一些信息,其...

763
来自专栏kalifaの日々

Intel寄存器名称解释及用途,%eax%ebx等都是什么意思

参考资料:https://www.swansontec.com/sregisters.html x86家族的CPU都有8个通用寄存器,每一个寄存器的名字都是一...

5615
来自专栏技术栈大杂烩

Python: 链式赋值的坑

可能你会觉得我又要说什么变量赋值就是引用, 这么简单的知识就不讨论啦, 相信聪明的大家肯定都知道的, 我想讲的是链式赋值

591
来自专栏全沾开发(huā)

Generator的正确打开方式

994

扫码关注云+社区