【C#】N-Queens Problem(エイトクイーン問題)を解いてみた

C#

 

今回は最近集中してやっているアルゴリズムの問題の中から超有名な「N-Queens Problem」という問題です。どういう問題なのかはすぐ後で説明します。

 

教えるのがかなりへたかもしれませんが、一応C#でのプログラム例をコメント付きで出すので参考にしていただけると幸いです。

 

N-Queens問題とは

 

問題自体は至極簡単です。

 

8×8マスのチェス盤で8つのクイーンを置くときに、どのクイーンも互いに襲撃されない状態にするにはどうゆうにクイーンを配置すればいいかを解いていきます。(今回は8×8に設定されているが、ほかのマス数でも可)

 

チェスでのクイーンがどのような動き方をするのかというと、縦横斜めから一方向にどこまでも進むことが出来ます。将棋をやったことのある人には、飛車と角の能力をあわせもった駒といえばわかりやすいかもしれません。

 

つまりこの問題を解く際は、1つのクイーンを置いたらそのマスの縦横斜めにはクイーンを置くことが出来ないということを頭に置いおくことが必要です。

 

他のクイーンに襲われないようにどう配置にするか、また、どこかに配置したとしてもそれはその後に置くことのできるクイーンの場所を制限することになるので、適当にやるとどこにおいてもクイーンが襲われるという詰んだ状態におちいってしまいます。

 

始めに言っておきますが、このN-Queens Problemは歴史が深い問題で、有名というのもそれに起因するのですが、様々な数学者やAIなどが任意のマス数におけるこの問題の解を現実的な時間内でだすための方法を考えています。

 

要は完全な解が見つかっていないということです。これは別に解けないと言うことではありません。現在も27×27のチェス盤での解は求まっています。

 

しかし、それらはいわゆる「配置できる配置できない」を実際にやってみてながら調べるしらみつぶしに近い方法です(最新の方法ではある程度効率化されているとは思いますが)。しかし、これでは数が増えるにしたがって解を求めるための時間がなくなってしまいます。

 

なので、私がこれからやる解き方も完全ではない解き方の1つであると思ってください。

 

問題

 

今回はAOJの「ALDS1_13_A:   8 Queens Problem」を解きます。

 

  • 入力

1行目に整数 が与えられます。続く  行にクイーンが配置されているマスが2つの整数r,c で与えられますr,cはそれぞれ0から始まるチェス盤の行と列の番号を表します。

  • 出力

出力は 8×8のチェス盤を表す文字列で、クイーンが配置されたマスを ‘Q’、配置されていないマスを ‘.’ で表します。

 

  • 入力例

2

2 2

5 3

 

  • 出力

……Q.
Q…….
..Q…..
…….Q
…..Q..
…Q….
.Q……
….Q…

 

具体的な解き方は次に解説します。

解き方

 

解き方は先ほども言ったように「こうすればもっとも少ない探索回数でスマートに解ける」というものがないので、しらみつぶし的な物になってしまいます。

 

しかし、本当にしらみつぶししていたら8×8のチェス盤でもすごい組み合わせ数になって、いわゆる組み合わせ爆発が起きて「いつまでたっても処理が終わらないよー」と言うことになります。

 

なので今回は、これまた有名な「バックトラック法」という単純な全探索を避けるための方法を使います。

 

バックトラック方とは、単純な全探索を少し効率化した方法であり、今回は「クイーンの利き筋(移動範囲)には置かない」という条件を付け足すことで、「クイーンを置けないならその場合を考えない」とします。これで、クイーンが置ける場合のみを考えられるので無駄な探索を避けることが出来ます。

 

上のバックトラック法のもと、置ける場所には順番にクイーンを置いていき、もし8個クイーンを置くことが出来たらその時点でいったん探索を抜けて、クイーンが置かれた位置情報をもとにクイーンの位置を結果として表示します。

 

