N皇后问题
N皇后问题是指将 N 个皇后放在 N×N 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
十分经典的作业题,高斯在这个问题上也没有得出正确的解(八皇后问题高斯给出的答案是76种,而正确答案是92种)
这个题目可以这么看,每一行只能放一个皇后,同时保证这一个皇后所对应的列,正反对角线都不能再放皇后。所以我们对于皇后的位置就有了判断的标准。
这里穿插一个小技巧:将棋盘看做一个坐标系,那么对角线上的点会满足x+y=b 或 x-y=b,这样一来,就有x-y为负数的情况,而棋盘的坐标系无负数象限,所以在后面加上一个N,即x-y+N=b,这样就可以避免负数情况。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100;
char board[N][N];
bool col[N], dg[N], udg[N]; //因为每行只放一个皇后,所以要保证其每列,正反对角线上都不能有皇后
int n;
int sum = 0;
void search(int cnt)
{
if (cnt == n) //n个皇后全部排好
{
sum++;
cout << endl;
for (int i = 0; i < n; i++) puts(board[i]);
puts("");
cout << "-------------------------------" << endl;
return;
}
for (int i = 0; i < n; i++)
{
if (!col[i] && !dg[cnt + i] && !udg[n - cnt + i])
{
board[cnt][i] = 'Q'; //放置皇后,将其所对应的位置上全部标记,不能再放
col[i] = dg[cnt + i] = udg[n - cnt + i] = true;
search(cnt + 1);
col[i] = dg[cnt + i] = udg[n - cnt + i] = false; //恢复现场,回溯
board[cnt][i] = '.';
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = '.';
search(0);
if (sum > 0)
cout << "一共有" << sum << "种方法" << endl;
else cout << "无解" << endl;
return 0;
}
0 条评论