建站
咨询
售后
建站咨询
再次优化过的8皇后问题-创新互联
其实我没有做到记忆一些已经判定过的状态，增加trace来记忆已判定状态，去掉重复判断
网站栏目：再次优化过的8皇后问题-创新互联
网页路径：http://www.scyingshan.cn/article/deosge.html
#include
#define N 9
int q[N] = {0};
int not_end = 1;
int trace = 0;
int cnt = 0;
int sum = 0;
void print_q() {
int i;
for (i=0; i=0 && j>=0; i--,j--) {
if (q[i] == j) return 0;
}
//right-up for (i=m-1,j=n+1; i>=0 && j= 0) {
if (q[trace] < N-1) {
q[trace]+=1;
break;
}
q[trace]= 0;
trace--;
}
if ( trace < 0) {
not_end= 0;
}else {
int i = trace + 1;
while (i < N) {
q[i]= 0;
i++;
}
}
return;
}
int main(int argc, char* argv[]) {
while (not_end) {
int i;
for (trace; trace 再次执行就好看多了
CNT: 352, times: 72378
real 0m0.007s
user 0m0.004s
sys 0m0.000s我们可以看到判定次数已经和递归一样，也就是说已经成功的用循环替代了递归，并且执行的时间少了0.001s，这大概是省在来回搬栈上了。
N = 16，跑了12m，再大，估计我的机器跑不动了。不过这个算法的时间复杂度怎么算呢？
CNT: 14772512, times: 842815472
real 12m26.208s
user 12m25.835s
sys 0m0.028s大概这是我的最终答案了，找时间去网上找找经典问题的经典解，或许能学到更有趣的事情。
网站栏目：再次优化过的8皇后问题-创新互联
网页路径：http://www.scyingshan.cn/article/deosge.html
