51-N皇后

LeetCode 51. N-Queens

LeetCode-51

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

method: 回溯

判断逻辑：

• 判断同一列是否有
• 判断45度斜线是否有
• 判断135度斜线是否有

递归的深度就是棋盘的行数n
如果这个点可以放就放，然后递归处理下一层

vector<vector<string>> res;
bool isValue(vector<string>& board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}
void traversal(vector<string>& board, int row, int n) {
    if (row == n) {
        res.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValue(board, row, col, n)) {
            board[row][col] = 'Q';      // 放皇后
            traversal(board, row + 1, n);   // 递归处理下一层
            board[row][col] = '.';      // 回溯取消皇后
        }
    }
}
vector<vector<string>> solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));    // 一个string就是一层
    traversal(board, 0, n);
    return res;
}

用空间换时间

vector<bool> cols;  // 列
vector<bool> diag1; // 45度对角线
vector<bool> diag2; // 135度对角线
vector<vector<string>> res;
void traversal(vector<string>& board, int row, int n) {
    if (row == n) {
        res.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        int d1 = row + col;
        int d2 = row - col + n - 1;
        if (cols[col] || diag1[d1] || diag2[d2]) continue;
        cols[col] = 1;
        diag1[d1] = 1;
        diag2[d2] = 1;
        board[row][col] = 'Q';
        traversal(board, row + 1, n);
        board[row][col] = '.';
        cols[col] = 0;
        diag1[d1] = 0;
        diag2[d2] = 0;
    }
}
vector<vector<string>> solveNQueens(int n) {
    cols.resize(n);
    diag1.resize(2 * n);
    diag2.resize(2 * n);
    vector<string> board(n, string(n, '.'));
    traversal(board, 0, n);
    return res;
}

---

LeetCode 52. N-Queens II

LeetCode-52

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 the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

method: 回溯

由元素所在行row和列col计算所在的对角线

• 45度对角线：row + col
• 135度对角线：row - col + n - 1

int res;
vector<bool> cols;  // 列
vector<bool> diag1; // 45度对角线
vector<bool> diag2; // 135度对角线
void traversal(int row, int n) {
    if (row == n) {
        res++;
        return;
    }
    for (int col = 0; col < n; col++) {
        int d1 = row + col;         // 45度对角线
        int d2 = row - col + n - 1; // 135度对角线
        if (cols[col] || diag1[d1] || diag2[d2]) continue;
        cols[col] = 1;
        diag1[d1] = 1;
        diag2[d2] = 1;
        traversal(row + 1, n);  // 递归下一层
        cols[col] = 0;
        diag1[d1] = 0;
        diag2[d2] = 0;
    }
}
int totalNQueens(int n) {
    cols.resize(n);
    diag1.resize(2 * n);    // 对角线的数量是2n-1
    diag2.resize(2 * n);
    traversal(0, n);
    return res;
}