プログラミングパズルに関心のある人は雑談しましょう！
人の書いたプログラムを解析するだけに留まっていますが面白いです。 Jeff Somers さんのプログラムは結局、ビット処理で高速化している だけでした。ただ、効き筋の扱い方とビット演算方法はみごとです。 彼は再帰関数を書けないのでしょうか。再帰で書けば簡単なプログラム をスタックを自己管理して非再帰で書いているので彼のプログラムは 解読しにくかったようです。そこで一般的というか自分流に再帰で書き 直したプログラムを下に置きます。 注意:このプログラムは対称性を考慮しない解を求めます。 N=15 -> 2279184 2sec N=16 -> 14772512 12sec N=17 -> 95815104 84sec N=18 -> 666090624 628sec CPU = Athlon 2100++(1.73GHz)
御無沙汰しています。相互リンクさせてもらっている 「点と線の部屋」の塗り壁です。工学社から出ている雑誌 「Ｉ／Ｏ」に「数学的プログラミング」という連載を 今月号から始めました。発売は毎月１８日です。 で、何と言う偶然か１回目のテーマが「Ｎ−クイーン 問題」です。順列や組合せの観点から問題を多方面に解析 していきたいと思っています。 よろしければ、見て下さい。
Jeff Somers さんのプログラムはまだ解析していませんが、 藤原さんの queen4.c はグッドアイデアが集積していて勉強 になります。ちょっと思い付いた枝刈りを追加してqueen4a.c を作ってみました。(ソースは下) **** queen4.c (オリジナル) N=15 -> Total count 285053 5sec N=16 -> Total count 1846955 37sec N=17 -> Total count 11977939 247sec **** queen4a.c (修正版) N=15 -> Total count 285053 3sec N=16 -> Total count 1846955 22sec N=17 -> Total count 11977939 150sec N=18 -> Total count 83263591 1107sec CPU = Athlon 2100++(1.73GHz) Jeff Somers さんのプログラムはビット処理で高速化している だけなのか、それともグッドアイデアが潜んでいるのか、解析 に手間取りそうな感じです。
どうもお久しぶりです。 興味があったのでWebでちょっと調べてみました。 世界記録はN=23のようです。 http://www.durangobill.com/N_Queens.html 詳しいことは不明ですが、多分分散コンピュータとかの世界なんでしょうね。 アルゴリズムについてはあまり調べていませんが、 http://www.jsomers.com/nqueen_demo/nqueens.html のソースが参考になりそうです。
ご無沙汰しております。deepgreenです。 静かなので、ちょっと落書きです。 今度の連休をあてこんで、N Queens Problem（すべての解を求めるもの） を高速に解くＳｏｌｖｅｒを検討しています。 Ｎ＝１８までは、解が求められているのをみつけました。 その先はどこまでいけるのでしょうか？ 当面の目標は、以下のＵＲＬに公開されている queen4.c というSolverを 超えることですが、問題が単純なだけに、ちょっとてこずるかも知れません。 http://www.pro.or.jp/~fuji/puzzlestudy/8queen.html 興味のある方は、一緒にチャレンジしてください。
倉庫番 for Windowsは倉庫番Perfectと同じ内容なので、レベル16のステージ6は、 Perfectの276面ということになります。（レベル−１）×１８＋ステージ 私の作ったSolverでは解けませんでしたが、deepgreenさんの作った、DGsoko#2.1 では 341moves 60pushes で解けているようです。 ちなみに、この掲示板ではこういう質問には応対していませんのであしからず。
はじめまして、まおと言います。 以下のようにステージを真似て作ったのですが。 ##### # # # $$# #### . #### # $ *.* # # $.....$ # # *.* $ # #### . #### #$$$# # @ # ##### ソフトでも解けません＾＾;; 図は間違ってないと思います。 倉庫番のソフトは THINKING RABBITの倉庫番 for Windowsです ↑のステージはレベル16のステージ6です。 解けるのでしょうか？？ よろしくお願いします。ｍ(__)ｍ
私も2つ目を見つけました。 特に目新しいことはやっていません。 - 9 8 - - - - - - - - - - 7 - - - - - - - - 1 5 - - - 1 - - - - - - - - - - - 2 - - - - 9 - - - 9 - 6 - 8 2 - - - - - - - 3 - 5 - 1 - - - - - - - - - 4 - - - 2 -
ヒント数17の問題図、また見つかりました。 - - 1 - 2 - 7 - - - 5 - - - - - 9 - - - - 4 - - - - - - 8 - - - 5 - - - - 9 - - - - - - - - - - - 6 - - - 2 - - 2 - - - - - - - - 6 - - - - - 5 - - - - - 9 - 8 3 実は前から３つの数字による閉所を探すことは試しています。 今のところ、盤面が9x9であることに依存している上に すべての閉所を探せているわけでもないという怪しげな方法だったりしますが。 とりあえず以下のような閉所を探します。 ６マスで閉じている例 Ａ口□ Ｂ口口 Ｃ口口 Ａ口□ Ｃ口口 口口口 Ｂ口口 Ｃ口口 Ａ口口 または Ｂ口□ Ａ口口 口口口 口口口 口口口 口口口 Ｃ口□ Ｂ口口 口口口 ７マスで閉じている例（左右２つの例は性質が微妙に違います） Ａ口□ Ｂ口口 Ｃ口口 Ａ口□ Ｂ口口 口■■ Ｂ口口 Ａ口口 口●● または Ｂ口□ Ａ口口 Ｃ口口（■のどちらかにＣ Ｃ口口 口■■ Ａ口口 Ｃ口□ 口●● Ａ口口 ●のどちらかにＢ） ８マスで閉じている例 Ａ口□ Ｃ口口 Ｂ口口 Ｂ口口 Ａ口口 Ｃ口口 Ｃ口口 Ｂ口口 口■■（■のどちらかにＡ） ９マスで閉じている例 Ａ口□ Ｃ口口 Ｂ口口 Ｂ口口 Ａ口口 Ｃ口口 Ｃ口口 Ｂ口口 Ａ口口 不完全な手法ながら、効果はあるんじゃないかと思っています。
浅海さんが最初に見つけたN=17の問題から副産物が出てきました。 ヒント位置を１ケ所変更することでもN=17の問題として成立する パターンがあったのです。(解答図も同じです) 尚、このようなものを他の４つで見つけることは出来ませんでした。 #3 1 - - - - - - - - - - 2 7 4 - - - - - - - 5 - - - - 4 - 3 - - - - - - - 7 5 - - - - - - - - - - - - 9 6 - - - 4 - - - 6 - - - - - - - - - - 7 1 - - - - - 1 - 3 - Hints: 17 Author: 浅海 焔 #6 1 - 4 - - - - - - - - 2 7 4 - - - - - - - 5 - - - - - - 3 - - - - - - - 7 5 - - - - - - - - - - - - 9 6 - - - 4 - - - 6 - - - - - - - - - - 7 1 - - - - - 1 - 3 - Hints: 17 Author: 浅海 焔 + 高橋謙一郎