自个儿写的8皇后递归移位实现

2013-10-18

自己写的8皇后递归移位实现本帖最后由 Benjaminzhou93 于 2013-10-14 07:41:13 编辑#includestdio.h#inc

自己写的8皇后递归移位实现
本帖最后由 Benjaminzhou93 于 2013-10-14 07:41:13 编辑

#include<stdio.h>
#include<time.h>
#include<windows.h>
#define B00000001 0x1
#define B10000000 0x80
int all = 0;
int iarr[8] = {1, 1, 1, 1, 1, 1, 1, 1};
int columns[8] = {0};
int exist[8][3] = {0, 0, 0};// 左斜， 右斜， 行

void print(int arr[])
{
for(int i = 0; i < 8; i++)
{
for(int j = B00000001; j <= B10000000; j <<= 1)
{
printf("%3d", (arr[i] & j) / j);
}
printf("\n");
}
printf("\n");
//Sleep(500);
all++;
}

bool OK(int n)
{
for(int i = 0; i < n; i++)
if(  exist[i][0] == exist[n][0] 
||  exist[i][1] == exist[n][1] 
|| exist[i][2] == exist[n][2] )
return false;
return true;
}


void find(int n = 0)
{
if(!OK(n - 1))
return;
for(iarr[n] = B00000001; iarr[n] <= B10000000;
iarr[n] <<= 1, columns[n] = (columns[n] +1) % 8)
{
exist[n][0] = n + columns[n];
exist[n][1] = n - columns[n];
exist[n][2] = columns[n];
if( n <= 7 )
find(n+1);
else
break;
}
if( n > 7)
print(iarr);
}

void main()
{
clock_t ct_begin, ct_end;
ct_begin = clock();
find();
ct_end = clock();
printf("all case: %d\n", all);
printf("used time: %f\n", (double)(ct_end - ct_begin)/CLOCKS_PER_SEC );
}

递归 8皇后移位
[解决办法]
仅供参考：（绝对不高效）

#include <stdio.h>
int d[8][8];
int n;
void queen8(int L) {
    int x,y;

    if (8==L) {
        n++;
        printf("%d\n",n);
        for (y=0;y<8;y++) {
            for (x=0;x<8;x++) {
//              printf("%d",d[y][x]);
                if (d[y][x]) printf("■");
                else         printf("□");
            }
            printf("\n");
        }
        return;
    }
    for (x=0;x<8;x++) {
        for (y=0;y<L;y++) {
            if  (              d[y][x      ]
             
[解决办法]
 (x-(L-y)>=0 && d[y][x-(L-y)])
             
[解决办法]
 (x+(L-y)< 8 && d[y][x+(L-y)]))
                break;
        }
        if (y>=L) {
            d[L][x]=1;
            queen8(L+1);
            d[L][x]=0;
        }
    }
}
int main() {
    int y,x;
    for (y=0;y<8;y++) {
        for (x=0;x<8;x++) {
            d[y][x]=0;
        } 
 
    }
    queen8(0);
    return 0;
}

[解决办法]

这个八皇后高效问题，可以网上搜索下！很多的！

至于代码格式，在发贴或者编译回复的时候，上方有个添加代码格式的选择<>，加载人头和笑脸之间的，点击下c/c++，把想要添加的代码加中出现的[code]之间就好了！
[解决办法]
试了下，求解耗时基本为0吧。时间全是花在输出上。

//*八皇后
void printQueen(int* queen,int top)
{
for(int j=0;j<top;j++)
{
for(int i=0;i<8;i++)
if(i==queen[j])
printf("Q");
else
printf(".");
printf("\n");
}
printf("\n");

}
int issolution(int* queen,int top)
{
for(int i=0;i<top;i++)
for(int j=0;j<top;j++)
if(j!=i)
{
if(abs(i-j)==abs(queen[i]-queen[j]) 
[解决办法]
 queen[i]==queen[j])
return 0;
}
return 1;
}
int main()
{
clock_t ct_begin, ct_end;
ct_begin = clock(); 
int queen[8],top=-1,count=0;
queen[++top]=0;
while(1)
{
if(!issolution(queen,top+1))
queen[top]++;
else if(top==7)
{
//printQueen(queen,top+1);
queen[top]++;
count++;
//getchar();
}
else
queen[++top]=0;
while(queen[top]>=8)
{
top--;
if(top<0)
break;
queen[top]++;
}
if(top<0)
break;
}
ct_end = clock();
printf("一共%d个解",count);
printf("used time: %f\n", (double)(ct_end - ct_begin)/CLOCKS_PER_SEC ); 
getchar();
}//*/

热点排行

C语言

自个儿写的8皇后递归移位实现