N-Queens Problem Solution

N-Queens Problem Solution: 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:

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

N-Queens Problem Solution

Problem Solution In Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.n = n
        res = []
        self.backtrack(0,[],res)
        return res
    
    def backtrack(self, row, pList, res):
        if row == self.n:
            res.append(['.'*x+'Q'+'.'*(self.n-1-x) for x in pList])
            return
        if row > self.n:
            return
        for col in range(self.n):
            if self.check(col, row, pList):
                self.backtrack(row+1, pList+[col], res)
                
    def check(self, col, row, pList):
        for r in range(row):
            if pList[r] == col or row-r == abs(col-pList[r]):
                return False
        return True

Problem Solution In Java

class Solution {
 
    StringBuilder line = new StringBuilder();

    void f(List<List<String>> result, int[] s, int i, int n, boolean x[]) {
        if (i == n) {
            List<String> solution = new ArrayList<>();
            for (int k = 0; k < n; k++) {
                StringBuilder line0 = new StringBuilder(line);
                line0.insert(s[k], 'Q');
                solution.add(line0.toString());
            }
            result.add(solution);
        } else {
            for (int j = 0; j < n; j++) {
                int p1 = j - i + 2 * n - 1;
                int p2 = i + j + 3 * n - 2;
                if (!x[j] && !x[p1] && !x[p2]) {
                    boolean[] x0 = new boolean[x.length]; System.arraycopy(x, 0, x0, 0, x.length);
                    int[] s0 = new int[n]; System.arraycopy(s, 0, s0, 0, n);
                    x0[j] = x0[p1] = x0[p2] = true;
                    s0[i] = j;
                    f(result, s0, i + 1, n, x0);
                }
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        if(n==2 || n==3) return new ArrayList<>();
        for (int i = 0; i < n - 1; i++) line.append('.');
        List<List<String>> result = new ArrayList<>();
        f(result, new int[n], 0, n, new boolean[5 * n - 2]);
        return result;
    }
    
}

Problem Solution In C++

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> rt;
        vector<int> vc, vs(2*n-1,-1), vd(2*n-1,-1);
        for( int i=0; i<n; i++) vc.push_back(i);
        
        dfs( 0, vc, vs, vd, rt);
        
        return rt; 
    }
    
    void dfs( int j, vector<int>& vc, vector<int>& vs, vector<int>& vd, vector<vector<string>>& rt){
        if(j==vc.size())    pushQ( vc, rt);
        
        for( int i=j, t; i<vc.size(); i++){
            t=vc[i];
            vc[i]=vc[j];
            vc[j]=t;
            
            if(vs[vc[j]+j]==-1&&vd[vc[j]-j+vc.size()-1]==-1){
                vs[vc[j]+j]=1;
                vd[vc[j]-j+vc.size()-1]=1;
                
                dfs( j+1, vc, vs, vd, rt);

                vs[vc[j]+j]=-1;
                vd[vc[j]-j+vc.size()-1]=-1;
            }
            
            t=vc[i];
            vc[i]=vc[j];
            vc[j]=t;            
        }
        
        return ;
    }
    
    void pushQ( vector<int>& vc, vector<vector<string>>& rt){
        string s(vc.size(),'.');
        vector<string> vs(vc.size(),s);
        
        for( int i=0; i<vc.size(); i++) vs[i][vc[i]]='Q';
        
        rt.push_back(vs);
        
        return ;
    }
    
};

Problem Solution In C

typedef struct Queens {     
    char ***queens[1000];
    int count;
}Queens, *pQueens;


void nqueen (int row, int n, int *res, pQueens Q);
void save (int n, int *res, pQueens Q);
bool check (int row, int *res);


char*** solveNQueens(int n, int* returnSize) {
    if (n < 1 || returnSize == NULL)
        return NULL;
    pQueens Q = (pQueens) calloc(1, sizeof(Queens));
    int res[n];
    memset(res, 0, sizeof(res));
    nqueen (0, n, &res, Q);
    *returnSize = Q->count;
    return Q->queens;
}


void nqueen (int row, int n, int *res, pQueens Q) {
    if (row == n){
        save(n, res, Q);
        return;
    }
    for (int i = 0; i < n; ++i) {
        res[row] = i;
        if (check(row, res))
            nqueen(row + 1, n, res, Q);
    }
}

void save (int n, int *res, pQueens Q) {
    char **matrix = (char **) malloc(n * sizeof(char *));
    for (int i = 0; i < n; ++i) {
        matrix[i] = (char *) calloc((n + 1), sizeof(char));
        int j;
        for (j = 0; j < n; ++j) {
            matrix[i][j] = '.';
        }
        matrix[i][res[i]] = 'Q';
    }
    *(Q->queens + Q->count) = matrix;
    ++Q->count; 
    return;
}


bool check (int row, int *res) {
    for (int i = 0; i < row; ++i) {
        if (res[row] == res[i] || abs(res[row] - res[i]) == (row - i))
            return false; 
    }
    return true;
}