ここでは、このパズルの全解を求めるプログラムについて、初心者なりに検討 しようということである。上にあるのが、８×８の盤面にクイーンを８個置くと いう普通のエイトクイーンを、サイズ固定のまま解いたものである。
ただ、サイズが８の場合だけというのでは、上のようにとても下手なプログラム でも、ちゃんと短時間で解けてしまうので、全然面白くない。でも、一応対象性を 取り除いて、ユニークな解１２個を求めている。
これを必死で改良(?)し、サイズを可変にした改良版が queen1.cである。
使い方は、
queen [-p] [size]であり、-p で解を表示しなくなる。要するに、実行時間を知りたいときに -p を指定する。
ついでに、queen2.c、 queen3.c、queen4.cと、わずかばかりの 改良を試みた。それらの実行時間比較を以下に載せる。
| ボードのサイズ | 11 | 12 | 13 | 14 | 15 |
| 解の総数 | 341 | 1787 | 9233 | 45752 | 285053 |
| queen1.c(msec) | 0.71 | 4.09 | 24.88 | 160.99 | 1120.73 |
| queen2.c(msec) | 0.07 | 0.35 | 1.94 | 11.78 | 76.91 |
| queen3.c(msec) | 0.04 | 0.19 | 1.00 | 5.89 | 37.36 |
| queen4.c(msec) | 0.02 | 0.11 | 0.49 | 3.04 | 17.92 |
とりあえず、どうしようもないのをサイズ可変にしただけと、最後の改良との間には数十倍の速度差が 出てしまった。この改良であるが、パズル勉強会のメーリングリストで流れた情報を元に、ちょっと細工 をしたりしたものである。
まず、盤面(ボード)は、２次元のchar型の配列をやめ、１次元の配列で表現した。添字をx座標とし、 要素の値(board[x])がy座標になるように配列を使う。互いの利き筋上にクイーンを置いてはいけない のであるが、このチェック方法には色々ある。
普通は、x=0から順に調べて行くのだが、ここでも同じようにそうしている。 そして、あるxについて、yとして可能な値全部について置けるかどうか調べる訳だが、 よく行われるのが、queen1.cのように、馬鹿正直に、 左、左上、左下の３方向のクイーンの有無を forループで真面目に調べることであろう。
ここでは、もうすこし、無い知恵を絞って工夫した方法を使った。 一応、付録として、どんな方法を採用したかを示す図を載せておく。
説明は不要かと思うが、若干の説明をしておこう。
２つの斜め方向について、図の破線上に既にクイーンが存在するかどうかを保持する 配列を用意した。sued[]とbused[] である。図中の N は盤面のサイズである。
水平方向も調べないといけないのであるが、調べなくても済む方法がある。 それは、ボードを示す配列に、0〜N-1までの数字を１つずつ入れておく。 このとき、必ず、同じy座標をもつクイーンは存在しない。 つまり、このように初期化された配列に対して、この配列の要素の入れ替えだけで得られる 配置では、どのクイーンも必ず個となるy座標を持っているので、水平方向は調べる必要は無い。 同じx座標を持ち得ないのは言うまでもなかろう。
以上の考え方でプログラムを組んだのがqueen3.cで、 無駄なループを減らし、左端のクイーンと、その後のクイーンで関数を分けて条件判定の回数 を減らしたのがqueen4.cである。
もっと高速な方法があったら、ぜひパズル＆プログラム初心者までメールしてくださ〜い。 あるいば、パズル勉強会のメーリングリストに投げてください。