エイト・クィーン問題
チェスには、キング・クィーン・ビショップ・ナイト・ルーク・ポーンの駒があり、日本の将棋に似
ている。ただ、違いは、日本の将棋盤が9×9なのに対して、チェス盤は8×8で少し狭い。
また、将棋は、相手の駒をとった場合、今度は味方の駒として自由に使えるのに対して、チェ
スの場合は、盤上から取り去られた駒は、2度と使えない。だから、将棋の場合、相手・味方
ともに、色の区別がない駒なのに、チェスはしっかり白黒の区別がつけられている。
チェスの駒の働きを、将棋の駒の働きでみてみよう。
チェスの駒 | キング | クィーン | ビショップ | ナイト | ルーク | ポーン |
将棋の駒 | 王将 | 飛車と角行 | 角行 | 桂馬に似ている | 飛車 | 歩に似ている |
チェス盤において、8個のクィーンを、お互いの利き筋には、どのクィーンもないように配置す
る問題を、エイト・クィーン問題という。92通りの配置方法のあることが知られている。
試行錯誤を繰り返して、ようやく、左のような配置図を得た。
(正直に告白すると、30分ほどかかってしまった。もっと、効率的に求
める方法があったら、是非お教えください。)
(参考文献:岡本 茂 監修 大島邦夫 堀本勝久 著
最新2002-’03年版パソコン用語事典(技術評論社))
同じような問題が、ビショップとかルークについても考えられる。
ビショップの場合、そのように配置できる駒の数は、14個で、例えば、
1つの例として、左図のようにおけばよい。また、配置の仕方は、7個
のビショップを黒地だけに配置する方法の数の2乗に等しい。
また、8個のルークを、互いの利き筋にないように配置するのは、
8!=40320通りの方法がある。
(参考文献:ゲリファント 他著 大門盛宏・日野寛三 訳
数列・組合せ・極限 (東京図書))
(追記) 塾生の諸君に、この問題について考えてもらったら、次のような配置を短時間で得る
ことが出来た。若い感性の素晴らしさに感動しました。脱帽です...f(^_^)。
T.K 君 高杉吉博 君 諏訪部恭平 君 府川武史 君
横尾良輔 君 A.M 君 T.K 君
(A.M 君のものは、偶然にも私の見つけたものと同じでした!)
(追記part2)新種が塾生達によって発見されましたので報告します。
川口直人 君 小泉晃一 君 杉山 聡 君
更なる発見を塾生たち諸君に期待します。全種発見まであと | 82 | 種類です! |
(エイト・クィーン問題解決のためのプログラム)
上記のように、いちいち絵を描いていては大変なので、数学的に処理する方法を考えよう。
8×8=64マスのどれかにクィーンを置くとき、縦・横・斜めのラインには、もう別のクィーンを
置くことはできない。この事実を、次のように数式処理する。
例えば、m行n列目にクィーンを置くとき、縦・横・斜めのラインには、固有な数が対応する。
即ち、 m : 横のライン (1≦m≦8)
n : 縦のライン (1≦n≦8)
m+n-1 : 右上がりの斜めのライン (1≦m+n-1≦15)
m-n+8 : 左下がりの斜めのライン (1≦m-n+8≦15)
この4つの数は、一つのクィーンに対して、ただ一つ定まる数である。従って、別なクィーン
を置いて、4つの数を求めたとき、そのどれかがそれ以前の対応するラインを表す数と一致
するものがある場合、その場所にクィーンを置くことは不可能であると判断される。
(成功例) | (失敗例) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
縦の列に、同じ数字がないので、全 てのラインは重複しない。 従って、これは、エイト・クィーン問題の 一つの解を与える。 |
8行8列目に最後のクィーンを置こう としても、既にその右下がりのラインが 使われてしまっているので、置くことが できない。 |
この考えを用いて、いくつかの場合を検証してみよう。
m+n-1、m-n+8 の計算は、表計算ソフトを使えば簡単に求まる。ここでは、Excel
を利
用して、エイト・クィーン問題の解を拾い上げる方法を述べる。
1行目にクィーンを置く可能性は、8通りある。今、1行1列目に1番目のクィーンを置くとする。
このとき、2行目にクィーンを置く可能性は6通りある。今、2行3、4列目に2番目のクィーンを
置くとすると、3行目のどこにクィーンを置いても失敗することが分かるので、2行5列目に2番
目のクィーンを置くとする。3行目にクィーンを置く可能性は3通りある。今、3行2、7列目に3
番目のクィーンを置くとすると、4行目のどこにクィーンを置いても失敗することが分かるので、
3行8列目に3番目のクィーンを置くとする。4行目にクィーンを置く可能性は2通りある。今、4
行2列目に4番目のクィーンを置くとすると失敗するので、4行6列目に4番目のクィーンを置く
とする。 n の残りの値は、2、3、4、7 で、この順列の数は、24通りある。Excelを用いて、こ
の全ての場合を調べると、(m,n)=(5,3)、(6,7)、(7,2)、(8,4)について、条件を満た
すことが分かる。(これは、まさしく上記の左側の場合である。)
このように、多少時間はかかるが、単に機械的な計算なので、92種類のパターンを得ること
は容易に出来ると思う。(全92種類のパターンを知りたい方は、こちらをクリック!)
(参考文献:野崎昭弘 著 コンピューターのセンス(数学セミナー’93-8 (日本評論社)))
(追伸)上記プログラムで検証の結果、今まで得られたパターンの中に誤りが発見されました。
本文を修正しましたので、ご了承下さい。