Interview Classic 150 Problems 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 and must place exactly one queen, then each backtracking step considers where to place the queen in the next row.
Note that when marking attacked areas, you should decrement by 1 instead of assigning -1. This is to avoid two queens attacking the same area.

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