小さいサイズのスライドパズルを解く
この記事は
の11日目がなんか空いていたので24日の朝に書いている記事です。
前日分は hakatashi さんの たぶん TSG CTF 開催記 、翌日分は hideo54 さんの なんかかく でした。 今は24日の朝なのにどっちも書かれてないのはなんでなんですかね(すっとぼけ)
導入
TSG は Slack での活動を含むサークルで、Slack の雑談チャンネルではプログラミング系サークルらしくいくつかの bot が動いています。
このようなゲーム bot たちが動く Slack 上で一定の地位を得るための手段として、何かしらのゲームが上手になるというのがあります。 本記事では、そのゲームとして「あほくさスライドパズル」を取り上げ、コツを紹介します。
あほくさスライドパズルとは
15パズルという古典的なパズルは皆さんもご存知かと思います。15パズルのように、並進対称性のあるピース(一般に平行四辺形であることが多い)が並んでいる盤面があり、その盤面の唯一ピースの存在しないマスに向けて隣接するピースを移動させることを繰り返して目標の状態にするパズルをスライドパズルと呼びます。
上の画像に「あほくさスライドパズル」で与えられる盤面がありますが、これは「なんでも言うことを聞いてくれるアカネチャン」というGYARI(ココアシガレットP)さんによるVOICEROID楽曲の一場面を模した画像を6つに分割して並べ替え、1ピース分抜いたものです。
あほくさスライドパズルは与えられた盤面から(存在していないピースを除いて)
く[茜ちゃんの頭部]あ
さ[茜ちゃんの胴部]ほ
の並びになるような操作をpostするゲームです。
一般にスライドパズルでは解くことができない盤面が与えられることはありません
というサイズは非自明な最小のスライドパズルのサイズです。1
TSG の Slack にはあほくさスライドパズルをはじめとした複数のスライドパズルが存在しますが、あほくさスライドパズルが多く遊ばれている理由の一つにこの最小性があると思います。
解き方
「あほ」もしくは「くさ」のピースは常に存在するので、存在するほうを取ってきてこれを基準に考えます。以下では「くさ」をベースに考えますが、「あほ」しか存在しない場合は左右反転して考えてください。
くさを作る
しばらく、あほや茜ちゃんは無視して、「くさ」を正しくすることに注力します。
向きの正しいくさ
次のようなくさがすぐに作れるとき、ラッキーです。このようなくさができればこれを回す(左2上右2下 を繰り返す)ことで正しいくさを作ることができます。
そうでないくさができているような場合、少し面倒です。
向きの正しくないくさ
そうでないくさがある場合、多少頑張る必要があります。
残り
あとは回して、
速く、短く解く
上の解き方では23手かかっています。 が、この盤面の最短手数は17手です。 この節では最短手数を出すコツについて話します。
揃える手順に上のものを採用したとしても「あほ」から揃えるか「くさ」から揃えるか、あるいは「(頭)あ」や「く(頭)」などから揃えることもできるなどの選択肢があります。この中で最も短くなりそうなものを選んで打つのが得です。
また、同じ組から揃え始めるとしても向きの反転を修正する方法は複数あるので、それのどれを選ぶか(他のピースの状態が綺麗になるものを選ぶといいことが多いです)で手数が短くなるかが決まります。
この取捨選択が高速になるとあほくさスライドパズルが高速に解けるようになります。 タイピング速度やスレッドを開くのにかかる時間もありますが、最短がn手の盤面をn秒以内に解けると「速く解けたな」という気になります。
〆
後半雑じゃないか？数やって直感を鍛えよう
どんなスライドパズルも最後に残るのは2x3盤面であることが多いと思うのでここを高速にするとスライドパズルが高速に解ける場合とそうでない場合があるぞい
-
は空きマスを正しい場所に動かすだけで解け、
はぐるぐる回しているだけで解けます。↩
