题目描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
n皇后问题是在n * n的棋盘上放置n个皇后，保证两两之间不会相互攻击。

国际象棋中的皇后比较牛逼，能攻击同一行、同一列、同一斜线上的棋子

八皇后问题的一个解

Given an integer n, return all distinct solutions to the n-queens puzzle.
给出一个整数n，返回所有n皇后的解。

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
每个解包含一种n皇后的放置方法，'Q'表示皇后，'.'表示空的格子。

Example:

Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

思路分析

解决n皇后问题本质上还是用DFS，还是用递归，遍历出棋盘的每一种可能，然后去掉那些不符合条件的结果。
简单粗暴的解决办法是直接在n * n的棋盘上每个格子都尝试放置皇后，然后在DFS过程中去掉那些不可能的路径。用一个n * n的数组记录当前皇后的摆放结果，将已经摆放的皇后的行、列、斜线都标记为不可放置。空间复杂度较高，为O(n * n)。
优化的办法是在于利用n皇后的特性，不一定真的要遍历出棋盘的每一种可能，也不用二维数组记录n * n的中间结果，因为对于一行来说，只要这行有了一个皇后，就不可能再有另一个皇后（反证法，如果有另一个皇后，两个就会冲突）；由于每行最多一个皇后，一共n行放置n个皇后，那么每行必须要有一个皇后。因此，棋盘的每行有且仅有一个皇后，那么就可以将中间变量的二维数组转化为每行皇后所在列数的一维数组。
四皇后的DFS树如图，每层负责处理行的一种情况。

四皇后的DFS树

代码实现

代码实现中涉及到了思路分析中没有讲的一些东西，例如DFS树到底后将一维数组转化为棋盘，例如DFS中为了节省空间重复利用中间变量，递归完后把中间变量row2Col调整回来。

public class Solution {

    /**
     * 9 / 9 test cases passed.
     *  Status: Accepted
     *  Runtime: 9 ms
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        List<Integer> temp = new ArrayList<>();
        List<List<String>> result = new ArrayList<>();
        recursiveSolveNQueens(temp, 0, n, result);
        return result;
    }

    private void recursiveSolveNQueens(List<Integer> row2Col, 
                      int curRow, int n, List<List<String>> result) {
        if (curRow == n) {
            List<String> rows = new ArrayList<>();
            for (int i = 0; i < row2Col.size(); i++) {
                char[] row = new char[n];
                for (int j = 0; j < n; j++) {
                    if (row2Col.get(i) == j) {
                        row[j] = 'Q';
                    } else {
                        row[j] = '.';
                    }
                }
                String sRow = new String(row);
                rows.add(sRow);
            }
            result.add(rows);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isValid(row2Col, curRow, i)) {
                row2Col.add(i);
                recursiveSolveNQueens(row2Col, curRow + 1, n, result);
                row2Col.remove(row2Col.size() - 1);
            }
        }
    }

    private boolean isValid(List<Integer> row2Col, int row, int col) {
        for (int i = 0; i < row2Col.size(); i++) {
            // 如果在同一列，或者通过行列差比较相等说明在同一斜线，则失败
            if (row2Col.get(i) == col 
                  || Math.abs(i - row) == Math.abs(row2Col.get(i) - col)) {
                return false;
            }
        }
        return true;
    }

}