倉庫番solverをちょっと Erlangっぽく (nakatani @ cybozu labs)
前回の倉庫番solver for Erlang は Erlang の勉強のためだった割には Erlang の良さを活かしていないつくりだったので、もう少しまじめに作り直してみました。 ソース： solver3.erl 今回はひとまず分散は置いといて、軽量プロセスの恩恵を発揮させる方向で攻めています。 プロセスの構造は manager と solver の２種類だけ、やりとりされるメッセージは基本的には solver → manager の branch メッセージだけという簡単なものに。 manager は branch メッセージを受け取ったら、最大歩数を超えてないか、解けてないか、探索済みの局面ではないかをチェック、問題なければ solver プロセスを起こしてデータを渡します。 solver はデータを１手進ませた枝（その局面で押せる荷物を全部押してみたもの）を作り、branch メ
倉庫番とそのソルバーの情報まとめ 神は細部に宿り給う
第8回 倉庫番を解くアルゴリズム：ITpro これをきっかけにちょっと調べたら、面白いことになってきたのでメモしておこう。私が初めて（2番目だったかも）買ってもらったパソコンには倉庫番のソフトが付属していて、ルールの単純さとそこから生み出されるパズルの複雑さの落差に興味を引かれたものだった。他にこれに匹敵するものはコンウェイのライフゲームぐらいのものではなかろうか。 倉庫番パズル ソルバ（問題を解くプログラム）の能力はまだ人間に遠く及ばないらしい。十数年前に初めて触った時点ですでにコンピュータの能力は人間を超えているだろうと思っていたのでこれはちょっと意外だった。なんと倉庫番はPSPACE完全問題らしい。 日の目を見なかった問題たち その2 日の目を見なかった問題たち その2の追記 Sokoban is PSPACE-complete Draft 後知恵だが、確かに言われてみれば、解
第8回 倉庫番を解くアルゴリズム - 地球にやさしいアルゴリズム：ITpro
「倉庫番」＊1というゲームをご存じでしょうか。図1のように盤面にはいくつかの「荷物」とそれを運ぶ「人」がいます。人は1個の荷物を押して運ぶことができます。荷物を引っ張ったり，二つ並んだ荷物を同時に押して運ぶことはできません。人と荷物は縦横4方向に動けますが，壁のある位置には進めません。人を使って盤面上の荷物を動かし，すべての荷物を目的地（ゴール）に収めることができればゲーム・クリアとなります。図1の問題を解くための手順を示すアルゴリズムを作ってください。 友人たちと車でスキーに行くとき，いつも困るのは「トランクへ荷物を詰め込む順番」です。大きなスキー靴やかさばるスキーウエアを詰め込んでいるうえ，人によってはゲーム機や本を持ってきたりするので，各自の荷物の量がまったく違うのです。狭い車のトランクには，これら荷物をうまい順番で入れていかないとなかなか全部収まりません。寒い冬の夜中にごそごそと詰
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
