DataStructure_Algorithm_HandBook_PreForLeetCode

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

• 1 <= n <= 9

solution

solution

这是一个非常经典的问题，虽然是 hard，但是实际上不是很难。

对于任意一个皇后来说，它的横竖对角线是不能有皇后的，不然就会相互攻击。

我们在存储皇后位置的时候可以用大小为 n 的数组来存储，每个元素代表皇后在每一行的位置。最后我们对数组处理返回一定格式的结果。

所以我认为可以开三个 boolean 数组，来判断列方向和两个斜对角线方向是否存在重复的元素。

var solveNQueens = function(n) {
    let queens = []; // 用于存放皇后的列号
    let result = []; // 存放所有的解
    dfs(0, [], [], [], n, queens, result); // 开始深度优先搜索
    return result; // 返回所有解
};

// 将皇后的位置表示为字符串的形式
function formatQueens(queens, n) {
    let res = [];
    for (let i = 0; i < queens.length; i++) {
        let row = '';
        for (let j = 0; j < n; j++) {
            row += (j === queens[i] ? 'Q' : '.'); // 当 j 等于 queens[i] 时，表示放置皇后的位置
        }
        res.push(row);
    }
    return res;
}

// 深度优先搜索函数
function dfs(index, col, diag1, diag2, n, queens, result) {
    if (index === n) {
        // 将皇后的位置转换为字符串形式，并添加到结果中
        result.push(formatQueens(queens, n));
        return;
    }
    // 尝试将皇后放置在当前行的每一列中
    for (let i = 0; i < n; i++) {
        // 如果当前位置在列、左对角线或右对角线上已经有皇后，则跳过当前位置
        if (col[i] || diag1[index + i] || diag2[index - i + 9]) continue;
        // 标记当前位置
        col[i] = diag1[index + i] = diag2[index - i + 9] = true;
        queens[index] = i; // 将皇后放在当前位置
        dfs(index + 1, col, diag1, diag2, n, queens, result); // 继续搜索下一行
        // 回溯，取消当前位置的标记
        col[i] = diag1[index + i] = diag2[index - i + 9] = false;
    }
}