Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2005年01月01日(土) あけましておめでとうございます

気が付けば 気が付けばを含むブックマーク 気が付けばのブックマークコメント

もう正月ですか。

時の過ぎるのはかくも速いもので。

この日記も始めて半年近くになるのか。

最近はHaskellネタが全然増やせてない…今年は頑張ろう。

年をとった 年をとったを含むブックマーク 年をとったのブックマークコメント

数日前に22歳の誕生日を迎えた。

もっとも、最近は年を重ねても全然嬉しくない。

今年もたいしたことができなかったなぁとか、

そんなことを思うだけだ。

初夢 初夢を含むブックマーク 初夢のブックマークコメント

変な起こされ方(わき腹を小突かれまくり)をされたので

初夢カオスになってしまった。本当に訳が分からない。

こんなに混沌とした夢は久しぶりで、微妙にショックだ。

[]nqueenの解を一つ見つける nqueenの解を一つ見つけるを含むブックマーク 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)である(というか、解を出力する手間のみ)。

久しぶりに頭を使った問題であった。

h_sakuraih_sakurai 2005/01/02 11:35 モナドがいまだにわからないので、分かりやすい説明を考えて書いて欲しいです。間違っていてもいいから、文系的な説明にも挑戦してほしいです。

yaneuraoyaneurao 2005/01/02 11:36 面白いですネ! > N Queen問題の解

まあ、コンピュータにやらせるならば可能な解を全て列挙したいので、個人的にはback trackを用いて解くにしても、可能性の高そうな局面を優先して調べるとかで、どの程度までなら解けるのかにも興味がありますが。

それでも1000 Queenは厳しそう..

tanakhtanakh 2005/01/04 00:43 モナドの説明ですか。うーん。
http://www.sampou.org/haskell/a-a-monads/html/
これよりうまく説明出来る気はあんまりしないのですが…。
文系的な説明とはどうなんでしょうかね。私自身完全な理系なので、感覚が分からなかったりしますが。まぁしかし、平易な説明を書く価値はあるかもしれませんね。うーむ。

tanakhtanakh 2005/01/04 00:51 可能性の高そうな局面ですか…。解の全列挙となると結局可能性が0とはいえない部分を全て探索しないといけないわけで、可能性が0な場所を通常よりも多く見つけないとあんまり有効ではないかもしれませんね…。現在のところnqueenの解は20強ぐらいまで解かれているようですが、それも普通のバックトラック+並列計算で解かれているみたいでした。可能性の考慮で伸びるものならすでに記録がもっと伸びていてもいいような気もします。1000queenの全解は途方も無い数字になりそうなので、どうやっても(今のところは)求められないように思います…

yaneuraoyaneurao 2005/01/04 14:47 ああ、なるほろ。確かに可能性を考慮しても解の全列挙には意味なさそうですネ..。結局back track法しかないのなら、back trackのために必要なコストを最小限にすれば記録を樹立できるということですな..。やってみようかしらん。

yaneuraoyaneurao 2005/01/04 15:02 そんなわけで、実際にやってみたところ、だいたい15queenぐらいで1秒。1増えるごとにだいたい5倍ぐらいの時間がかかるとして..おそらく20queenで3125秒(52分)、30queenで967年..。ダ、、ダメ。思ったよか奥が深いですナァ..。

Connection: close