Leetcode Study Day 50

N-Queens II

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.
Example 2:

Input: n = 1
Output: 1
 

Constraints:

1 <= n <= 9

Solution

This is a backtracking problem. We can use a vector to store the position of the queens. The index of the vector represents the row and the value represents the column. We can use a function to check if the current position is valid. If it is valid, we can add it to the vector and call the function recursively. If the size of the vector is equal to n, we can add it to the result. Otherwise, we can remove the last element of the vector and try another position.

class Solution {
public:
    bool isSafe(vector <int> board, int row, int col, int n){
        for(int i = 0; i < row; i++){
            if (board[i] == col or abs(board[i] - col) == abs(i - row))
                return false; 
        }
        return true;
    }
    int solveNQueens(vector <int> board, int row, int n, int count){
        if (row == n){
            count ++;
            return count;
        }
        for (int col = 0; col < n; col++){
            if (isSafe(board, row, col, n)){
                board[row] = col;
                count = solveNQueens(board, row + 1, n, count);
                board[row] = - 1;
            }
        }
        return count;
    }
    int totalNQueens(int n) {
        vector <int> board (n, -1);
        int count = 0;
        return solveNQueens(board, 0, n, count);
    }
};

Variable explanation

In the N-Queens solution, the board array and the row and col variables in the recursion have specific meanings that are crucial to understanding how the algorithm works. Let’s clarify these:

1. The board Array:

   • The board array is a 1D vector of size n, where n is the size of the chessboard (n x n).
   • Each element of the board array represents a row on the chessboard.
   • The value stored at each index of the board array represents the column position where a queen is placed in that row.
   • For example, if board[2] = 3, it means that in row 2, a queen is placed in column 3.

2. The row Variable:

   • The row variable in the solveNQueens function represents the current row on the chessboard where you are trying to place a queen.
   • It is used to iterate through the rows of the chessboard, starting from 0 up to n-1.

3. The col Variable:

   • The col variable in the solveNQueens function represents the column position in the current row where you are attempting to place a queen.
   • For each row, you try placing a queen in each column (from 0 to n-1) and check if it’s a safe placement.

4. The isSafe Function:

   • This function checks whether placing a queen at the board[row] = col position is safe.
   • It checks for conflicts with queens in previous rows. There are two types of conflicts:
     • Column conflict: If any previous row (i) has a queen in the same column (board[i] == col).
     • Diagonal conflict: If any previous row (i) has a queen positioned diagonally. This is checked by the condition abs(board[i] - col) == abs(i - row).

5. Backtracking and Recursion:

   • The solveNQueens function uses recursion to try placing queens row by row.
   • If a safe position is found for a queen in the current row, it moves to the next row.
   • If no safe position is found in a row, it backtracks (i.e., it goes back to the previous row and tries a different column for the queen in that row).

In summary, the board array is a compact way to represent the positions of queens on the chessboard, and the row and col variables are used to navigate through the chessboard to place the queens safely. The algorithm explores all possible ways to place the queens, backtracking when necessary, until all solutions are found.