Chessboard and Queens

Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

Example:

Input:  {{'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '*', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '*', '*', '.'}, {'.', '.', '.', '*', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}}
Output: 65

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const int n = 8;
vector<int> masks(n);

int backtrack(int r, int c, int ld, int rd)
{
    if (r == n)
        return 1;
    int res = 0, mask = masks[r] | c | ld | rd;
    for (int i = 0; i < n; i++)
    {
        if (mask >> i & 1)
            continue;
        res += backtrack(r + 1, c | (1 << i), (ld | (1 << i)) << 1, (rd | (1 << i)) >> 1);
    }
    return res;
}

int chessboardAndQueen(vector<vector<char>> &board)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            char c = board[i][j];

            if (c == '*')
                masks[i] |= (1 << j);
        }
    }
    return backtrack(0, 0, 0, 0);
}

int main()
{
    vector<vector<char>> board = {{'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '*', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '*', '*', '.'},
                                  {'.', '.', '.', '*', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'}};

    cout << chessboardAndQueen(board) << "\n";

    return 0;
}