https://leetcode.cn/problems/n-queens/description/

<aside> 💡

首先分析冲突的情况：

1. 行冲突：x相同时冲突
2. 列冲突：y相同时冲突
3. 斜角冲突1：x + y相同时发生冲突
4. 斜角冲突2：x + (n - 1 - y)相同时发生冲突

• 以上情况1由于每层递归x都不同，所以不需要特别处理，其余三种情况各需要建立一个used数组进行对应

分析好以上冲突情况接下来套模板即可

</aside>

vector<bool> usedY;           // 对应情况2
vector<bool> usedCross1;      // 对应情况3
vector<bool> usedCross2;      // 对应情况4
vector<vector<string>> ans;
vector<vector<bool>> cur;

void backtracking(int x, int n) {
    if (x == n) {
        vector<string> ansString;
        for (auto v : cur) {
            string str = "";
            for (auto b : v) {
                str += b ? 'Q' : '.';
            }
            ansString.push_back(str);
        }
        ans.push_back(ansString);
    }

    // 固定x，遍历y
    for (int i = 0; i < n; ++i) {
        if (usedY[i] || usedCross1[x + i] || usedCross2[x + n - 1 - i]) {
            continue;
        }

				// 回溯
        usedY[i] = true;
        usedCross1[x + i] = true;
        usedCross2[x + n - 1 - i] = true;
        cur[x][i] = true;
        backtracking(x + 1, n);
        cur[x][i] = false;
        usedCross2[x + n - 1 - i] = false;
        usedCross1[x + i] = false;
        usedY[i] = false;
    }
}

vector<vector<string>> solveNQueens(int n) {
    usedY = vector<bool>(n, false);
    usedCross1 = vector<bool>(2 * n - 1, false);
    usedCross2 = vector<bool>(2 * n - 1, false);
    cur = vector<vector<bool>>(n, vector<bool>(n, false));

    backtracking(0, n);
    return ans;
}

一维used数组

本题虽然看上去是二维的，但每一行只能取一个数，还是能抽象为一维的序列（一维序列长度为N，每个元素的取值为[0, N)）

vector<string> toString(vector<vector<bool>> p) {
		vector<string> res;
		for (auto vec : p) {
				string s = "";
				for (bool elem : vec) {
						if (elem)
								s += 'Q';
						else
								s += '.';
				}
				res.push_back(s);
		}
		return res;
}

vector<vector<string>> ans;

void backtracking(int row, int& n, vector<vector<int>>& used, vector<vector<bool>>& plan) {
		if (row == n) {
				ans.push_back(toString(plan));
				return;
		}
	
		for (int j = 0; j < n; ++j) {
				// 不合法直接跳过
				if (used[row][j])
						continue;
				plan[row][j] = true;
				for (int i = 0; i < n; ++i) {
						// 标记同列所有位置
						++used[i][j];
						// 标记两条斜线上的所有位置
						if ((j - row + i) >= 0 && (j - row + i) < n)
								++used[i][j - (row - i)];
						if ((j + row - i) >= 0 && (j + row - i) < n)
								++used[i][j + (row - i)];
				}
				// 进入下一行的递归
				backtracking(row + 1, n, used, plan);
				for (int i = 0; i < n; ++i) {
						--used[i][j];
						if((j - row + i) >= 0 && (j - row + i) < n)
								--used[i][j - (row - i)];
						if ((j + row - i) >= 0 && (j + row - i) < n)
								--used[i][j + (row - i)];
				}
				plan[row][j] = false;
		}
}

vector<vector<string>> solveNQueens(int n) {
		vector<vector<bool>> plan(n, vector<bool>(n, false));
		vector<vector<int>> used(n, vector<int>(n, 0));
		backtracking(0, n, used, plan);
		return ans;
}