151 DSA Problem journey

151 DSA Problem journey

N Queens

Q23: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
Solution:
class Solution {
public:
vector<vector<string>> ret;
    bool is_valid(vector<string> &board, int row, int col){
        // check col
        for(int i=row;i>=0;--i)
            if(board[i][col] == 'Q') return false;
        // check left diagonal
        for(int i=row,j=col;i>=0&&j>=0;--i,--j)
            if(board[i][j] == 'Q') return false;
        //check right diagonal
        for(int i=row,j=col;i>=0&&j<board.size();--i,++j)
            if(board[i][j] == 'Q') return false;
        return true;
    }
    void dfs(vector<string> &board, int row){
        // exit condition
        if(row == board.size()){
            ret.push_back(board);
            return;
        }
        // iterate every possible position
        for(int i=0;i<board.size();++i){
            if(is_valid(board,row,i)){
                // make decision
                board[row][i] = 'Q';
                // next iteration
                dfs(board,row+1);
                // back-tracking
                board[row][i] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
         if(n <= 0) return {{}};
        vector<string> board(n,string(n,'.'));
        dfs(board,0);
        return ret;       
    }
};
Explantion:
>This C++ code is an implementation of the N-Queens problem using backtracking.
  The N-Queens problem is a classic chess problem where you need to place N
  queens on an N×N chessboard in such a way that no two queens threaten each
  other. The code uses a recursive approach to find all possible solutions.
Here's a breakdown of the code:
>is_valid Function:
 This function checks if it's valid to place a queen at a given position
 (row, col) on the chessboard. It checks for conflicts in the same column,
 left diagonal, and right diagonal.
>dfs Function:
 dfs stands for Depth-First Search, and it's a recursive function that 
 explores the possibilities of placing queens on the board.
 It starts from the first row and iterates through each column, checking if 
 placing a queen at that position is valid.
 If valid, it updates the board, moves to the next row (recursive call), and 
 continues the process.
 If not valid, it backtracks by undoing the queen placement and continues the 
 iteration.
>solveNQueens Function:
 Initializes an empty vector ret to store the solutions.
 Checks if n is less than or equal to 0, and if so, returns an empty vector 
 (no solution).
 Creates a chessboard represented by a vector of strings (board) initially 
 filled with dots (.).
 Calls the dfs function to find all solutions starting from the first row.
 Returns the vector containing all valid solutions.

In simple terms, the code explores all possible arrangements of queens on 
the chessboard, making sure that no two queens threaten each other. 
It uses backtracking to try different positions and efficiently find all 
solutions. The final result is a vector of vectors, where each inner vector 
represents a valid solution to the N-Queens problem.

Did you find this article valuable?

Support GAURAV YADAV by becoming a sponsor. Any amount is appreciated!