51 N-Queens

51. N-Queens

经典的题目……很有趣

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:

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

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

分析& 代码

参考该博客

首先说一下判断一个格子是不是能放，行列+两侧斜角比较非常笨重，可以用一个一维数组来表示int[] queuePos = new int[n]. 每一个格子表示这行上皇后的位置。

• 首先一个行只有一个皇后的位置，所以行自然没有重复的皇后

• 对于列，我们寻找到现在这一行之前的所有行，有没有皇后已经被放在同样的列上，如果没有就可以放

• 对于斜角，处在斜角上的格子有一个性质Math.abs(row - rowWeWannaPlace) == Math.abs(queuePos[row] - colWeWannaPlace). 所以也是检查一遍就行了

helper函数接受两个参数，一个queuePos的一维数组，一个当前行

伪代码：

如果当前行 == n

　　添加结果

不然对于每一列

　　如果这个位置能放

　　　　放皇后在这个位置上

　　　　递归helper(row + 1)

所以整体的代码是：

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    int[] queuePos = new int[n];
    Arrays.fill(queuePos, -1);
    queue(res, queuePos, 0);
    return res;
}

private boolean canPlace(int[] queuePos, int row, int col) {
    for(int i = 0; i < row; i++) {
        if(queuePos[i] == col) {
            return false;
        }
        if(Math.abs(i - row) == Math.abs(queuePos[i] - col)) {
            return false;
        }
    }
    return true;
}

private void queue(List<List<String>> res, int[] queuePos, int row) {
    int n = queuePos.length;
    if(row == n) {
        List<String> cur = generateResStr(queuePos);
        res.add(cur);
        return;
    }
    for(int i = 0; i < n; i++) {
        if(canPlace(queuePos, row, i)) {
            queuePos[row] = i;
            queue(res, queuePos, row + 1);
        }
    }
}

private List<String> generateResStr(int[] queuePos) {
    int n = queuePos.length;
    char[] row = new char[n];
    Arrays.fill(row, '.');
    List<String> res = new ArrayList<>();
    for(int i = 0; i < queuePos.length; i++) {
        row[queuePos[i]] = 'Q';
        res.add(new String(row));
        Arrays.fill(row, '.');
    }
    return res;
}

相当于遍历一棵树，树的层数是N，每层的节点数数是可以放的列，所以总复杂度是O(n!)