エイトクイーン問題とはチェス盤とクイーンの駒を用いるパズルです。
8×8の盤上に8個のクイーンをそのどれもが一手でとられるような配置にしてはいけないように置く置き方を探すいうものです。(ちなみにクイーンは縦・横・斜めに何マスでも進める駒です)
図で表すと以下のようになるような駒の配置を考えます。丸の位置に駒を置いていきます。
単純にすべての組み合わせを考えると8×8=64マスにコマを8つ置く組み合わせは約45億通り(4,426,165,368)になり、コンピュータを使用して計算しても長い時間がかかってしまいます。そこで以下の条件を考えていきます。
- 各行8マスに置く駒は1つのみ
- 垂直方向に同じ列に駒があったらその列は置かない
以上の条件を付けて当てはまらないものを除外していくと、考える組み合わせは8!=40,320通りになり、コンピュータで解くのにも十分現実的な数になります。以上のことをプログラミングで解くことを考えます。
まずマスを以下のように番号を振って考えます。
そして左の列から駒を置くマスを選んでいきます。
置くマスの判定は二つのマスの位置を以下のように(x1,y1)と(x2,y2)とすると、(a)と(b)の場合に分けて考えることができます。
この時、斜め方向の判定は以下のように書けます。
判定が1または(-1)の場合、斜め一直線上にあるため、置くことができない判定になります。上の例でいえば(a)の点の場合です。それ以外の場合は置くことができます。(b)の点の場合が該当します。
以上の場合分けを用いればプログラミングでエイトクイーン問題を解くことができます。
ソースコードはこちらに置いておきます。
今回は8×8のチェス盤で考えましたが、升目を大きくして考えることもできます。現代では27×27の問題(27-queen)も考えられています。
このプログラムを直接使えるかはわかりません(そもそもマシンスペックが足りないと思いますが)ので気になった方は以下の参考から調べてみてください。
参考
0 件のコメント:
コメントを投稿