Chessboard and Queens
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 columncol;diagonal1_used[row + col]— a queen is on the diagonal whererow + colis constant;diagonal2_used[row - col + 7]— a queen is on the other diagonal, whererow - colis 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";
}