また、「しらみつぶしにクイーンが置ける場所を調べる」という機能を実装するために再帰関数を利用します。再帰した先で、先程の「クイーンをおくことが出来る」という条件に一致しない場合にメソッドをバック(戻る)して前のメソッドに戻ります。

 

再帰メソッド内では、「現在配置されているクイーン達の利き筋じゃない場所にクイーンを置いてみる」という処理を中心にして、「置いた結果がだめだったら置いたことをなかったことにして前にメソッドに戻る」、「現在置かれたクイーンはいくつ目のクイーンなのかの記録」をしていきます。

 

N-Queens Problemソースコード

 

 

使っている変数がいったい何を意味するのか、どんな役割を担っているのかをコメントでできるだけ簡潔にかいたのですが、けっこうごちゃごちゃしてますね。すいません。

 

しかし個人的に、プログラムの参考書を見ていて、著者が設定したそれぞれの変数がいったい何を意味するのかがまったく分からず、具体的な値を入れてみてようやくその役割を理解するということがありかなり苦労した経験があるので、どうしてもコメントは少し多めです。

 

上のコードをじっくり見てもらえばわかると思いますが、Visitが今回の本命のクイーンの置ける位置を探索してくれる再帰メソッドです。

 

再帰は、クイーンが8個置けた瞬間に中断して、Printメソッドで最初の入力のクイーンの配置を満たすのかを確認。もし満たしていたら結果を出力して終了し、満たしていない別の解だったら望む解を見つけるためにもう一度Visitメソッドへ戻ります。

 

探索は、とある行((i, j)におけるiに対応、今回は0 ~ 7まで)において、クイーンがどの列((i, j)におけるjに対応、今回は0 ~ 7まで)に置けるのかを確認していきます。

 

i = 0の時、クイーンは0 ~ 7列のうちどこに置くことが出来るか

i = 1の時、クイーンはi = 0の時に置いた列以外のどこに置くことが出来るか

i = 2の時、クイーンはi = 0とi = 1の時に置いた列以外のどこに置くことが出来るか

とi = 7となるまで繰り返していくことになります。

 

そして変数について、rowやculmはまんまコメントに書いてあることがすべてなのでわかると思うのですが、slan_rightやslan_leftが分かりにくいと思います。

 

どっちも盤上のすべてのマス (i, j) において、その場所はクイーンの利き筋かどうかを表すための配列ですが、配列に入るのが「i + j」や「i – j + N – 1」となっているのがパッと見た瞬間にはわかりずらいと思います。

 

現在、盤上のマスを一番左上を(0, 0)として一番右下を(7, 7)としたマスを考えています。この時とある任意の場所(i, j)にクイーンがいるとすると、slan_rightは、そのマスの斜め左方向\のマスはすべて「i + j」において一定値になることを利用しています。

 

それもそのはず、あるマス(i, j)から↘に移動すると、iは+1、jは-1となり±0、↖に移動すると、iは-1、jは+1となりこれも±0で変化なし。つまり、あるマス(i, j)の斜め左のマスの「i + j」のマスは常に一定となります。

 

/方向もこれと似たようなことを利用しており、今度は斜めに移動するとiとjは最初のマス(i, j)からどちらも+1または-1ずつされていきます。これはつまりiとjが同じ比率で増減することを意味するので、i – j、つまりiとjの差が常に一定であることを意味します。

 

しかし、「i – j」をそのまま入れるわけにはいきません。というのもi – jの値はi = 0 j = 7の時にi – j = -7となることがあり、この場合配列の添え字にはマイナスの値は入れられないのでエラーがでます。なので、「i – j + N – 1」とすることで最小の値が出た場合でも負にならないようにしているのです。

 

言われてみれば単純な解放なのかもしれませんが、思いつくことはできませんね。再帰メソッドも使い慣れてないですし。

 

また、このアルゴリズムはとても有名なので、Googleで検索したらヒットすること間違いなしです。なので、わかりにくいと思ったらいろんなところの解法も見て、自分が一番わかりやすいと思ったやつを参考にするといいです。

 

コメント