在一个8*8的棋盘上 放置八个皇后 , 使得他们互相不攻击(皇后攻击范围为 同行同列同对角线) ,
从64个格子中 选一个子集 , 使得 " 子集 中恰好有八个元素 , 且任意选出的两个格子都不是同一行,同一列同,一对角线" , 这是子集枚举问题 , 然而 , 64个格子的自己有2^64个 , 所需处理数据过大 !
从64个格子中 选八个格子 , 称为组合生成问题 , 根据组合数学 有 4.426*10^9中方案 , 虽然比第一种好 , 但是然并卵 .
---------------------------我是分割线--------------------------------------
经过思考你会不难发现下面一种方法 , 每一行每一列恰好会放一个皇后 , 所以可以从第一行开始放 , 然后考虑第二行 , 依次进行 下去 !
这样就变成了全排列生成问题 , 这样的排列有 8! = 40320个 , 枚举量不会超过该数字
然而 如果每次都枚举这么多次的话 也会超时的 , 所以我们可以采用回溯的方法 或者 用 上/下一个排列 .
1 // 代码超时 2 #include<stdio.h> 3 #include<string.h> 4 #include<math.h> 5 #include<iostream> 6 #include<algorithm> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #include<set> 11 #include<stack> 12 using namespace std; 13 int n,c[123456],tot; 14 void search(int cur) 15 { 16 if(cur==n) //递归边界 , 只要走到了这里 , 所有皇后必然不冲突 . 17 tot++; 18 else 19 for(int i=0;i<n;i++) 20 { 21 int ok=1; 22 c[cur]=i; // 尝试将 cur 行的 皇后放在 i 列 . 23 for(int j=0;j<cur;j++) // 检查是否 个 前面的皇后冲突 24 { 25 if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j]) // 26 { 27 ok=0; 28 break; 29 } 30 } 31 if(ok) 32 search(cur+1); 33 } 34 } 35 int main() 36 { 37 while(~scanf("%d",&n),n) 38 { 39 memset(c,0,sizeof(c)); 40 tot=0; 41 search(0); 42 printf("%d\n",tot); 43 } 44 }
原文：http://www.cnblogs.com/A-FM/p/5315785.html