もう一度質問します。

質問

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=329998

回答No.7

s2t · ベストアンサー

局面の情報を出さなくてもいいなら、計算式でパターン数を求められます。
bit演算で求めたいってこういう事かな？

#include <stdio.h>

unsigned recursivesums(long long q, long long x, long long y)
{
long long v = 0;
long long z = q & ~x & ~y;
unsigned cnt = 1;

if(q)
for(cnt = 0; v = (z&=~v)&-z; cnt += recursivesums(q&~v, (x|v)<<1, (y|v)>>1));

return cnt;
}

int main(int argc, char *argv[])
{
int q;
printf("N=");
scanf("%d", &q);
if(q >= 4 && q <= 32)
printf("result: %u\n\n", recursivesums(~((long long)~0<<q), 0, 0));
else printf("invalid parameter.\n\n");
return 0;
}

お礼

ありがとうございます！！
ところでlong longは何ｂｉｔなんですか？３２ですか？
（つまらない質問ですいません）

一応局面も出したいです。
でも、数さえ分かればできますよね？
参考にさせて頂きます。

回答No.8

s2t

long longはVC++やBCでは__int64という型で64bitです。
お使いのコンパイラによって記述方法が違います。

また、この場合は計算式によって求めているので局面を出すのは無理かと思います。
局面を出したい場合は、実際にクイーンの効き筋チェックを行う方法をとる必要があります。

回答No.6

s2t

クイーンの効き筋チェックをbit演算で行いたいなら、コレ。
構造体は何に使いたいのか不明だから使っていません。

MinGWで確認しました。

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

#define N 8 /* 8×8の場合(最大32×32) */

int v, z[N];
long long x, y;

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)&1 && (x>>i+j)&1 && (y>>i-j+N-1)&1)
{
z[i] = j;
if(i < N-1)
{
v ^= 1<<j;
x ^= 1<<i+j;
y ^= 1<<i-j+N-1;
recursivesums(i+1);
v ^= 1<<j;
x ^= 1<<i+j;
y ^= 1<<i-j+N-1;
}
else printbits();
}
}
}

int main(int argc, char *argv[])
{
v = x = y = -1;
recursivesums(0);
return 0;
}

お礼

ありがとうございます！！
　そうですね。構造体を用いる必要はないですね。
　有難うございました。

回答No.5

notnot

書かれてるプログラム読んでません（すいません）ので、
ツリー構造をどう使いたいのかよくわかりません。
(変数名が短くコメントも無いので読む気がしないのが正直なところ)
bit列を盤面の記憶に使うと解釈されている回答者が多いのですが、それはナンセンスなので、すでに置かれているクイーンの効き筋のチェックに使うんだと思います。
各列に1つずつなのはロジックで制御するとして、
各行の効きチェックに変数ひとつ。右上がりと右下がりの斜めの効き筋チェックに各1つ。32ビットの変数が計３つあれば16ｘ16までの盤で効き筋チェックができます。
どのビットでチェックするかですが、行は自明。
斜めはx+yとx-y+16でチェックすればいい。

お礼

分かりにくいプログラムですいません。
　なるほど、変数を上手く使えばいいのですね。
　参考にさせてもらいます。

回答No.4

s2t

> unsignedをもちいたら３２×３２までかんがえられませんか？

どういう事でしょうか？
私の処理系ではunsignedの変数は32bitなので、32×32の全フィールドを格納する事はできません。
32×32ということは、局面を保存するには1024bitの領域が必要になるのでは？
また、signedとunsignedの違いは符号だけなので、bit演算の場合は関係ないですね。

> unsignedを用いたら配列に拡張したらかなり大きなものでももとめられるとおもうのですが、・・・・・

よく分かりませんが、局面は配列を利用して保存してもいいということでしょうか？

お礼

structを用いてやろうと考えていたのですが・・・・・・
　以前にunsigned型の変数１つを用いてｂｉｔ操作により素数を求めるプログラムを考えた事があるので、その延長としてできないかな？と思ってみたのです。
　どっちにしろｂｉｔ操作によりこの問題が解けるのであればどんな風になるのか少し興味があるので。
　どうでしょう？

回答No.3

ymmasayan

答えにならないかも知れませんが。
ツリー構造とビット操作にこだわらないといけませんか。

昔、８クイーンをＢＡＳＩＣで解いた事が有ります。
８進数８桁（００００００００～７７７７７７７７）を連続的に発生させ
８クイーンの条件を満たすものを探すという単純なものです。
後は、早めのチェックによって、余計な数字の組合せをいかにスキップ
させるかと言うのが腕の見せ所です。

余り、自慢できるアルゴリズムではありませんが、参考にでもなれば。

お礼

ありがとうございます。
　参考にさせていただきます。
　私はｂｉｔ操作で出来ると聞いたので挑戦してみたいんです…
　どうでしょう？

回答No.2

s2t

> ｔｒｅｅ構造とｂｉｔ操作を用いて考えたいのですがなかなかうまくいきません。

bit操作でN-Queen問題を・・・でしたか。失礼。
しかしながら、なぜbit操作なのでしょうか？
「long long」を用いてもせいぜい8x8までしか求められませんがそれでいいのですか？

お礼

unsignedをもちいたら３２×３２までかんがえられませんか？
　二次元配列でするやり方は人もしていたので・・・・と思ったのですが・・・
　unsignedを用いたら配列に拡張したらかなり大きなものでももとめられるとおもうのですが、・・・・・

回答No.1

s2t

コレじゃダメ？

参考URL：

http://www.okweb.ne.jp/kotaeru.php3?q=329998