(KATAMINOを解くプログラムを作成する)KATAMINOを解くプログラムKATAMINOとはKATAMINOとは、Gigamic社が発売するパズルゲームです。長方形の枠にぴったり収まるように組み合わせて遊ぶゲームです。(2019/6/19時点)楽天で購入KATAMINOを解くアルゴリズムKATAMINOを解くアルゴリズムとして、総当たりの方法を採用します。以下のように、左上から右に向かって順番に番号を振ります。ピースが置かれていないマスのうち、一番小さい番号を埋めるようにピースを置いていきます。全てのピースが置ければおしまい、全ての組み合わせを試してみてどの組み合わせでもマスを全て埋めることができなければ解けない組み合わせです。総当たりの手順は以下のようになります。使用するピースを決めます。今回は以下の3つのピースを使います。番号1のマスを埋めるように1つピースを置きます。ピースは枠からはみ出して置くことはできません。残ったピースのうち、一番小さい番号(今回の例では3)を埋めるようにピースを置きます。ピースは枠からはみ出して置くことはできません。ピース同士は重なってはいけません。(今回の例では繰り返せないので下の手順へ進んでください)どのピースも置けなくなったら、ピースを回転または反転させます。全ての回転・反転を試した場合は、ピースを1つ戻して、まだ試していない別のピースを置きます。全てのピースの全ての回転を試したならば、1つ前のピースを回転または反転させます。全てのピースが置ければ終了です。解く過程を図にすると、以下のような木構造になります。KATAMINOを解くには、この木をもれなくたどっていけば良いことがわかります。上のアルゴリズムは深さ優先探索を用いています。プログラムを書きやすくするために、もう少しプログラミングしやすい言葉を使って手順を書きます。深さ優先探索を採用するので、スタックを使用します。以上がKATAMINOを解くプログラムの基本的なアルゴリズムです。次回はデータ構造について考えます。「ピーターからの問題」1から9までを使って分数の穴埋め算。(1)はてなブログをはじめよう!yucatioさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。