Chessboard and Queens

Chessboard and Queens
CSES medium

Place eight queens on a chessboard so that no two queens attack each other. Each square is either free (.) or reserved (*). Queens can be placed only on free squares, but reserved squares do not block attacks between queens.

Find the number of ways to place the queens.

Input:

  • Eight lines of eight characters: the chessboard.

Output:

  • One integer — the number of ways.

Example:

Input:

........
........
..*.....
........
........
.....**.
...*....
........

Output:

65
Solution

Two queens in the same row attack each other, so every row has exactly one queen. We use backtracking over the rows: in row row we try every column, place a queen if the square is allowed, continue with the next row, and then remove the queen.

A square is allowed if it is free and no queen placed before attacks it. We keep three arrays so that each check takes \(O(1)\):

  • column_used[col] — a queen is in column col;
  • diagonal1_used[row + col] — a queen is on the diagonal where row + col is constant;
  • diagonal2_used[row - col + 7] — a queen is on the other diagonal, where row - col is constant. We add \(7\) so that the index is not negative.

When all eight rows have a queen, we have found one way.

The backtracking removes every square that is attacked, so it checks far fewer than \(8^8\) placements and runs quickly.

#include <iostream>
#include <string>
using namespace std;

string board[8];
bool column_used[8];
bool diagonal1_used[15];  // squares with the same row + column
bool diagonal2_used[15];  // squares with the same row - column + 7
int ways = 0;

void backtracking(int row) {
    // a queen is placed in every row
    if (row == 8) {
        ways++;
        return;
    }

    for (int col = 0; col < 8; col++) {
        if (board[row][col] == '*' || column_used[col] ||
            diagonal1_used[row + col] || diagonal2_used[row - col + 7]) {
            continue;
        }

        column_used[col] = diagonal1_used[row + col] = diagonal2_used[row - col + 7] = true;
        backtracking(row + 1);
        column_used[col] = diagonal1_used[row + col] = diagonal2_used[row - col + 7] = false;  // undo the step
    }
}

int main() {
    for (int i = 0; i < 8; i++) {
        cin >> board[i];
    }

    backtracking(0);

    cout << ways << "\n";
}