Problem Statement

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 the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Problem Link

N-Queens II - LeetCode

Code

class Solution {
public:
    int totalNQueens(int n) {
        
        vector<vector<char>> board(n,vector<char>(n,'.'));
        int res = 0;
        solve(0,n,res,board);
        
        return res;
        
    }
    
    void solve(int col,int n,int &res,vector<vector<char>> &board)
    {
        
        if(col==n)
        {
            res++;
            return;
        }
        
        for(int row=0;row<n;row++)
        {
            if(isSafe(row,col,n,board))
            {
                board[row][col] = 'Q';
                solve(col+1,n,res,board);
                board[row][col] = '.';
            }
        }
    }
    
    bool isSafe(int row,int col,int n,vector<vector<char>> &board)
    {
        int i = row;
        int j = col;
        
        while(j>=0)
        {
            if(board[i][j]=='Q')
                return false;
            j--;
        }
        
        i = row;
        j = col;
        
        while(i<n && j>=0)
        {
            if(board[i][j]=='Q')
                return false;
            j--;
            i++;
        }
        
        i = row;
        j = col;
        
        while(i>=0 && j>=0)
        {
            if(board[i][j]=='Q')
                return false;
            j--;
            i--;
        }
        
        return true;
        
        
            
    }
};