n皇后问题

题目链接

题目描述

给定一个 n，要求在 n×n 格的棋盘上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

解题思路

我们从第一行到第n行放置，在放置每一行时，我们从第1列遍历到第n列，查看每一列是否放置过，且要判断斜对角线上是否放置过。思路比较简单。

我自己认为的一个难点就是，怎样判断斜对角线上是否放置过棋子。我们把棋盘看成一个个小方块，行我们从上到下编号为1…n，列我们从左到右编号为1…n，对于右下的对角线，我们不难发现，它的行列对应的值分别加 1， 那么行列的差值便是相等的。对于左下的对角线，我们观察可以发现，对应的行和列的数值是相反变化的，若行加1，则列减一，若列加1，则行减一。我们就可以通过判断，行+列的值和行-列的值是否出现过来判断左下和右下斜对角线是否放置过棋子。

代码如下

#include<bits/stdc++.h> using namespace std; int n; int a[11]; bool vis[11]; //标记列是否放置过 map<int,int>leftdown; //标记左下对角线是否放置过，放置过则对应的(行+列)置为1 map<int,int>rightdown; //标记右下对角线是否放置过，放置过则对应的行-列)置为1 int an; //用来记录可行方案的数量 void dfs(int x) { //x表示当前要放置棋子所在行为x if(x == n+1) {   an++; for(int i = 1; i<= n; i++) { printf("%d ",a[i]); } printf("n"); return; } for(int i = 1; i<= n; i++) { if(!vis[i] && leftdown[x-i]==0 && rightdown[x+i]==0) {    a[x] = i;    vis[i] = true; //标记列    leftdown[x-i] = 1; //左下对角线    rightdown[x+i] = 1; //右下对角线 dfs(x+1);    vis[i] = false;    leftdown[x-i] = 0;    rightdown[x+i] = 0; } } return; } int main() { scanf("%d",&n); memset(vis,false,sizeof(vis)); dfs(1); if(an == 0) printf("no solute!n"); }