Interview Classic 150 Questions P52 N-Queens II

---

Timeline

Timeline

2025-11-30

init

---

Problem:

P52 NQueen II

https://leetcode.cn/problems/n-queens-ii/description/?envType=study-plan-v2&envId=top-interview-150

Classic backtracking problem, consider that each row can only and must place one queen, then each backtrack considers where to place the next row.
Note that when marking areas that can be attacked, use -1 instead of assigning -1. This is to avoid two queens being able to attack the same area simultaneously.

#include <vector>
using std::vector;

class Solution {
    private:
	int cnt;
	void backtrace(vector<vector<int> > &board, int row, int n)
	{
		if (row == n) {
			this->cnt++;
			return;
		}
		int i, j, k;
		for (j = 0; j < n; j++) { // column
			if (board[row][j] == 0) {
				for (i = row + 1; i < n; i++) { //set column of other row
					board[i][j] -= 1;
				}
				i = row + 1;
				k = j + 1;
				while (i < n && k < n) {
					board[i][k] -= 1;
					i++;
					k++;
				}
				i = row + 1;
				k = j - 1;
				while (i < n && k >= 0) {
					board[i][k] -= 1;
					i++;
					k--;
				}

				board[row][j] = 1;

				backtrace(board, row + 1, n);

				i = row + 1;
				k = j + 1;
				while (i < n && k < n) {
					board[i][k] += 1;
					i++;
					k++;
				}
				i = row + 1;
				k = j - 1;
				while (i < n && k >= 0) {
					board[i][k] += 1;
					i++;
					k--;
				}
				for (i = row + 1; i < n; i++) { //set column of other row
					board[i][j] += 1;
				}
				board[row][j] = 0;
			}
		}
	}

    public:
	int totalNQueens(int n)
	{
		this->cnt = 0;

		vector<vector<int> > board = vector(n, vector<int>(n, 0));
		backtrace(board, 0, n);
		return cnt;
	}
};

int main()
{
	Solution S;
	S.totalNQueens(4);
}