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

题目

n皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互攻击。

给定一个整数n,返回所有不同的n皇后问题的解决方案。

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

样例 对于4皇后问题存在两种解决的方案:

[".Q..", // Solution 1

 "...Q",

 "Q...",

 "..Q."],

["..Q.", // Solution 2

 "Q...",

 "...Q",

 ".Q.."]

分析

经典的问题,找出各个可行解。 首先我们判断怎样的位置是可行的,也就是不在同一行,不在同一列,且不在对角线上。 自然每个都在不同行上,所以我们可以把问题简化,在每一行找可以放进皇后的列。

一行一行的找遇到可行的列就加进去,当list的大小等于n的时候,就说明加满了,可以把结果存进去。

代码

class Solution {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    ArrayList<ArrayList<String>> solveNQueens(int n) {
        ArrayList<ArrayList<String>> results = new ArrayList<>();
        if (n <= 0) {
            return results;
        }
        
        search(results, new ArrayList<Integer>(), n);
        return results;
    }
    
    /*
     * results store all of the chessboards
     * cols store the column indices for each row
     */
    private void search(ArrayList<ArrayList<String>> results,
                        ArrayList<Integer> cols,
                        int n) {
        if (cols.size() == n) {
            results.add(drawChessboard(cols));
            return;
        }
        
        for (int colIndex = 0; colIndex < n; colIndex++) {
            if (!isValid(cols, colIndex)) {
                continue;
            }
            cols.add(colIndex);
            search(results, cols, n);
            cols.remove(cols.size() - 1);
        }
    }
    
    private ArrayList<String> drawChessboard(ArrayList<Integer> cols) {
        ArrayList<String> chessboard = new ArrayList<>();
        for (int i = 0; i < cols.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cols.size(); j++) {
                sb.append(j == cols.get(i) ? 'Q' : '.');
            }
            chessboard.add(sb.toString());
        }
        return chessboard;
    }
    
    private boolean isValid(ArrayList<Integer> cols, int column) {
        //cols存储了每一行Q所在的列
        int row = cols.size();
        
        //不能在同一列,且不能为对象线上的元素
        for (int rowIndex = 0; rowIndex < row; rowIndex++) {
            if (cols.get(rowIndex) == column) {
                return false;
            }
            if (Math.abs(rowIndex - row) == Math.abs(column - cols.get(rowIndex))) {
                return false;
            }
            
        }
        return true;
    }
};

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.26外存数据结构——B 树

No.26期 外存数据结构——B 树 小可:看来在磁盘上二叉搜索树对新来的数据插入树中支持得不好,那么究竟怎么解决这个问题呢? Mr. 王:有一个非常经典的...

35970
来自专栏Java爬坑系列

【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

  TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

9830
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

14610
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

10520
来自专栏大数据和云计算技术

算法基础7:平衡查找树概述

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第7篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

34590
来自专栏Golang语言社区

go语言mongdb管道使用(二)

原始代码: /* 重点项目实体机需求汇总 查询数据 */ func (this *IndexController) ProjectReqTotalData(...

34770
来自专栏木子昭的博客

明星程序员被Google挂掉的故事

首先要提一个软件Homebrew Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore ? ...

38550
来自专栏数据处理

leetcode222求完全二叉树节点个数

38040
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

9220
来自专栏从流域到海域

《数据结构》 顺序表常用操作代码集合

Ps:每段代码中,添加了署名Solo的是博主自己写的,其余来自课本或者老师。 //定义线性表的存储结构 #define MAXSIZE 100 typedef...

19550

扫码关注云+社区

领取腾讯云代金券