javascript递归回溯法解八皇后问题

JavaScript递归回溯法是一种常用于解决八皇后问题的算法。下面是具体的攻略：

什么是八皇后问题

八皇后问题是一种将8个皇后放置在8×8的棋盘上，使其不能互相攻击(皇后能够攻击在同一行、列、斜线的其他棋子)的问题。8皇后问题是一种NP完全问题，在计算机科学中占有重要地位。

解题思路

我们可以通过递归回溯的方法来解决八皇后问题，以下为具体思路：

• 在第一列放置第一个皇后。
• 在第二列开始，逐个列放置皇后，并判断该皇后是否与前面放置的任何一个皇后发生冲突。若发生冲突，则尝试在当前列放置下一个皇后。直至该列放置完毕，进入下一列。
• 重复上述步骤，直至所有的皇后均被放置。

递归回溯具体表现为：

• 在每一列开始遍历时，我们逐个行放置皇后，如果该皇后满足条件，我们将继续在下一列寻找合适位置放置皇后。
• 如果当前皇后无法放置，我们将回溯到上一列皇后，重新寻找合适位置，直至当前列可以放置皇后。

因为每个皇后只能与同一行、列、斜线上的另一个皇后发生冲突，所以我们需要用三个标记，分别用于记录当前行、列、斜线上是否有皇后，用于判断该皇后能否在当前位置放置。

代码实现

下面为JavaScript递归回溯法解八皇后问题的代码实现，其中，board为当前棋盘状态，row为当前行。代码中的hasConflict函数判断当前列所能放置的皇后是否与之前的皇后发生冲突。

var solveNQueens = function(n) {
    let board = [];
    let result = [];

    const backtrack = (row) => {
        if (row === n) {
            let solution = board.map(row => row.join(''));
            result.push(solution);
            return ;
        }

        for (let col = 0; col < n; col++) {
            if (hasConflict(board, row, col)) {
                continue;
            }

            board[row][col] = 1;
            backtrack(row + 1);
            board[row][col] = 0;
        }
    };

    const hasConflict = (board, row, col) => {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 1) {
                return true;
            }
        }

        let i = row - 1, j = col - 1;
        while (i >= 0 && j >= 0) {
            if (board[i][j] === 1) {
                return true;
            }
            i--;
            j--;
        }

        i = row - 1, j = col + 1;
        while (i >= 0 && j < n) {
            if (board[i][j] === 1) {
                return true;
            }
            i--;
            j++;
        }

        return false;
    };

    for (let i = 0; i < n; i++) {
        board.push(new Array(n).fill(0));
    }

    backtrack(0);

    return result;
};

示例说明

下面为两个示例，对于n=4和n=8的八皇后问题进行求解。

示例1：n=4

console.log(solveNQueens(4));

输出如下：

[
  [ ' . Q . .',  '. . . Q', 'Q . . .',  '. . Q .'],
  [ ' . . Q .',  'Q . . .', '. . . Q',  '. Q . .']
]

示例2：n=8

console.log(solveNQueens(8));

输出结果较多，在此略过。