This is the first post of October 2023.

wikipedia

cses problem

solution:

Since no queens can share a row, there will be one queen per row and one queen per column in a solution. This makes for 8! queen arrangements.

The intuition behind backtracking here is that when you place a queen, say in the first column of the first row, you threaten squares in following rows. So, in a trial and error fashion, you can successively place queens row by row until there is no unthreatened square to place the next queen. By that point if you have placed all your queens (the last queen you placed was on the last row), then you found a solution. If you still have queens yet to be placed, then you undo queen places, or backtrack, to a point where you can try a new arrangement.

solution 1:

#include<iostream>
#include<array>

using namespace std;

#define REP(i,N) for (int i = 0;i < N;++i)
#define ll long long

const int N = 8;

void backtrack(int row, long long& cnt, array< array<int, N>, N>& A, const array<string, N>& board) {
	if (row == N) {
		++cnt;
		return;
	}

	REP(col, N) {
		if (board[row][col] == '.' && A[row][col] == 0) {

			for (int i = row + 1;i < N;++i) ++A[i][col];

			int h = col + 1;
			int v = row + 1;

			for (;h < N && v < N;++h,++v) ++A[v][h];

			h = col - 1;
			v = row + 1;

			for (;h >= 0 && v < N;--h,++v) ++A[v][h];


			backtrack(row + 1, cnt, A, board);


			for (int i = row + 1;i < N;++i) --A[i][col];

			h = col + 1;
			v = row + 1;

			for (;h < N && v < N;++h,++v) --A[v][h];

			h = col - 1;
			v = row + 1;

			for (;h >= 0 && v < N;--h,++v) --A[v][h];
		}
	}
}




int main() {
	array<string, N> board;

	REP(i, N) {
		cin >> board[i];
	}

	array< array<int, N>, N> A;

	REP(i, N) {
		REP(j, N) {
			A[i][j] = 0;
		}
	}

	stack<pair<int, int> > s;

	ll cnt = 0;

	backtrack(0, cnt, A, board);

	cout << cnt << endl;
}

You can also do this iteratively using a stack to perform the depth first search.

solution 2:

#include<iostream>
#include<array>
#include<stack>


using namespace std;

#define REP(i,N) for (int i = 0;i < N;++i)
#define ll long long

const int N = 8;

int main() {
	array<string, N> board;

	REP(i, N) {
		cin >> board[i];
	}

	array< array<int, N>, N> A;

	REP(i, N) {
		REP(j, N) {
			A[i][j] = 0;
		}
	}

	stack<pair<int, int> > s;

	ll cnt = 0;

	REP(col, N) {
		if (board[0][col] == '.') s.push({0, col});
	}


	while (!s.empty()) {
		pair<int, int> p = s.top();

		if (A[p.first][p.second]) {
			--A[p.first][p.second];

			for (int i = p.first + 1;i < N;++i) --A[i][p.second];

			int v = p.first + 1;
			int h = p.second + 1;

			for (;h < N && v < N;++h,++v) --A[v][h];

			v = p.first + 1;
			h = p.second - 1;

			for (;h >= 0 && v < N;--h,++v) --A[v][h];

			s.pop();
			continue;
		}

		if (p.first == N - 1) {
			++cnt;

			s.pop();
			continue;
		}



		++A[p.first][p.second];

		for (int i = p.first + 1;i < N;++i) ++A[i][p.second];

		int v = p.first + 1;
		int h = p.second + 1;

		for (;h < N && v < N;++h,++v) ++A[v][h];

		v = p.first + 1;
		h = p.second - 1;

		for (;h >= 0 && v < N;--h,++v) ++A[v][h];

		REP(col, N) {
			if (board[p.first + 1][col] == '.' && A[p.first + 1][col] == 0) {
				s.push({p.first + 1, col});
			}
		}
	}

	cout << cnt << endl;
}

I think this problem is pretty neat. It came up in my data structures course and my professor had a lot to say about it.

backtracking

solution 3: usaco guide The usaco guide details a better way to keep track of whether diagonals are threatened.