51-N皇后.md

51-N皇后

原题

结题 典型的使用回溯法来解决问题

const solveNQueens = function (n) {
    let board = Array.from({length: n}).map(() => Array.from({length: n}).fill('.'));
    let res = [];

    function backtrack(board, row) {
        if (row === n) {
            const stringsBoard = board.slice();
            for (let i = 0; i < n; i++) {
                stringsBoard[i] = stringsBoard[i].join('');
            }
            res.push(stringsBoard);

            // 奇怪，如果这里不设置 stringsBoard，而是直接 push board.slice() 结果里面没有 Q
            // 是不是哪里出了什么问题
            // res.push(board.slice());
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1);
                board[row][col] = '.';
            }
        }
    }

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

        // 检测列是否有皇后相冲突
        for (let i = 0; i < n; i++) {
            if (board[i][col] === 'Q') {
                return false;
            }
        }

        // 检测右上方是否有皇后相冲突
        for (
            let i = row - 1, j = col + 1;
            i >= 0 && j < n;
            i--, j++
        ) {
            if (board[i][j] === 'Q') {
                return false;
            }
        }

        // 检测左上方是否有皇后互相冲突
        for (
            let i = row - 1, j = col - 1;
            i >= 0 && j >= 0;
            i--, j--
        ) {
            if (board[i][j] === 'Q') {
                return false;
            }
        }

        return true;
    }

    backtrack(board, 0);
    return res;
}

let result = solveNQueens(4);
console.log(result);

这里的检测是否符合条件的判断函数isValid 有更好的方式，如

const isValid = function (row, col) {
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < n; j++) {
            if (
                board[i][j] === 'Q' // 发现了有皇后
                && (
                    j === col // 皇后与自己同列
                    || i + j === row + col // 皇后与自己右上对角线相同，如 (1,4) 与 (2,3)
                    || i - j === row - col // 皇后与自己左下对角线相同，如 (1,1) 与 (2, 2)
                )
            ) {
                return false;
            }
        }
    }
}

还可以优化 本题必须记录之前放置皇后的位置，才能结合约束条件去做剪枝。 我每次都调用 isValid 遍历一遍前面的格子，效率是不优的。 最好是用三个数组或 Set 去记录出现过皇后的列们、正对角线们、反对角线们，用空间换取时间。

const solveNQueens = n => {
    const board = Array.from({length: n}, () => Array.from({length: n}).fill('.'));

    const cols = new Set(); // 与当前皇后同列的位置
    const diag1 = new Set(); // 与当前皇后反对角线的位置
    const diag2 = new Set(); // 与当前皇后正对角线的位置
    const res = [];

    const backtrack = row => {
        if (row === n) {
            const stringsBoard = board.slice();
            for (let i = 0; i < n; i++) {
                stringsBoard[i] = stringsBoard[i].join('');
            }
            res.push(stringsBoard);
            return;
        }

        for (let col = 0; col < n; col++) {
            // 先检测一下，在与当前皇后同列以及对角线不存在的时候，就进行回溯
            if (
                !cols.has(col)
                && !diag1.has(row + col)
                && !diag2.has(row - col)
            ) {
                cols.add(col);
                diag1.add(row + col);
                diag2.add(row - col);

                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';

                cols.delete(col);
                diag1.delete(row + col);
                diag2.delete(row - col);
            }
        }
    }

    backtrack(0);
    return res;
}

let result = solveNQueens(4);
console.log(result);