题解 | #N皇后问题#

回溯的基本框架：

// 怎么做？
function Nqueen(n) {
    let res = 0;
    
    const backtrack = function (?) {
        // 终止条件是啥
        if (?) {
            res++;
            return;
        }
        // 怎么遍历
        for (?) {
            // 做什么操作？
            ?

            backtrack(board, row + 1);

            // 取消操作
            ？
        }
    };

    backtrack(?);

    return res;
}

module.exports = {
    Nqueen,
};

解题步骤：

• 问1：思考N皇后问题怎么做？它是在做什么？

答：在 N * N 的棋盘上放置棋子 Q ，Q有个特性就是它会攻击所在行所在列以及斜对角上的棋子。现在要求你在棋盘上放上最多的Q，问你有几种放法。

所以，你需要一个 N * N 的 棋盘 board，记录你的放法。

• 问2：你会怎么放？

答：第一行先放一个Q，下一行遍历所有的格子，在一个合适的格子上放上Q，然后再到下一行。直到棋盘的最后一行放上了Q，就完成了一种方法。

所以，backtrack的入参是:

const backtrack = function(board, row) {}

终止条件：

if(row === board.length) {
  res++;
  return;
}

每行遍历所有列，在合适的格子上放上Q：

for(let c = 0; c < board[row].length; c++) {
  // 判断当前格子是否合适放置,不合适就不放了
  if(!isvalid(board, row, col)) continue;
  // 做的操作 
  board[row][c] = 'Q';
  
  backtrack(board, row + 1);
  
  // 取消操作
  board[row][c] = '#';
}

• 问3：怎么判断格子是否合适：

答：当前列有Q不能再放；当前格子左上角有Q不能再放（不只是左上角的一个格子，是整个左上角斜对角线）；当前格子右上角有Q不能再放。

伪代码如下：

function isValid(board, row, col) {
  for(let i = 0; i < board.length; i++) {
   if(board[i][col] === 'Q') return false;
  }
  
  for(i = row - 1, j = col - 1; i && j >= 0 ; i--, j--)  {
   if(board[i][j]==='Q') return false;
  }
  
  for(i = row-1, j = col + 1; i && j < bCols; i--,j++) {
   if(board[i][j] === 'Q') return false;
  }
  
  return ture;
}

最终结果：

function Nqueen(n) {
    const board = Array.from(Array(n), () => Array(n).fill("#"));

    let res = 0;

    const backtrack = function (board, row) {
        // 终止条件是啥
        if (row === board.length) {
            res++;
            return;
        }
        // 怎么遍历
        for (let c = 0; c < board[0].length; c++) {
            if (!isValid(board, row, c)) continue;
            // 做什么操作？
            board[row][c] = "Q";

            backtrack(board, row + 1);

            // 取消操作
            board[row][c] = "#";
        }
    };

    backtrack(board, 0);

    return res;
}

function isValid(board, row, col) {
    const n = board.length;

    // 同一列有Q不行
    for (let i = 0; i < n; i++) {
        if (board[i][col] === "Q") {
            return false;
        }
    }

    // 左上角有Q不行
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] === "Q") {
            return false;
        }
    }

    // 右上角有Q不行
    for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if(board[i][j] === 'Q') {
            return false;
        }
    }

    return true;
}

module.exports = {
    Nqueen,
};