再次优化过的8皇后问题-创新互联

其实我没有做到记忆一些已经判定过的状态,增加trace来记忆已判定状态,去掉重复判断再次优化过的8皇后问题
#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

再次执行就好看多了

创新互联专业为企业提供余杭网站建设、余杭做网站、余杭网站设计、余杭网站制作等企业网站建设、网页设计与制作、余杭企业网站模板建站服务,10年余杭做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
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皇后问题-创新互联
网站URL:http://myzitong.com/article/deosge.html