パズル勉強会

パズルプログラミング勉強会

初心者課題:8クイーン|Nクイーン

見てはいけないソース: 8queen.c
参考:再帰のお勉強」(初心者限定)
by パソコン初心者


8クイーンについては、あまりにも有名なパズルなので、いちいち説明する ことは面倒なので止める。どういうパズルか知りたいときには、検索エンジンで 勝手に探して欲しい。

ここでは、このパズルの全解を求めるプログラムについて、初心者なりに検討 しようということである。上にあるのが、8×8の盤面にクイーンを8個置くと いう普通のエイトクイーンを、サイズ固定のまま解いたものである。

ただ、サイズが8の場合だけというのでは、上のようにとても下手なプログラム でも、ちゃんと短時間で解けてしまうので、全然面白くない。でも、一応対象性を 取り除いて、ユニークな解12個を求めている。

これを必死で改良(?)し、サイズを可変にした改良版が queen1.cである。

使い方は、

	queen [-p] [size]
であり、-p で解を表示しなくなる。要するに、実行時間を知りたいときに -p を指定する。

ついでに、queen2.cqueen3.cqueen4.cと、わずかばかりの 改良を試みた。それらの実行時間比較を以下に載せる。

ボードのサイズ1112131415
解の総数3411787923345752285053
queen1.c(msec) 0.714.0924.88160.991120.73
queen2.c(msec) 0.070.351.9411.7876.91
queen3.c(msec) 0.040.191.005.8937.36
queen4.c(msec) 0.020.110.493.0417.92
時間計測は、time の userモードのCPU時間

とりあえず、どうしようもないのをサイズ可変にしただけと、最後の改良との間には数十倍の速度差が 出てしまった。この改良であるが、パズル勉強会のメーリングリストで流れた情報を元に、ちょっと細工 をしたりしたものである。

まず、盤面(ボード)は、2次元のchar型の配列をやめ、1次元の配列で表現した。添字をx座標とし、 要素の値(board[x])がy座標になるように配列を使う。互いの利き筋上にクイーンを置いてはいけない のであるが、このチェック方法には色々ある。

普通は、x=0から順に調べて行くのだが、ここでも同じようにそうしている。 そして、あるxについて、yとして可能な値全部について置けるかどうか調べる訳だが、 よく行われるのが、queen1.cのように、馬鹿正直に、 左、左上、左下の3方向のクイーンの有無を forループで真面目に調べることであろう。

ここでは、もうすこし、無い知恵を絞って工夫した方法を使った。 一応、付録として、どんな方法を採用したかを示す図を載せておく。

説明は不要かと思うが、若干の説明をしておこう。

2つの斜め方向について、図の破線上に既にクイーンが存在するかどうかを保持する 配列を用意した。sued[]とbused[] である。図中の N は盤面のサイズである。

水平方向も調べないといけないのであるが、調べなくても済む方法がある。 それは、ボードを示す配列に、0〜N-1までの数字を1つずつ入れておく。 このとき、必ず、同じy座標をもつクイーンは存在しない。 つまり、このように初期化された配列に対して、この配列の要素の入れ替えだけで得られる 配置では、どのクイーンも必ず個となるy座標を持っているので、水平方向は調べる必要は無い。 同じx座標を持ち得ないのは言うまでもなかろう。

以上の考え方でプログラムを組んだのがqueen3.cで、 無駄なループを減らし、左端のクイーンと、その後のクイーンで関数を分けて条件判定の回数 を減らしたのがqueen4.cである。

もっと高速な方法があったら、ぜひパズル&プログラム初心者までメールしてくださ〜い。 あるいば、パズル勉強会のメーリングリストに投げてください。

2001年11月19日

パズル勉強会