51

51. N-Queens (Hard)

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.

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

Related Topics:
Backtracking

Similar Questions:

• N-Queens II (Hard)
• Grid Illumination (Hard)

Solution 1. Backtracking

// OJ: https://leetcode.com/problems/n-queens/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N^2)
class Solution {
    vector<vector<string>> ans;
    vector<string> B;
    vector<bool> col, hill, dale;
    int n;
    void dfs(int i) {
        if (i == n) {
            ans.push_back(B);
            return;
        }
        for (int j = 0; j < n; ++j) {
            int h = i + j, d = i + n - 1 - j;
            if (col[j] || hill[h] || dale[d]) continue;
            col[j] = hill[h] = dale[d] = true;
            B[i][j] = 'Q';
            dfs(i + 1);
            B[i][j] = '.';
            col[j] = hill[h] = dale[d] = false;
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        B.assign(n, string(n, '.'));
        col.assign(n, false);
        hill.assign(2 * n - 1, false);
        dale.assign(2 * n - 1, false);
        dfs(0);
        return ans;
    }
};