DAY 91 - 51. N-Queens

Hey Folks!. Welcome to day 91 of the 100DaysOfCode Challenge. We shall be covering Today's daily leetcode problem today.

Question: 51. N-Queens

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 1:

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

Example 2:

Input: n = 1
Output: [["Q"]]

Intuition and Algorithm:

Rules:

• Let's lay the rules that we are required to solve this problem with.
• Every column should have one queen, every row should have one queen and no two queens should attack each other.
• For the attacking part we must first understand how it attacks: The queen can attack in any 8 directions of a board meaning diagonally, vertically or horizontally.

Intuition:

• We can't seem to find a trick, to get a good fast solution, so let's go with the most straight forward approach Trying all the possible ways.
• If we can try all possible ways , we should surely find an answer if it exists and we can then push that back into our answers array.
• But how do we approach if there could be multiple boards as our answers?.
• We use backtracking, if we can somehow visit back and change our choice of placing the queen at some position and trying the other position, we can for sure find out the answer.
• Using this intuition let's write out an approach for the answer.
• I am going to write the code first and then the approach so that we can understand how we wrote the approach.
• We also use hashing to store the queens in a diagonal so that we make sure we never place a queen again on that diagonal or row.

Code:

class Solution {
  public:
    void solve(int col, vector < string > & board, vector < vector < string >> & ans, vector < int > & leftrow, vector < int > & upperDiagonal, vector < int > & lowerDiagonal, int n) {
      if (col == n) {
        ans.push_back(board);
        return;
      }
      for (int row = 0; row < n; row++) {
        if (leftrow[row] == 0 && lowerDiagonal[row + col] == 0 && upperDiagonal[n - 1 + col - row] == 0) {
          board[row][col] = 'Q';
          leftrow[row] = 1;
          lowerDiagonal[row + col] = 1;
          upperDiagonal[n - 1 + col - row] = 1;
          solve(col + 1, board, ans, leftrow, upperDiagonal, lowerDiagonal, n);
          board[row][col] = '.';
          leftrow[row] = 0;
          lowerDiagonal[row + col] = 0;
          upperDiagonal[n - 1 + col - row] = 0;
        }
      }
    }

  public:
    vector < vector < string >> solveNQueens(int n) {
      vector < vector < string >> ans;
      vector < string > board(n);
      string s(n, '.');
      for (int i = 0; i < n; i++) {
        board[i] = s;
      }
      vector < int > leftrow(n, 0), upperDiagonal(2 * n - 1, 0), lowerDiagonal(2 * n - 1, 0);
      solve(0, board, ans, leftrow, upperDiagonal, lowerDiagonal, n);
      return ans;
    }
};

Approach:

• I define a function solve that takes several parameters: col (the current column being considered), board (the current state of the chessboard), ans (the vector to store valid solutions), leftrow, upperDiagonal, and lowerDiagonal (vectors to keep track of unavailable positions), and n (the size of the chessboard).
• The base case of the recursion is when we've placed all N queens successfully (i.e., col == n). In this case, we add the current state of the board to the ans vector as a valid solution and return.
• We iterate through each row in the current column (col). For each row, we check if it's a safe position to place a queen. We do this by ensuring that no other queen threatens it. We check the leftrow, upperDiagonal, and lowerDiagonal vectors to determine this.
• If it's a safe position, we mark it as 'Q' on the board and update the vectors accordingly. Then, we recursively move on to the next column (col + 1) and continue the search.
• After exploring all possibilities, we backtrack by resetting the board and vectors to their previous state to explore other combinations.
• In the solveNQueens function, I initialize the ans vector to store solutions, create the initial board configuration with all empty squares ('.'), and initialize the vectors for tracking unavailable positions.
• I call the solve function to start the backtracking process from the first column (col = 0). Once all valid solutions are found, they are stored in the ans vector.
• Finally, I return the ans vector containing all valid solutions to the N-Queens problem.

Complexity Analysis: