エイトクイーンとは
| | / | ||||
\ | | | / | |||
\ | | | / | |||
― | ― | ― | ― | ― | |
/ | | | \ | |||
/ | | | \ |
チェスのクイーンは、上下左右斜めに何マスでも進める、チェスにおいて最も利きの強い駒である。将棋の飛車と角行を合わせた利きと同等。
エイトクイーンは、チェスボードの8×8マスに、8つのクイーンを互いに利きに入らないように配置するパズルである。言い換えれば、8×8マスの中に、縦・横・斜めにクイーンが重複しないよう配置していくパズルである。
1848年にチェス作局家のMax Bezzelが創案したパズルで、現在、解は12通り(回転同形や鏡像同形を含めると92通り)あることが知られている。以下にエイトクイーンの一例を掲載する。縦・横・斜めにクイーンが重複していないことが確認できる。
|
重複を気にせず配置してしまい、そこからクイーンを置き換えていくトライ&エラー方式で解けるが、ここでは計算を用いた解法を紹介する。下のような表を使って考える。
R | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
C | ||||||||
R+C | ||||||||
R-C |
Cの行に、1から8までを重複がないよう、ランダムに入れ、R+CとR-Cをそれぞれ計算する。
R | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
C | 4 | 6 | 8 | 2 | 7 | 1 | 3 | 5 |
R+C | 5 | 8 | 11 | 6 | 12 | 7 | 10 | 13 |
R-C | -3 | -4 | -5 | 2 | -2 | 5 | 4 | 3 |
R+Cの行とR-Cの行それぞれについて、重複があればCの行に入れた数を変更して再計算する。重複がなければOK。RとCが各クイーンの位置(行と列)を示しており、上の表からは以下のような解を得られる。ちなみに、今回得られたこの解は、8×8のエイトクイーンでは唯一の点対称形である。
|
エイトクイーンを一般化、n×nのマス上にn個のクイーンを配置する問題として考えることができる。以下に一例を示す。
|
|
|
|
|
掲示板
1 ななしのよっしん
2016/08/20(土) 13:06:39 ID: bzwufueLCe
点対称形って珍しいんだな
2 ななしのよっしん
2016/09/04(日) 17:50:45 ID: vapt7R5l2C
懐かしいわ
昔総当りで解いた
真ん中の4x4マスに置ける配置がほんの数パターンしかなくて
最外周も3~4個をなんとかして押しこむ形だから
少し頑張れば終わるのよ 組合せ爆発なんてならない
タイトル:こうりゃく
3 ななしのよっしん
2016/09/04(日) 18:06:10 ID: EGBFVrLiC0
>>2
真ん中の4×4に必ずしも4つ入るとは限りません。
“単純に見てnが増えるのに従って、全マス数 n^2 個に対し置く駒の数は n 個であるから、置ける場所(の候補)の増え方により、解の数には組合せ爆発が起きる。”(Wikipediaより引用)
急上昇ワード改
最終更新:2024/04/26(金) 00:00
最終更新:2024/04/26(金) 00:00
ウォッチリストに追加しました!
すでにウォッチリストに
入っています。
追加に失敗しました。
ほめた!
ほめるを取消しました。
ほめるに失敗しました。
ほめるの取消しに失敗しました。