公園設計の土地探し
エイトクィーンパズルと言って一般にnXnのboardにn個の石を配置し
お互いの石がぶつからない(縦、横、斜め)ように石を配置するものとする。
さて配置できるパターンでその中に石が全く置かれていない長方形での部分の面積が
最大になれる大きさはどれだけ取れるものが出来るか？
（なお1マスの大きさを1としておく。)
ｎ=6,7,8について求めて下さい。
出来ればその時の配置パターンも
(n=9も考えていたんですが,余りにパターンがあり過ぎて手をつけられていません。)
私の解釈が正しいかどうかの確認のために聞きたいのですが、
n=6のときの最大の長方形の面積は8ですか？
n=6では4通り配置が可能ですが位相的にはどれも同型となり中に取れる長方形の面積
は2*4=8の大きさを持ちます。
合っているかどうかわかりませんが、こんな値になりました。
n=6: 2*4=8
n=7: 2*5=10
n=8: 4*4=16
n=9: 4*5=20
n=10: 4*6=24
n=11: 5*6=30
n=12: 5*7=35
n=13: 6*7=42
n=14: 6*8=48
n=15: 7*8=56
手作業ではとても手に負えなかったので、Copilot(人工知能)と何度もやり取りを繰り返し
PARI/GPで走らせるプログラムをやっとの思いで完成させ調査してみました。
(位相的に同じものを探し出す手続きがとても面倒でした。でもこれをしないと対象のものが
莫大な数に膨れて調べる気力を奪われてしまいます。)
n=6,7,8,9,10での結果が以下の様になるようです。
なお
S:異なる配置総数、S0:位相的異なる配置総数とし
配置した中に生まれる公園(長方形)を最も広くできる配置図が以下のもので可能となります。
(最大面積は位相的に異なるパターンをすべて出力し、目で見て探しているのでひょっとして
見落としているものがあるかもしれませんが、一応何度も点検した積りです。)
6X6board (S=4;S0=1); 最大8
Solution
･ ･ ･ Q ･ ･
Q ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･
･ ･ ･ ･ ･ Q
･ ･ Q ･ ･ ･
7X7board (S=40;S0=6); 最大10
Solution
･ ･ Q ･ ･ ･ ･
Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ ･ ･ Q
･ ･ ･ Q ･ ･ ･
8X8board (S=92;S0=12); 最大16(正方形となる)
Solution
･ ･ ･ ･ Q ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･
Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ Q ･ ･ ･ ･
9X9board (S=352;S0=46); 最大20(２パターン存在)
Solution 1
･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･ ･ ･ ･
Solution 2
･ ･ ･ ･ Q ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･
10X10board (S=724;S0=92); 最大20(５パターン存在)
Solution 1
･ ･ ･ ･ ･ ･ ･ Q ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
Solution 2
･ ･ Q ･ ･ ･ ･ ･ ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
Solution 3
･ ･ ･ ･ ･ ･ ･ Q ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･
Solution 4
･ ･ ･ ･ ･ ･ Q ･ ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
Solution 5
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
n=10での24の配置図はどの様なものなのですか？
パターンはいろいろあるみたいですが、例えば
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
(追記)
パターンは全部で4パターンのようです。
･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･
最後のパターンは点対称できれいですね。
でもこれらは斜めが重複しませんか？
「すべての石について、縦横斜めの8方向に他の石が存在しない」
が成り立てば良いものと思っていましたが、違いますか？
もしこれが正しければ重複していないつもりですが、
重複しているようでしたら具体的にどのパターンのどの石とどの石が
重複しているかを教えて頂ければと思います。
また、私の解釈が間違いでしたら正しい解釈を教えて頂ければと思います。
# 上の書き込みでn=10のパターン数を「5」と書いてしまいましたが、「4」の間違いですので訂正しました。
すみませんでした。
投稿してすぐに間違いであることに気付いて削除しようと操作するもサイトの状態が固まった状態がしばらく続いて
いたので訂正できずにいました。
92パターンを再び画面を拡大して眺めていたら
92個を一覧にするため、出力されていたのをエクセルに並べて
(一文字が小さくなっていた)印刷してたので眺めていたので
. Q . . . . . . . . が
.Q.........
とQ.が重なった状態でしか見えなくてつい見落としていました。
(年とともに小さい字が見えずらい!）
･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･
これらは
Solution 73
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
Solution 76
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
Solution 87
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
Solution 92
･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ Q ･ ･ ･ ･
として実際に出力していた。
24の広さが取れることを確認できました。
高速化のアルゴリズムを考えていて気付いた点など書きます。
(1) 長方形は最大でも縦横2辺の合計がn
n≧6では最大の長方形の縦横2辺の合計がn未満になることはなさそうです。
n=2mの場合の最大面積は高々m^2、n=2m+1の場合の最大面積は高々m(m+1)となります。
nが大きい場合は自由度が増すためm^2またはm(m+1)となりそう(15≦n≦50で確認済み)ですが、
nが小さい(n=6,7,10,12,14)場合は制約が多くなり、それより小さい値になることがあります。
(2) 最大がm^2(n=2m)またはm(m+1)(n=2m+1)となる場合、石は長方形の上下左右にしか置けない
長方形の辺を延長して井の形にしたとき、角の4区画には置けません。
これは上辺の上と下辺の下を合わせてちょうど上下辺の長さ分の個数、
左辺の左と右辺の右を合わせてちょうど左右辺の長さ分の個数になる必要が
あることから言えます。
(3) 上記を踏まえて考えると、「条件を満たすパターンを生成して内部の最大長方形を調べる」よりも
「長方形の大きさと位置を先に固定し、石は置ける範囲だけ試す」の方が高速に探索できます。
（もちろん長方形の位置は全通り試す必要があります）
このように高速化すると、「条件に合うパターンを一つ見つける」だけならばn=50程度まで可能となります。
「パターンが何通りあるか」の場合はn=25程度までです。
(4) パターン数は、n=18程度まではあまり多くないですが、それを超えると爆発的に増えます。
n=6: 2*4=8 (1通り)
n=7: 2*5=10 (1通り)
n=8: 4*4=16 (1通り)
n=9: 4*5=20 (2通り)
n=10: 4*6=24 (4通り)
n=11: 5*6=30 (2通り)
n=12: 5*7=35 (2通り)
n=13: 6*7=42 (4通り)
n=14: 6*8=48 (26通り)
n=15: 7*8=56 (16通り)
n=16: 8*8=64 (44通り)
n=17: 8*9=72 (23通り)
n=18: 9*9=81 (77通り)
n=19: 9*10=90 (333通り)
n=20: 10*10=100 (1027通り)
n=21: 10*11=110 (1705通り)
n=22: 11*11=121 (2337通り)
n=23: 11*12=132 (18464通り)
n=24: 12*12=144 (27553通り)
n=25: 12*13=156 (188172通り)
n=26: 13*13=169 (247527通り)
n=27: 13*14=182 (2069383通り)
n=11で位相的に異なる341通りの配置方法から
最大面積が30となる配置図が2通りということだったので
その配置方法を何とか探しだすことを試みてみました。
(長方形を任意の位置に設定し空席のカウントを自動で行うプログラムなんて
とても組めるものではないので、探す方法は目が頼りです。)
Solution 237
･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･
Solution 312
･ ･ ･ ･ ･ Q ･ ･ ･ ･ ･
･ Q ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ Q ･
Q ･ ･ ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ ･ ･ ･ Q
･ ･ ･ ･ ･ ･ ･ ･ Q ･ ･
･ ･ ･ ･ Q ･ ･ ･ ･ ･ ･
･ ･ Q ･ ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ ･ Q ･ ･ ･
･ ･ ･ Q ･ ･ ･ ･ ･ ･ ･
･ ･ ･ ･ ･ ･ Q ･ ･ ･ ･
