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, to a point where you can try a new arrangement.

Here is my depth first search solution. I explicitly use a stack instead of recursion

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;
}

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