C++とアセンブラで8クイーン解いてみた

プログラミング

８クイーンの話題二度目。
それにしてもパズル好きだなあと思う。
でも今回は、アセンブラの練習がしたかったのが主な理由。

あと、今はじめて知ったのだが、プログラムコード記述用に「シンタックス・ハイライト」なるものがあって、自動的にプログラムを色づけして表示してくれるらしい。こんな便利なものがあったとは……


ともあれ、８クイーンの話。


まず、８クイーンを解くアルゴリズムは、以前の記事
http://d.hatena.ne.jp/g940425/20100505/1273051885
と同じく、このページ→http://www.ic-net.or.jp/home/takaken/nt/queen/index.htmlから引用しました。


まず、C++で書けばこう↓なる。

#include<iostream>
using namespace std;
int count=0;
void search(int n,int l,int s,int r){
	l|=n;l<<=1;l&=255;
	s|=n;s&=255;
	r|=n;r>>=1;r&=255;
	if(s==255){count++;return;}
	int c=255^(l|s|r);
	while(c){search(-c&c,l,s,r);c^=(-c&c);}
}
int main(){
	search(0,0,0,0);
	cout<<count<<"\n";
	return 0;
}

実行すると
92
となる。


で、本題ですよ。
これと全く同じことをアセンブラでやりたいのだが、如何せんアセンブラ自体やりはじめなんで、関数への引数の受け渡しとかスタックの使い方とかが手探りだったので時間がかかってしょうがなかった。
で、できたプログラムが下のコード。
ほとんどC++版コードと同じ流れですが、次の段のクイーンの配置可能場所を生成するところと、正解かどうか判定するところが逆になってます。

bits	16
org	100h

mov	ch,0
mov	ah,00000000b
mov	al,00000000b
mov	bh,00000000b
mov	bl,00000000b
call	search

mov	dl,ch
call	putt

endquit:
;プログラム終了
mov	ax,4Ch
int	21h

;DLレジスタを出力
putc: 
push	ax
mov	ah,02h
int	21h;
pop	ax
ret

;DLレジスタを１０進数で表示
putt: 
push	ax
push	bx
mov	ah,0
mov	al,dl
;100の位
mov	bl,64h
div	bl
cmp	al,0h
jz	decade
push	dx
add	al,30h
mov	dl,al
sub	al,30h
call	putc
pop	dx
mov	dl,ah
;10の位と1の位
decade:
mov	ah,0
mov	al,dl
mov	bl,0Ah
div	bl
add	al,30h
add	ah,30h
mov	dl,al
call	putc
mov	dl,ah
call	putc
pop	bx
pop	ax
ret

;DLの最下位の１をDLに取得
getmin: 
push	ax
push	dx
xor	dl,11111111b
;11111111でマスクしたDLをALに保存
mov	al,dl
inc	al
pop	dx
and	dl,al
pop	ax
ret

;potitioning(AH,AL,BH,BL)
;AH:新規にクイーンを配置する位置
;AL:クイーン左前方攻撃範囲
;BH:クイーン前方攻撃範囲
;BL:クイーン右前方攻撃範囲
;の４つのデータから、
;AL:新規クイーン配置後のクイーン左前方攻撃範囲
;BH:新規クイーン配置後のクイーン前方攻撃範囲
;BL:新規クイーン配置後のクイーン右前方攻撃範囲
;DL:新規クイーン配置後のクイーン配置可能範囲
;（1:配置可能、0:配置不可能）
;を生成する関数
potitioning: 
or	al,ah
or	bh,ah
or	bl,ah
shl	al,1
shr	bl,1
mov	dl,al
or	dl,bh
or	dl,bl
xor	dl,11111111b
ret

;クイーンの置ける位置を探索し、置いていく関数
;８クイーンが完成したらCHをインクリメント
;深さ優先探索
search: 
call	potitioning
cmp	bh,11111111b
jnz	begloop
inc	ch

begloop:
push	ax
push	bx
push	dx

call	getmin
cmp	dl,00000000b
jz	endloop
mov	ah,dl
call	search
pop	dx
xor	dl,ah
pop	bx
pop	ax
jmp	begloop
endloop:
pop	dx
pop	bx
pop	ax
ret

;改行を出力
newline: 
push	dx
mov	dl,0dh
call	putc
mov	dl,0ah
call	putc
pop	dx
ret

実行すると
92
となる。成功。

せっかく作ったんで、次回は速度比較でもしようと思います。
アセンブラの方はスタック以外のメモリ使ってないから速そうだしね。

あ、それと小ネタ（？）を一つ
「C++でならどこまで短いコード書けるだろうか？」と思っていろいろやってみたところ、

#include<iostream>
int t=0;f(int n,int l,int s,int r){s|=n;l|=n<<1;r|=n>>1;if(s==255)t++;int c=~(l|s|r)&255;while(c){f(n=-c&c,l<<1&255,s,r>>1&255);c^=n;}}main(){f(0,0,0,0);std::cout<<t<<"\n";}

の193バイトが最高でした。見づらいけど。



ではまた（・ω・）ﾉｼ