首页 > 代码库 > 优化后的循环8皇后

优化后的循环8皇后

去掉重复判断,这样应该基本没问题了

到wiki上去验证数据是否正确:http://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98

#include <stdio.h>#define N 13int q[N] = {0};int not_end=1;int cnt = 0;void print_q() {    int i;    for (i=0; i<N; i++) printf("%d ", q[i]);    printf("\n");    return;}int can_put(int m, int n) {    int i,j;    //row is ok    //colume    for (i=0; i<m; i++) {        if (q[i] == n) return 0;    }    //left-up    for (i=m-1,j=n-1; i>=0 && j>=0; i--,j--) {        if (q[i] == j) return 0;    }    //right-up    for (i=m-1,j=n+1; i>=0 && j<N; i--,j++) {        if (q[i] == j) return 0;    }    return 1;}void next_qn(int i) {    while (i >= 0) {        if (q[i] < N-1) {            q[i] +=1;            break;        }        q[i] = 0;        i--;    }    if ( i < 0) {        not_end = 0;    } else {        i++;        while (i < N) {            q[i] = 0;            i++;        }    }    return;}int main(int argc, char* argv[]) {    while (not_end) {        int i;        for (i=0; i<N; i++) {            if (!can_put(i, q[i])) break;        }        if (i == N) {            cnt++;            print_q();            next_qn(N-1);        } else {            next_qn(i);        }    }    printf("CNT: %d\n", cnt);    return 0;}

 

优化后的循环8皇后