2006/09/21(木) [n年前の日記]
#1 [iappli] ペントミノとやらのページを眺める
n x m の領域の中に、特定のパターンを複数配置する、という変更要求がきているので、そのへんどうしたもんかと悩んでいたり。で、ヒントになる情報はないかと探していたら、どうもペントミノなるパズルがあるらしく。
_ペントミノを解く
_パズル問題解法のアルゴリズム
なるほど、一旦ギューッと詰めちゃって、その中の何番目を利用するか、だけを乱数で求めて、とかやればそれっぽい配置になるだろうか。
と思って眺めてたのだけど、考えてみれば、自分がやろうとしてるものは、必ずしもピッチリ隙間無く領域内に収まるものではないから、これらのアルゴリズムは利用できないのだな。てなことに後で気づいて、ショボン。
_ペントミノを解く
_パズル問題解法のアルゴリズム
なるほど、一旦ギューッと詰めちゃって、その中の何番目を利用するか、だけを乱数で求めて、とかやればそれっぽい配置になるだろうか。
と思って眺めてたのだけど、考えてみれば、自分がやろうとしてるものは、必ずしもピッチリ隙間無く領域内に収まるものではないから、これらのアルゴリズムは利用できないのだな。てなことに後で気づいて、ショボン。
◎ とりあえず2つほど処理を考えた。 :
ひとまず次々に置いてみて、置けないと判ったらまた最初から置き直す方法と、パターンの縦横個数で領域を割って置いていく方法。
前者は、時間はかかるけど隙間無く置ける可能性がある。ただ、最悪、配置が決まるまで、領域の個数分 x 配置するパターンの数分、延々とリトライし続ける可能性が。既に置いた場所を記録しておいて無駄を省くとかしないといけないのだろうな。まあ、再帰が使えそうなあたりはいい感じなのだけど。
後者は、あっさり場所が求まる。けど、その配置具合には明らかに規則性があるというか、見た目だけでも即座に手抜き配置をしているとユーザさんに判ってしまう可能性が。
前者は、時間はかかるけど隙間無く置ける可能性がある。ただ、最悪、配置が決まるまで、領域の個数分 x 配置するパターンの数分、延々とリトライし続ける可能性が。既に置いた場所を記録しておいて無駄を省くとかしないといけないのだろうな。まあ、再帰が使えそうなあたりはいい感じなのだけど。
後者は、あっさり場所が求まる。けど、その配置具合には明らかに規則性があるというか、見た目だけでも即座に手抜き配置をしているとユーザさんに判ってしまう可能性が。
◎ とりあえず考えた処理をメモ。 :
忘れるといかんので。ていうかメモ用紙に書いたのを清書。
- 「出現位置記録配列」のインデックスをチェック。置けるはずの全ての位置に置いたか？ 置いたなら、エラーを返す。
- 乱数でx,yを取得。
- 取得した x,y は既に出現したか。出現済みなら、2. に戻る。
- x,y を、「出現位置記録配列」に記録。インデックスを進める。
- 「パターン配置マップ」を参照。パターンを置こうとしてる場所に別のパターンが書き込まれてないかチェック。書き込まれてたら、1. に戻る。
- 「パターン配置マップ」にパターンを書き込み。
- 次に置くパターンの、「出現位置記録配列」を初期化＆先頭に自分の位置を記録。
- 次に置くパターンを決定。（自身が処理したのと同じ関数を再帰呼び出し）
- 次に置くパターンが決定できたなら、正常終了を返して、関数を抜ける。エラーが返ってきたら、自分が書き込んだパターンを消去して、1. に戻る.
[ ツッコむ ]
以上です。