51. N-Queens

[huimeich]

The n-queens puzzle is the problem of placing n queens on an n×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.

For example, There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."],

["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

[huimeich]

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> q(n,string(n,'.'));
        vector<vector<string>> res;
        vector<bool> checkcol(n,false);
        vector<bool> check(4*n-2,false); // check index from right-to-left, then left-to-right
        locateQueens(q,res,0,checkcol,check);
        return res;
    }
    void locateQueens(vector<string>& q, vector<vector<string>>& res, int row, vector<bool>& checkcol, vector<bool>& check) {
        if (row == q.size()) {
            res.push_back(q);
            return;
        }
        for (int i = 0; i < q.size(); i++) {

            if (!checkcol[i] && !check[row+i] && !check[row-i+3*q.size()-2]) {
                checkcol[i] = true;
                check[row+i] = true;
                check[row-i+3*q.size()-2] = true;

                q[row][i] = 'Q';
                locateQueens(q, res, row+1, checkcol, check);
                q[row][i] = '.';

                checkcol[i] = false;
                check[row+i] = false;
                check[row-i+3*q.size()-2] = false;
            }
        }

    }
};

[huimeich]

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

class Solution {
public:
    int totalNQueens(int n) {
        int res = 0;
        vector<bool> checkcol(n,false);
        vector<bool> check(4*n-2,false);
        return totalNHelper(n,res,checkcol,check,0);
    }
    int totalNHelper(int n, int& res, vector<bool>& checkcol, vector<bool>& check, int row) {
        if (n == row) {
            res++;
            return res;
        }
        for (int i = 0; i < n; i++) {
            if (!checkcol[i] && !check[row+i] && !check[row-i+3*n-2]) {
                checkcol[i] = check[row+i] = check[row-i+3*n-2] = true;
                totalNHelper(n, res, checkcol, check, row+1);
                checkcol[i] = check[row+i] = check[row-i+3*n-2] = false;
            }
        }
        return res;
    }
};