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

相关文章

来自专栏决胜机器学习

《Redis设计与实现》读书笔记(三十五) ——Redis 二进制位数组及SWAR汉明重量算法

《Redis设计与实现》读书笔记(三十五) ——Redis 二进制位数组及SWAR汉明重量算法 (原创内容,转载请注明来源,谢谢) 一、基本概念 redis提供...

3614
来自专栏章鱼的慢慢技术路

排序算法的实现与比较

1668
来自专栏田云专栏

virtualdom diff算法实现分析

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

5515
来自专栏nnngu

Hibernate的继承映射

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

2644
来自专栏田云专栏

virtualdom diff算法实现分析

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

3016
来自专栏Python小屋

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

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

2878
来自专栏温安适的blog

union/find--不相交集合

3547
来自专栏令仔很忙

新手学HighCharts(二)----对比柱状图的动态加载

上一篇文章 新手学HighCharts(一)—-基本使用 中介绍了highCharts的基本使用,今天给大家介绍对比柱状图的使用,贴张图先:

831
来自专栏窗户

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

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

1213
来自专栏Android自学

Java中选择排序,冒泡排序等排序方法示例

1415

扫码关注云+社区