首页 > 代码库 > n 皇后问题
n 皇后问题
问题描述：
八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。
问题分析：
显然，每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1≤ i≤ n且1≤ xi≤ n，即第n个皇后放在第i行第xi列上。
由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:
xi≠ xj;
若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj;
综合两种情况，由于两个皇后不能位于同一斜线上，所以，
解向量X必须满足的约束条件为:
|i-xi|≠ |j-xj|
以杭电hdu2553为例：http://acm.hdu.edu.cn/showproblem.php?pid=2553
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 int a[11], out[12], sum, n; 6 7 void dfs (int cnt) 8 { 9 if (cnt == n)10 {11 sum++;12 return;13 }14 else for (int i=0; i<n; i++)15 {16 bool flag = true;17 a[cnt] = i;18 for (int j=0; j<cnt; j++)19 if (a[cnt]==a[j] || cnt-j==a[cnt]-a[j] || cnt+a[cnt]==a[j]+j)20 {21 flag = false;22 break;23 }24 if (flag) dfs (cnt+1);25 }26 }27 int main()28 {29 for (int i=1; i<=10; i++)30 {31 sum = 0;32 memset (a, 0, sizeof a);33 n = i;34 dfs (0);35 out[i] = sum;36 }37 while (~scanf ("%d",&n) && n)38 {39 printf ("%d\n",out[n]);40 }41 return 0;42 }
n 皇后问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。