N-Queen 問題

質問

N-Queen問題を考えています。
　なかなかうまくいきません。
　どうやったら解けるか、アルゴリズムでも下の私が考えたプログラムでもいいんでアドバイスください。

（４×４の場合）

#include<stdio.h>
#define BYTESIZE 8
void printbits(unsigned i);
struct data
{
int basho;
unsigned l1,l2,tate,x;
};

int main(void)
{
unsigned m,l,hojo=0;
int kenchi,i,j,k;
struct data a[5];

for(i=0;i<=3;++i)
{
l=1<<i;
hojo|=hojo|l;
}

a[0].l1=0;
a[0].l2=0;
a[0].tate=0;

for(kenchi=0;kenchi<=3;)
{
for(i=1;i<=4;)
{
a[i].x=0;
for(j=a[i].x;j<=3 && ((~l)&hojo)==0;++j)
{
m=1<<j;
a[i].l1=((a[i-1].l1)<<1)&hojo;
a[i].l2=((a[i-1].l2)>>1)&hojo;
a[i].tate=(a[i-1].tate)|m;
l=(a[i].l1)|(a[i].l2)|(a[i].tate);
a[i].x=j+1;
}
if((~l)&hojo)
{
a[i].basho=j;
a[i].l1=(a[i].l1)|m;
a[i].l2=(a[i].l2)|m;
++i;
if(i==5) {for(k=1;k<=4;++k) printf("%d ",a
[k].basho);printf("\n");}
}

if(j==3)--i;
if(i==0) kenchi++;
}
}
}

void printbits(unsigned intval)
{
unsigned i;
for(i=0;i<BYTESIZE*sizeof(unsigned);++i)
printf("%d",(intval<<i&1<<BYTESIZE*sizeof(unsigned)-1)?1:0);
putchar('\n');
}

　tateで駒があった列、l1で左にずらしたもの、l2で右にずらしたものを表しています（うまく説明出来なくすいません）。

参考URL：http://oshiete1.goo.ne.jp/kotaeru.php3?qid=330589

回答No.1

s2t · ベストアンサー

こんな感じで。
MinGWで確認しました。

#include <stdio.h>
#include <stdlib.h>

#define N 8 /* 8×8の場合 */

int v[N], x[2*N-1], y[2*N-1], z[N];

void printbits(void)
{
int i, j;
static sol = 0;

printf("\nAns. %d\n", ++sol);
for(i = 0; i < N; i++)
{
for(j = 0; j < N; j++)
{
if(z[i] == j) printf("■");
else printf("□");
}
printf("\n");
}
}

void recursivesums(int i)
{
int j;
for(j = 0; j < N; j++)
{
if(v[j] && x[i+j] && y[i-j+N-1])
{
z[i] = j;
if(i < N-1)
{
v[j] = x[i+j] = y[i-j+N-1] = 0;
recursivesums(i+1);
v[j] = x[i+j] = y[i-j+N-1] = 1;
}
else printbits();
}
}
}

int main(int argc, char *argv[])
{
memset(v, 1, sizeof(v));
memset(x, 1, sizeof(x));
memset(y, 1, sizeof(y));

recursivesums(0);

return 0;
}

お礼

ありがとうございます！