ホームページへ戻る  書き込みリストへ戻る
プログラミングパズル雑談コーナー

プログラミングパズルに関心のある人は雑談しましょう!


メモリ節約問題 投稿者:高橋謙一郎  投稿日:01月21日(水)22時42分29秒

期間限定のアルゴリズム問題を出題します。

コンピュータ&パズル
 公開プログラム研究開発ノート 
  11パズルの最適解が最長手数となる面の探索
   探索に必要なメモリ量
において、
29,937,600バイト×3=89,812,800バイト(86MB) という方法を示しましたが、
29,937,600バイト×2=59,875,200バイト(57MB) で済ます方法を思い付きました。

その方法は、それほど大したことでもありませんので、近いうちに訂正したい
と考えていますが、その前に「その方法が分ったという方」はこの掲示板に書き込み
してほしいのです。期限は2004年2月24日までとします。お待ちしてます。


re:マンハッタン距離について 投稿者:高橋謙一郎  投稿日:12月20日(土)12時36分51秒

福地さん、こんにちは。

いやぁ、この掲示板の約半年ぶりの書込みありがとうございます。
そして、楽しい情報をありがとうございます。マンハッタン距離の持つ内容は
後から知りましたが、マンハッタン距離の言葉の由来がそういうものだった
とは知りませんでした。マンハッタンなんて行ったことないですからね。

> 余談ですが、「最短でなくてもいいから、一見知的であるかのように15パズルを解く
> ソルバー」を探し求めて辿りつきました。なかなか見付からないものです。

せっかくなので私も探してみました。ソルバープログラムではありませんが、
15パズルを機械的にすんなり解く方法が下のURLで紹介されていました。
ここに書いてある手順をそのままプログラムすれば福地さん探しているソルバー
になると思います。では。

http://www.nakayosi-net.com/amuse/nakage/15puz.htm


マンハッタン距離について 投稿者:福地  投稿日:12月19日(金)05時03分06秒

すでに御存知の事とは思いますが、「15パズル自動解答プログラム〜」のページで
Manhattan Distanceについて詳細不詳と書かれているので、蛇足ながらご説明いた
します。
結論から言えば御推察の通りで、各軸上の距離の合計がマンハッタン距離となります。
例えば点(X,Y,Z)と(x,y,z)との間のマンハッタン距離は|X-x|+|Y-y|+|Z-z|です。
何故このような名前がついているかと言うと、ニューヨーク市のマンハッタンの
あたりは、ちょうど京都のように碁盤目の街路がめぐらされており、ある地点から
ある地点まで歩いていく場合、歩いていく距離は二点間のユークリッド距離では
実状にあいません。実際に歩くのに要する距離がマンハッタン距離となります。

余談ですが、「最短でなくてもいいから、一見知的であるかのように15パズルを解く
ソルバー」を探し求めて辿りつきました。なかなか見付からないものです。


倉庫番がファルコンから再スタート 投稿者:高橋謙一郎  投稿日:07月22日(火)20時41分53秒

倉庫番の原点は「一見やさしそうで実は...」、もはや世界の倉庫番。

倉庫番が COPYRIGHT(C)1989,1990,2001-2003 FALCON CO.,LTD. として
再スタートするようです。日本から生まれた名作パズルゲームに期待し
ています。(下のURLで偶然にも発見しました)

旧作面の使いまわしだけは無いよう願いつつ、
操作性にも充分に配慮されることを願いつつ、
大人向け知的ゲームに徹することを願いつつ、
発売が待ち遠しい!。

# Sokoban Official Site が出来つつあるので、著作権を侵害していそう
# な私のページも一部閉鎖しなければならないと感じています。

http://www.sokoban.jp/


凄いね貴方は... 投稿者:鈴木哲臣  投稿日:06月24日(火)10時42分25秒

くだらない質問ですみません。ゲームコーナーでお馴染みのWATTA,倉庫版,干し柿お年ゲーム,30xインテリジェントはかなり難しいゲームですが、作ったほうも苦労したと思います。このゲームをインターネットで公開するきっかけは何だったのですか!?また、途中で挫折しそうなときはありませんでしたか!?


Re:N Queens Problem  投稿者:deepgreen  投稿日:06月04日(水)21時34分45秒

こんばんは、deepgreenです。

私の方も、Join処理で苦戦しています。やはり、制約が弱いため、候補の数が
多くて、高速化が難しいですね。私のアプローチは、ちょっと無理筋かもしれません。

時間がとれなくて、ほとんど進んでいませんが、予定の改善項目(?)は何とか
作り込みたいと思っていますが、。。。

最新の結果は、以下。前回よりちょっと改善して、nqueen3の2倍以下のところまで
やっとこれたという状況です。これから先はどうなることやら?

            deepgreen result                      nqueen3換算値
                                         msec        秒
===== N=12   Count =     1787    Time=     175 
===== N=14   Count =    45752    Time=   2,910 
===== N=16   Count =  1846955    Time=  66,770     28(=104/22*6)
===== N=18   Count = 83263591    Time=2443,815    1413(=104/22*299)


Re:N Queens Problem 投稿者:高橋謙一郎  投稿日:06月02日(月)07時14分27秒

 探索量を減らすための工夫をいろいろ試してみましたが、結局すべて逆効果に
終わってしまいました。部分解をハッシュ表に登録する方法も試してみましたが
確かに効き筋が同型となる異なる部分解は多く存在していますが全体から占める
割合があまりに小さすぎるので、処理が重くなった分だけ逆効果となりました。

構想も出尽くしてしまい、とりあえずの完成版としていたものを超えるものは作れ
ませんでした。せっかくなので前回のメモ書きをほとんどそのままでHPにアップ
ロードしてしまいました。


N Queens Problem 投稿者:としひで  投稿日:05月20日(火)21時42分05秒

久しぶりの投稿です。

どうやら下記URLで(理論)値は出ているようです。
n^8くらいのペースで増えるようですね。

私はビット処理の高速化版を見ているだけでお腹いっぱいになってしまいました。

http://web.iol.cz/vaclav.kotesovec/math.htm


re:N−クイーン問題 プロジェクト 投稿者:高橋謙一郎  投稿日:05月19日(月)22時38分16秒

現状でN=24の解を求める場合、私のマシン1台なら3年半はかかるという見積りです。
100台なら2週間ですが、こんなことにマシンを遊ばせてもいいよという程度のPCを
使うなら300台以上は必要でしょう。(2週間を限度として)

面白い提案ですが、まだまだアルゴリズムの工夫とか改善をしていくしかないでしょうか。
でも、いつか本当にそんなことができたら楽しいでしょうね。


N−クイーン問題 プロジェクト 投稿者:塗り壁  投稿日:05月18日(日)22時39分23秒

今晩は、高橋謙一郎さん。
せっかく、N−クイーン問題を考えているのですから、
この掲示板で世界記録を目指すプロジェクトを立ち上げるのも
面白いのではないかと思います。
勿論、クリアすべき問題点がいろいろありますが、まずは、
次の二つでしょうか。

・分散コンピューティングの仕組み作り
私のプログラム(I/O 4月号版)では問題を簡単に分割できますが
性能面はお話にならないので辞退します。高謙さん、或いは他の人のプログラムが
ベースになると思いますが、どうやって分散化するかが、まず最初の問題になるでしょう。

・正当性の証明
世界記録を目指すとしたら、先人の結果と比較できないのですから、
計算結果が正しい事を、客観的に示す必要があります。
例えアルゴリズムが正しいとしても、それがそのまま実装されている
とは限らないわけだし、これもクリアは結構大変そうですね。


 ホームページへ戻る 書き込みリストへ戻る