51. N-Queens

📋 Đề Bài

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

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)Backtracking (Quay lui)Matrix (Ma trận)String (Chuỗi)

⏱️ Thời gian O(2ⁿ)

💾 Không gian O(n)

💻 Lời Giải

C++ 0051-n-queens.cpp

class Solution {
private:
    vector<string> nQueens;
    vector<vector<string>> ans;
    int row, col;
    
public:
    bool canGo(int i, int j) {
        for (int x = 0; x < i; ++x) {
            if (nQueens[x][j] == 'Q') {
                return false;
            }
        }
        for (int x = i - 1, y = j - 1; x >= 0 and y >= 0; --x, --y) {
            if (nQueens[x][y] == 'Q') {
                return false;
            }
        }
        for (int x = i - 1, y = j + 1; x >= 0 and y < col; --x, ++y) {
            if (nQueens[x][y] == 'Q') {
                return false;
            }
        }
        return true;
    }
    void backTracking(int i) {
        if (i == row) {
            ans.push_back(nQueens);
        }
        for (int j = 0; j < col; ++j) {
            if (canGo(i, j)) {
                nQueens[i][j] = 'Q';
                backTracking(i + 1);
                nQueens[i][j] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        nQueens.resize(n, string(n, '.'));
        row = col = n;
        backTracking(0);
        return ans;
    }
};