Leetcode (Hard) : N-Queens II #52

Title: Understanding the N-Queens Problem: Logic, Implementation, and Insights

Introduction:

• The N-Queens problem is a classic puzzle where the task is to place N queens on an N x N chessboard without any of them attacking each other.
• This article will delve into the logic, implementation, intuition, and approach behind solving the N-Queens problem using a recursive algorithm.

Logic Behind the Solution:

• The solution revolves around a backtracking approach where we systematically explore all possible configurations of placing queens on the board.
• At each step, we place a queen in a valid position and move to the next row. If we reach a dead-end, we backtrack and try a different position.

Implementation Overview:

• The code provided offers a recursive solution to the N-Queens problem using C++.
• It consists of a totalNQueens function which initializes the chessboard and calls a helper function board to recursively explore and count the solutions.

Key Components of the Implementation:

1. board Function:This function recursively explores the chessboard row by row, placing queens in valid positions and backtracking when necessary.It counts the number of valid solutions found.
2. issafe Function:This function checks whether it's safe to place a queen in a given position by examining the rows, columns, and diagonals.It ensures no two queens can attack each other based on the rules of chess.
3. Backtracking:Backtracking is central to the solution. If a dead-end is reached (i.e., no valid position for the queen in the current row), the algorithm backtracks to the previous row and explores a different position.

Intuition Behind the Approach:

• The approach starts with an empty board and systematically tries all possible configurations of placing queens.
• By recursively exploring the board, it eliminates invalid placements using the issafe function, ensuring queens are not attacking each other.
• The backtracking mechanism allows the algorithm to efficiently explore all possible solutions without redundant computation.

Insights from the Code:

• The code elegantly demonstrates the application of backtracking to solve combinatorial problems like the N-Queens puzzle.
• It showcases the importance of efficiently pruning the search space to avoid unnecessary computation.
• The use of helper functions like issafe enhances code readability and modularity.

Conclusion:

• Solving the N-Queens problem requires a systematic approach that balances exploration and elimination of invalid configurations.
• Through the provided code, we gain insights into the application of backtracking and recursive techniques in solving complex combinatorial puzzles.
• Understanding this solution opens doors to tackling similar problems in various domains, from chessboard configurations to scheduling and optimization challenges.

class Solution {
    private: 
    int count = 0;
     void board( vector<vector<bool>>& chess,int row ,int Q )
    {
        if(Q==0){
            count++;
            return ;
        }
            for(int c = 0;c<chess.size();c++){
                if(issafe(chess,row,c,chess.size())){
                    chess[row][c] = true;
                    board(chess,row+1,Q-1);
                    chess[row][c]=false ;
                }
            }
    }
    bool issafe(vector<vector<bool>>& chess,int r,int c,int n){
        // upward check 
       for(int row = r-1;row>=0;row--){
           if(chess[row][c]){
               return false ;
           }
       }
       //left upward check
        int drow = r;
        int dcol = c;
       while(drow>=0 && dcol>=0){
           if(chess[drow][dcol]){
               return false ;
           }
           drow--;
           dcol--;
       }
       //right upward check
       int rdrow = r;
       int ldcol =  c;
       while(rdrow>=0&&ldcol<n){
           if(chess[rdrow][ldcol]){
               return false ;
           }
           rdrow--;
           ldcol ++;
       }
       return true ;
    }
public:
    int totalNQueens(int n) {
           vector<vector<bool>> chess(n, vector<bool>(n, false));;
       board(chess,0,n);
       return count;
    }
};