本文共 2114 字，大约阅读时间需要 7 分钟。
传说中的N皇后问题，不过这道题只要求一组满足条件的解。如果按照通用的递归回溯算法会在n比较大的时候超时。所以有两个思路：
一是随机产生一个1~N的排列，如果满足条件（斜行不冲突），则输出；否则，交换两个元素的位置减少冲突，如果冲突可以减为0，则输出，否则重新生成随机排列。解法见。
另一种思路是构造解。见。可以以0ms过测试。原理见。（声明：我看不进去啊。。。只能知其然不知其所以然。。。）
代码如下：
#include using namespace std;void print(int sol[], int n){ for(int i = 0; i < n; ++i) { cout< >n; if(n == 0) return 0; if(n % 6 != 2&& n % 6 != 3) { int cnt = 0; for(int i = 2; i <= n; i += 2) { sol[cnt] = i; cnt++; } for(int i = 1; i <= n; i += 2) { sol[cnt] = i; cnt++; } } else { int k; if(n % 2 == 0) k = n / 2; else k = (n - 1) / 2; if(n % 2 == 0 && k % 2 == 0) { int cnt = 0; for(int i = k; i <= n; i += 2) { sol[cnt] = i; cnt++; } for(int i = 2; i <= k - 2; i += 2) { sol[cnt] = i; cnt++; } for(int i = k + 3; i <= n - 1; i += 2) { sol[cnt] = i; cnt++; } for(int i = 1; i <= k + 1; i += 2) { sol[cnt] = i; cnt++; } } else if(n % 2 == 1 && k % 2 == 0) { int cnt = 0; for(int i = k; i <= n - 1; i += 2) { sol[cnt] = i; cnt++; } for(int i = 2; i <= k - 2; i += 2) { sol[cnt] = i; cnt++; } for(int i = k + 3; i <= n - 2; i += 2) { sol[cnt] = i; cnt++; } for(int i = 1; i <= k + 1; i += 2) { sol[cnt] = i; cnt++; } sol[cnt] = n; } else if(n % 2 == 0 && k % 2 == 1) { int cnt = 0; for(int i = k; i <= n - 1; i += 2) { sol[cnt] = i; cnt++; } for(int i = 1; i <= k - 2; i += 2) { sol[cnt] = i; cnt++; } for(int i = k + 3; i <= n; i += 2) { sol[cnt] = i; cnt++; } for(int i = 2; i <= k + 1; i += 2) { sol[cnt] = i; cnt++; } } else { int cnt = 0; for(int i = k; i <= n - 2; i += 2) { sol[cnt] = i; cnt++; } for(int i = 1; i <= k - 2; i += 2) { sol[cnt] = i; cnt++; } for(int i = k + 3; i <= n - 1; i += 2) { sol[cnt] = i; cnt++; } for(int i = 2; i <= k + 1; i += 2) { sol[cnt] = i; cnt++; } sol[cnt] = n; } } print(sol, n); } return 0;}
转载地址：http://jxxli.baihongyu.com/