51.N皇后

链接：51.N皇后
难度：Hard
标签：数组、回溯
简介：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

题解 1 - javascript

• 编辑时间：2020-04-27
• 执行用时：72ms
• 内存消耗：36.1MB
• 编程语言：javascript
• 解法介绍：回溯算法，遍历后剪枝。

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  const cols = new Array(n);
  const res = [];
  queues(0);
  function queues(row) {
    if (row === n) {
      res.push(getRes());
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        cols[row] = col;
        queues(row + 1);
      }
    }
  }
  function isValid(row, col) {
    for (let i = 0; i < row; i++) {
      if (cols[i] === col) return false;
      if (row - i === Math.abs(cols[i] - col)) return false;
    }
    return true;
  }
  function getRes() {
    const res = [];
    for (let row = 0; row < n; row++) {
      let string = '';
      for (let col = 0; col < n; col++) {
        if (cols[row] === col) string += 'Q';
        else string += '.';
      }
      res.push(string);
    }
    return res;
  }
  return res;
};

题解 2 - typescript

• 编辑时间：2021-07-25
• 执行用时：108ms
• 内存消耗：44.7MB
• 编程语言：typescript
• 解法介绍：dfs+剪枝。

function solveNQueens(n: number): string[][] {
  const ans: string[][] = [];
  const colSet = new Set<number>();
  const lineSet = new Set<string>();
  const board = new Array(n).fill(0).map(_ => new Array(n).fill('.'));
  dfs();
  return ans;
  function getLine(row: number, col: number): [string, string] {
    return [`y=x+${n - 1 - row - col}${specStr}, ${specStr}y=-x+${n - 1 - row + col}`];
  }
  function dfs(row: number = 0) {
    if (row === n) {
      const newBoard: string[] = new Array(n).fill(0).map((_, row) =>
        new Array(n)
          .fill(0)
          .map((_, col) => board[row][col])
          .join('')
      );
      ans.push(newBoard);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (colSet.has(col)) continue;
      const [line1, line2] = getLine(row, col);
      if (lineSet.has(line1) || lineSet.has(line2)) continue;
      colSet.add(col);
      lineSet.add(line1);
      lineSet.add(line2);
      board[row][col] = 'Q';
      dfs(row + 1);
      board[row][col] = '.';
      colSet.delete(col);
      lineSet.delete(line1);
      lineSet.delete(line2);
    }
  }
}