8クイーンで遊んでみた
８クイーン問題
Wikipedia:
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3
を解くプログラムは、以前C++の練習で書いたことがあったはず（Cだったかも？)だが、久しぶりに思い出したので、当時調べて見つけた解法をJavaで書いてみた。
（引用元：http://www.ic-net.or.jp/home/takaken/nt/queen/index.html）
class eQueen{
public static int count=0;
public static void setQ(int n,int l,int c,int r){
//８マスのボードに制限する為のビット
//"11111111"との論理和（または排他的論理和）を取ることで８マスのフィールドのみを考えられる。
final int bits = 255;
if(n<8){
//クイーン設置可能箇所を確認
int settable = bits^(l|c|r);
//再帰の際に受け渡す変数l,c,r
int nextl=0,nextc=0,nextr=0;
for(int i=0;i<8;i++){
if((settable&1)==1){
//右からi番目におく。
int pos=i;
//ビットで位置を表現。"00000001"->"00000100"
int posbit=1<<pos;
//クイーンの攻撃範囲を作成
nextl = ( (l<<1) | (posbit<<1))&bits;
nextc = (c | posbit)&bits;
nextr = ( (r>>1) | (posbit>>1))&bits;
setQ((n+1),nextl,nextc,nextr);
}
settable>>=1;
}
}else{
count++;
}
}
public static void main(String args[]){
setQ(0,0,0,0);
System.out.println(count);}
}
ちなみにこれはバリエーション解を数えてその数を出力するプログラムである。ユニーク解だけを数えるプログラムは残念ながら当時も今も俺のレベルじゃ書けない。つーか面倒。
さて、要は８ビットで８つのマスを表現して解こうという魂胆。８つのint型配列を使うより全然速い。
だいたい５００００回実行して平均をとると0.204msecぐらいで正解の９２を出す。
うむ、これでも十分速いと思うのだが、（というかこのビット演算利用のアイデア自体、調べた中で最速のものを用いた。Jeff Somersさんという方が考案されたようです）もう少し速くできないか。
ユニーク解を求めて重複度倍するのがやっぱり一番速いのだろうし、それもやる気がある時に書いてみたいのだが、とりあえず今考えつくのが「鏡像解」のみを求める解法だ。
要するに、「一列目に４番目〜７番目にクイーンを置く解」は「一列目に０番目〜３番目にクイーンを置く解」と鏡像関係にあるのだろうから、単純に二倍すればいいのではないかと。
……で、とりあえず改造してみたのがコレ。
class eQueen{
public static int count=0;
public static void setQ(int n,int l,int c,int r){
//８マスのボードに制限する為のビット
//"11111111"との論理和（または排他的論理和）を取ることで８マスのフィールドのみを考えられる。
final int bits = 255;
if(n<8){
//クイーン設置可能箇所を確認
int settable = bits^(l|c|r);
//再帰の際に受け渡す変数l,c,r
int nextl=0,nextc=0,nextr=0;
for(int i=0;i<8;i++){
if((settable&1)==1){
//右からi番目におく。
int pos=i;
//ビットで位置を表現。"00000001"->"00000100"
int posbit=1<<pos;
//クイーンの攻撃範囲を作成
nextl = ( (l<<1) | (posbit<<1))&bits;
nextc = (c | posbit)&bits;
nextr = ( (r>>1) | (posbit>>1))&bits;
setQ((n+1),nextl,nextc,nextr);
}
settable>>=1;
}
}else{
count++;
}
}
public static void main(String args[]){
for(int j=0;j<4;j++){
setQ(1,(2<<j),(1<<j),(1<<(j-1)));
}
count*=2;
System.out.println(count);}
}
解の数：９２
実行時間（１０００００平均）：0.10112msec
おお、速い。
予想通り約半分の時間で求まった。
このままいくとうまく最適化すれば0.1msec切れるのかなあ。
なんかこういう区切りいい壁があると燃えます（？）よね。
また記録縮まったら書きます。
つづく（のか？）
