51.n-queens.md

n  皇后问题研究的是如何将 n  个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

每一种解法包含一个明确的  n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4

输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解释: 4 皇后问题存在两个不同的解法。

---

dfs + 回溯

算法思路

依次枚举每一行皇后的位置

• 每一列只有一个皇后 col[N]
• 每一条斜线只有一个皇后
  • 两种斜线 d[2*N -1], ud[2*N -1]
  • 斜率为 1 => d[x + y]
  • 斜率为-1 => ud[x - y + N]

代码实现

javascript 实现

var solveNQueens = function (n) {
  let board = new Array(n);
  for (let i = 0; i < n; i++) {
    board[i] = new Array(n).fill(".");
  }
  let ans = [];
  let col = new Array(n).fill(false); // 列
  let d = new Array(2 * n - 1).fill(false); // 斜率为1; d[x+y]
  let ud = new Array(2 * n - 1).fill(false); // 斜率为-1; d[x-y+n]
  function setPos(i, j, flag) {
    col[j] = flag;
    d[i + j] = flag;
    ud[i - j + n] = flag;
  }
  for (let i = 0; i < n; i++) {
    setPos(0, i, true);
    board[0][i] = "Q";
    dfs(board, 1);
    board[0][i] = ".";
    setPos(0, i, false); // 回溯
  }

  function dfs(board, i) {
    if (i == n) {
      let r = new Array(n);
      for (let i = 0; i < n; i++) {
        r[i] = board[i].join("");
      }

      ans.push(r);
      return;
    }
    for (let j = 0; j < n; j++) {
      if (!col[j] && !d[i + j] && !ud[i - j + n]) {
        setPos(i, j, true);
        board[i][j] = "Q";
        dfs(board, i + 1);
        setPos(i, j, false);
        board[i][j] = ".";
      }
    }
  }
  return ans;
};

cpp 实现

class Solution {
public:
    vector<vector<string>> res;
    vector<bool> col;
    vector<bool> d; // 正斜 x+ y
    vector<bool> ud; // 反斜 x - y + n
    vector<string> grid;
    vector<vector<string>> solveNQueens(int n) {
        col = vector<bool>(n, false);
        d = vector<bool>(2*n, false);
        ud = vector<bool>(2*n, false);
        grid = vector<string>(n, string(n, '.'));
        for (int i = 0; i< n; i++){
            if (grid[0][i] == '.'){
                col[i] = true;
                d[i] = true;
                ud[n-i] = true;
                grid[0][i] = 'Q';
                dfs(1, n);
                grid[0][i] = '.';
                col[i] = false;
                d[i] = false;
                ud[n-i] = false;
            }
        }
        return res;
    }

    void dfs(int row, int n){
        if (row == n){
            res.push_back(grid);
            return ;
        }
        for (int j = 0; j< n; j++){
            if (!col[j] && !d[row+j] && !ud[row - j + n]){
                col[j] = true;
                d[row + j] = true;
                ud[row -j + n] = true;
                grid[row][j] = 'Q';
                dfs(row+1, n);
                grid[row][j] = '.';
                col[j] = false;
                d[row + j] = false;
                ud[row -j + n] =false;
            }
        }
    }
};