nqueenの解を一つ見つける

その他

今年一つ目は去年解いた割と面白かった問題より。
http://acm.uva.es/p/v100/10094.html
要するに、nqueenの解を一つ見つけよという問題。
サイズは1000まで。


普通にバックトラックで解くと、20あたりですでに秒のオーダに突入してしまい、
1000などとてもじゃないが無理である。
ニューラルネットを用いて解く方法でも、1000*1000のサイズともなると
一回のスキャンに1000^3のコストがかかるので、
どうもタイムリミットに収まりそうも無い。
一緒に考えていたM氏がニューラルネットの解法を応用した(?)
乱数を用いたアルゴリズムで1000の解を数秒で出すことに成功したが、
これでもSubmitしてみるとタイムリミットになったようである。


というわけで、試行を繰り返す方法はどれも駄目なようである。
そこで、全てのサイズにおいて自明な解が存在しないかを考えることにした。
8queenの解を列挙してみたところ、

.....o..
...o....
......o.
o.......
.......o
.o......
....o...
..o.....

このような比較的綺麗な解があることに気が付いた。
この配置より、桂馬跳びのラインをうまく使えば良いのではないかと考えた。
色々と試行錯誤をしてみたところ、サイズが4+6nと6+6nの時は
非常に単純な解が存在することが分かった。

4
..o.
o...
...o
.o..
10
.....o....
o.........
......o...
.o........
.......o..
..o.......
........o.
...o......
.........o
....o.....
6
...o..
o.....
....o.
.o....
.....o
..o...

桂馬とびのラインを二本の解が存在する。
縦横のサイズが+6されたときも同様に可能である。
というのも、桂馬とびのラインは斜めラインを三本に一本占有するので、
桂馬跳びライン二本が互いに重なっていなければ、
どちらかのラインを横に3の倍数ずらしてもまた
それらのライン二本は重ならないのである。
8+6nの場合は簡単にはいかない。
これはかなり試行錯誤した結果、以下のようなパターンで生成できることが分かった。

14
....o.........
..........o...
.....o........
...........o..
......o.......
............o.
o.............
.............o
.o............
.......o......
..o...........
........o.....
...o..........
.........o....

桂馬のライン4つから構成されている。
8の場合と比べるとよく分かるかもしれない。
左端は中央から始まり、斜め下に進んで、
上から出てきてまた斜め下…という感じ。
これまた+6のサイズで同じように出来るというのを示すのは簡単である。


というわけで、これでめでたく偶数の場合の解が見つかったことになる。
(もちろん4以上のサイズで)
奇数の場合であるが、これは偶数の場合の解を拡張して、角に一個追加すれば良い。
というのも、上記偶数解は全て点対象の配置になっており、
対角線のラインにはクイーンが置かれていないためである。


これで全ての解が見つかった。
計算量のオーダはO(n)である(というか、解を出力する手間のみ)。
久しぶりに頭を使った問題であった。