51. N-Queens

原题：51. N-Queens

思考

这道题主要用到 回溯 的思想解题。

假设第i行Q占据图中的位置，则她的四条攻击路径如图所示。

容易得出：路径3（撇）经过的单元格都有y+x=c1，路径4（捺）经过的单元格都有y-x=c2，其中c1/c2是一个常数。

• 由于我们逐行扫描，所以路径1必然不会冲突。
• 对于路径2，使用col标记已经占用的列
• 对于路径3，使用xySum标记已经被占用的撇
• 对于路径4，使用xyDiff标记已经占用的捺

最后回溯即可。

source code

// Runtime: 88 ms, faster than 33.33% of JavaScript online submissions for N-Queens.
// Memory Usage: 39.3 MB, less than 100.00% of JavaScript online submissions for N-Queens.
var solveNQueens = function (n) {
  //左上角为原点，横向为x，纵向为y
  const col = {}; //列
  const xySum = {}; //撇，y+x=c
  const xyDiff = {}; //捺，y-x=c
  const result = [];

  const helper = function (y, tmp) {
    //x为第几行
    //tmp为中间结果，值为第y行皇后的位置
    if (y >= n) {
      //到底
      result.push(tmp);
      return;
    }
    for (let x = 0; x < n; x++) {
      //对每一列假设求解
      if (!col[x] && !xySum[x + y] && !xyDiff[y - x]) {
        col[x] = 1;
        xySum[x + y] = 1;
        xyDiff[y - x] = 1;

        helper(y + 1, [...tmp, x]);

        //恢复现场
        col[x] = 0;
        xySum[x + y] = 0;
        xyDiff[y - x] = 0;
      }
    }
  };

  helper(0, []);

  return result.map((v) =>
    v.map((qi) => {
      const arr = new Array(n).fill(".");
      arr[qi] = "Q";
      return arr.join("");
    })
  );
};

test cases

test("test1", () => {
  expect(solveNQueens(4).sort()).toEqual(
    [
      [
        ".Q..", // Solution 1
        "...Q",
        "Q...",
        "..Q.",
      ],

      [
        "..Q.", // Solution 2
        "Q...",
        "...Q",
        ".Q..",
      ],
    ].sort()
  );
});