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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment