プログラミングパズルに関心のある人は雑談しましょう！
期間限定のアルゴリズム問題を出題します。 コンピュータ＆パズル 公開プログラム研究開発ノート １１パズルの最適解が最長手数となる面の探索 探索に必要なメモリ量 において、 29,937,600バイト×3＝89,812,800バイト(86MB) という方法を示しましたが、 29,937,600バイト×2＝59,875,200バイト(57MB) で済ます方法を思い付きました。 その方法は、それほど大したことでもありませんので、近いうちに訂正したい と考えていますが、その前に「その方法が分ったという方」はこの掲示板に書き込み してほしいのです。期限は２００４年２月２４日までとします。お待ちしてます。
福地さん、こんにちは。 いやぁ、この掲示板の約半年ぶりの書込みありがとうございます。 そして、楽しい情報をありがとうございます。マンハッタン距離の持つ内容は 後から知りましたが、マンハッタン距離の言葉の由来がそういうものだった とは知りませんでした。マンハッタンなんて行ったことないですからね。 > 余談ですが、「最短でなくてもいいから、一見知的であるかのように15パズルを解く > ソルバー」を探し求めて辿りつきました。なかなか見付からないものです。 せっかくなので私も探してみました。ソルバープログラムではありませんが、 １５パズルを機械的にすんなり解く方法が下のＵＲＬで紹介されていました。 ここに書いてある手順をそのままプログラムすれば福地さん探しているソルバー になると思います。では。http://www.nakayosi-net.com/amuse/nakage/15puz.htm
すでに御存知の事とは思いますが、「15パズル自動解答プログラム〜」のページで Manhattan Distanceについて詳細不詳と書かれているので、蛇足ながらご説明いた します。 結論から言えば御推察の通りで、各軸上の距離の合計がマンハッタン距離となります。 例えば点(X,Y,Z)と(x,y,z)との間のマンハッタン距離は|X-x|+|Y-y|+|Z-z|です。 何故このような名前がついているかと言うと、ニューヨーク市のマンハッタンの あたりは、ちょうど京都のように碁盤目の街路がめぐらされており、ある地点から ある地点まで歩いていく場合、歩いていく距離は二点間のユークリッド距離では 実状にあいません。実際に歩くのに要する距離がマンハッタン距離となります。 余談ですが、「最短でなくてもいいから、一見知的であるかのように15パズルを解く ソルバー」を探し求めて辿りつきました。なかなか見付からないものです。
倉庫番の原点は「一見やさしそうで実は...」、もはや世界の倉庫番。 倉庫番が COPYRIGHT(C)1989,1990,2001-2003 FALCON CO.,LTD. として 再スタートするようです。日本から生まれた名作パズルゲームに期待し ています。(下のURLで偶然にも発見しました) 旧作面の使いまわしだけは無いよう願いつつ、 操作性にも充分に配慮されることを願いつつ、 大人向け知的ゲームに徹することを願いつつ、 発売が待ち遠しい！。 # Sokoban Official Site が出来つつあるので、著作権を侵害していそう # な私のページも一部閉鎖しなければならないと感じています。
くだらない質問ですみません。ゲームコーナーでお馴染みのWATTA,倉庫版,干し柿お年ゲーム,30ｘインテリジェントはかなり難しいゲームですが、作ったほうも苦労したと思います。このゲームをインターネットで公開するきっかけは何だったのですか!?また、途中で挫折しそうなときはありませんでしたか!?
こんばんは、deepgreenです。 私の方も、Ｊｏｉｎ処理で苦戦しています。やはり、制約が弱いため、候補の数が 多くて、高速化が難しいですね。私のアプローチは、ちょっと無理筋かもしれません。 時間がとれなくて、ほとんど進んでいませんが、予定の改善項目（？）は何とか 作り込みたいと思っていますが、。。。 最新の結果は、以下。前回よりちょっと改善して、nqueen3の２倍以下のところまで やっとこれたという状況です。これから先はどうなることやら？ deepgreen result nqueen3換算値 msec 秒 ===== N=12 Count = 1787 Time= 175 ===== N=14 Count = 45752 Time= 2,910 ===== N=16 Count = 1846955 Time= 66,770 ２８（＝104/22*6) ===== N=18 Count = 83263591 Time=2443,815 １４１３（＝104/22*299)
探索量を減らすための工夫をいろいろ試してみましたが、結局すべて逆効果に 終わってしまいました。部分解をハッシュ表に登録する方法も試してみましたが 確かに効き筋が同型となる異なる部分解は多く存在していますが全体から占める 割合があまりに小さすぎるので、処理が重くなった分だけ逆効果となりました。 構想も出尽くしてしまい、とりあえずの完成版としていたものを超えるものは作れ ませんでした。せっかくなので前回のメモ書きをほとんどそのままでＨＰにアップ ロードしてしまいました。
久しぶりの投稿です。 どうやら下記URLで(理論)値は出ているようです。 n^8くらいのペースで増えるようですね。 私はビット処理の高速化版を見ているだけでお腹いっぱいになってしまいました。http://web.iol.cz/vaclav.kotesovec/math.htm
現状でＮ＝２４の解を求める場合、私のマシン１台なら３年半はかかるという見積りです。 １００台なら２週間ですが、こんなことにマシンを遊ばせてもいいよという程度のＰＣを 使うなら３００台以上は必要でしょう。(２週間を限度として) 面白い提案ですが、まだまだアルゴリズムの工夫とか改善をしていくしかないでしょうか。 でも、いつか本当にそんなことができたら楽しいでしょうね。
今晩は、高橋謙一郎さん。 せっかく、Ｎ−クイーン問題を考えているのですから、 この掲示板で世界記録を目指すプロジェクトを立ち上げるのも 面白いのではないかと思います。 勿論、クリアすべき問題点がいろいろありますが、まずは、 次の二つでしょうか。 ・分散コンピューティングの仕組み作り 私のプログラム（Ｉ／Ｏ ４月号版）では問題を簡単に分割できますが 性能面はお話にならないので辞退します。高謙さん、或いは他の人のプログラムが ベースになると思いますが、どうやって分散化するかが、まず最初の問題になるでしょう。 ・正当性の証明 世界記録を目指すとしたら、先人の結果と比較できないのですから、 計算結果が正しい事を、客観的に示す必要があります。 例えアルゴリズムが正しいとしても、それがそのまま実装されている とは限らないわけだし、これもクリアは結構大変そうですね。