クイーン支配問題

前回のクイーン支配問題のブログは, 8×8の大きさのチェス盤に, 5個の クイーンを置き, 盤面のすべての場所が支配できる配置の数を計算するものであった. 4860という解が得られたが, どう考えても, 90度の回転や, 左右の反転で同じになる 仲間が沢山含まれている筈である.

そこで次の課題は, 本質的に異なる配置の数を知ることである. 前回のすべての配置の それぞれに, 回転や反転を施し, それで一緒になる配置を仲間とするプログラムを書き, 実行すると, 638という答が出た.

クイーン支配の配置は, かなりランダムらしいから, 回転で仲間が4倍になり, 反転で また2倍になって, 仲間は8人がほとんどになりそうである. しかし, 反転するとどうなるか. 左右反転では, 偶数の列に奇数のクイーンを置くから, クイーンの奇数個を中央の列に置き, 残りの偶数個を, 左右対称の位置に置けばいいわけだが, 中央の列が存在しないから, 左右や上下の反転で一緒になるものはない. 一方, 対角線で反転することを考えると, 対角線には中央があるから, そこに奇数個を置くと, 対称になり得る. この対角線の 中央を通る, もう一方の対角線で, もう一回反転できるかというと, 対角線の長さ が8という偶数なので, そういう反転はあり得ない.

従って, 4人の仲間のグループと, 8人の仲間のグループとで, グループは638あり, メンバーの総数は, 4860人ということになる.

4人と8人のグループはそれぞれ何個あるかは, いわゆる鶴亀算で得られる. a+b=638, 4a+8b=4860 だから a=61, b=577である.

そこで, その638の配置をすべて図示したのが次である. 1行に16個, 縦に20行あって, 最初のページに320個, 次のページに318並んでいる. 638個の配置には, 0番から637番 の番号があり, 最初のページの左上が0, そこから右へ1,2,3,...と続く. 次のページの最下行の右端が, 637番である.

これらの図は, 小さ過ぎるので, それぞれの図で, 各クイーンがどのように全盤を支配する かを示す図を描いた. 下の20の図は, 上の図の左端の配置の一つ置きに描いたもので, 塗りつぶしの丸がクイーン, それから四方八方に出る破線が支配領域である. 8×8 のすべての盤面が破線で蔽われているのが分る.

最後に4人仲間の配置はどれかという話題である. 合格発表のような下の番号が, 2回対称軸を持つ61の4人組である.

(20 25 29 30 59 128 129 137 141 149 163 165 171 180 182 183 204 215 219 229 232 238 242 258 259 261 267 276 283 288 289 365 368 372 391 393 441 468 470 473 474 511 516 517 518 524 526 530 551 568 569 574 582 584 592 594 605 617 620 623 633)

この表の0, 15, 30, 45番目を選び(20, 183, 289, 524番になる), 上と同じように 示したのが, 下の図である. 対角線で反転するのが分る. 中のふたつは面白い.