【復活求む!】惜しくも解散してしまったバンド|J-ROCK編 >>

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



(4×4の場合)

#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

 

A 回答 (1件)

こんな感じで。


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;
}
    • good
    • 0
この回答へのお礼

ありがとうございます!

お礼日時:2002/08/07 04:56

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

価格.com 格安SIM 料金比較