N皇后问题12 · N-Queens

［抄题］：

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

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

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

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

[

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

"...Q",

"Q...",

"..Q."],

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

"Q...",

"...Q",

".Q.."]

]

［思维问题］：

看不懂特殊情况：主要是要区别x y

［一句话思路］：

DFS去掉特殊情况后画图

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

search函数可以是空类型，不返回search函数，返回其中的results即可。cols链表是后续函数的参数，此处需要新建链表。
如果辅助链表cols满了，需要在结果数组中添加画图，之后直接返回results。cols是数组，画成图才是链表
drawCheesboard方法中，需要新建一个chessboard数组，作为最后返回的结果。 sb.append(j == cols.get(i) ? 'Q' : '.');表示j如果到达x有值处就打印Q
判断函数要有默认的return true 此函数判断的是cols,column是否有效，因此全部行通过后返回true

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

search函数用的DFS回溯是关键

［复杂度］：Time complexity: O(分支的深度次方) Space complexity: O(分支*深度)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

DFS：找出全部方法

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

Nqueen第二版，改参数不行暂时算了吧

[代码风格] ：

规律：返回值和函数类型是相同的

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

     */

    List<List<String>> solveNQueens(int n) {

        List<List<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(List<List<String>> results,

                        List<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 List<String> drawChessboard(List<Integer> cols) {

        List<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(List<Integer> cols, int column) {

        int row = cols.size();

        for (int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {

            if (cols.get(rowIndex) == column) {

                return false;

            }

            if (rowIndex + cols.get(rowIndex) == row + column) {

                return false;

            }

            if (rowIndex - cols.get(rowIndex) == row - column) {

                return false;

            }

        }

        return true;

    }

}

巴特西

N皇后问题12 · N-Queens

最新文章

热门文章