N皇后问题：回溯算法与剪枝优化

#include <bits/stdc++.h> using namespace std; int a, ans = 0; #define N 15 int fig[N]; char dp[N][N]; int posx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int posy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; bool INIT(int n) { memset(dp, ' ', sizeof(dp)); for (int i = 1; i <= n; i++) { dp[i][fig[i]] = 'Q'; } for (int i = 1; i <= n; i++) { for (int j = 0; j < 8; j++) { int x = i, y = fig[i]; while (x >= 1 && y >= 1 && x <= a && y <= a) { x += posx[j]; y += posy[j]; if (dp[x][y] == 'Q') { return false; } dp[x][y] = '1'; } } } return true; } void pos(int x, vector<vector> &res) { if (x > a && INIT(x)) { ans++; vector temp; for (int i = 1; i <= a; i++) { temp.push_back(fig[i]); } res.push_back(temp); return; } for (int i = 1; i <= a; i++) { if (!fig[i]) { fig[i] = x; if (INIT(x)) { pos(x + 1, res); } fig[i] = 0; } } return; } int main() { cin >> a; vector<vector> res; pos(1, res); sort(res.begin(), res.end()); for (int i = 0; i < min(3, int(res.size())); i++) { for (int j = 0; j < a; j++) { cout << res[i][j] << ' '; } cout << endl; } cout << res.size(); return 0; }