N皇后问题

 

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define MAX 20//最大20个皇后
int n ;//实际皇后个数
int sum ;//答案个数
vector<vector<int>> attack(MAX, vector<int>(MAX, 0));//标记攻击位置
vector<vector<char>>queen(MAX,vector<char>(MAX,'.'));//存放皇后的位置void put_queen(int x, int  y)
{int dx[] = { -1,-1,-1,0,1,1,1,0 };int dy[] = { -1,0,1,1,1,0,-1,-1 };attack[x][y] = 1;//将皇后位置标记为1for (int i = 1; i < attack.size(); i++){for (int j = 0; j < 8; j++)//8个方向{int xx = x + i * dx[j];int yy = y + i * dy[j];if (xx >= 0 && xx < attack.size() && yy >= 0 && yy < attack.size()){attack[xx][yy] = 1;//将皇后攻击到的地方标记为1}}}
}void Backtrack(int k)//第k行，数量是n个
{if (k > n - 1)//找到一组解{sum = sum + 1;cout << endl;for (int a = 0; a < n; a++){for (int b = 0; b < n; b++){cout << queen[a][b] << " ";}cout << endl;}cout << endl;return;}for (int i = 0; i < n; i++){if (attack[k][i] == 0)//判断当前第k行i列是否可以放皇后{vector<vector<int>>tmp = attack;queen[k][i] = 'Q';put_queen(k, i);//更新皇后攻击范围Backtrack(k + 1);queen[k][i] = '.';//回溯attack = tmp;//回溯}}
}int main()
{cout << "请输入皇后数量：" << endl;cin >> n;sum= 0;Backtrack(0);cout << "答案个数：" << sum<<endl;return 0;
}