小さいサイズのスライドパズルを解く

この記事は

adventar.org

の11日目がなんか空いていたので24日の朝に書いている記事です。

前日分は hakatashi さんの たぶん TSG CTF 開催記 、翌日分は hideo54 さんの なんかかく でした。 今は24日の朝なのにどっちも書かれてないのはなんでなんですかね(すっとぼけ)

導入

TSG は Slack での活動を含むサークルで、Slack の雑談チャンネルではプログラミング系サークルらしくいくつかの bot が動いています。

f:id:naan11235813:20211224032253p:plain
さまざまなbot

このようなゲーム bot たちが動く Slack 上で一定の地位を得るための手段として、何かしらのゲームが上手になるというのがあります。 本記事では、そのゲームとして「あほくさスライドパズル」を取り上げ、コツを紹介します。

あほくさスライドパズルとは

15パズルという古典的なパズルは皆さんもご存知かと思います。15パズルのように、並進対称性のあるピース(一般に平行四辺形であることが多い)が並んでいる盤面があり、その盤面の唯一ピースの存在しないマスに向けて隣接するピースを移動させることを繰り返して目標の状態にするパズルをスライドパズルと呼びます。

上の画像に「あほくさスライドパズル」で与えられる盤面がありますが、これは「なんでも言うことを聞いてくれるアカネチャン」というGYARI(ココアシガレットP)さんによるVOICEROID楽曲の一場面を模した画像を6つに分割して並べ替え、1ピース分抜いたものです。 あほくさスライドパズルは与えられた盤面から(存在していないピースを除いて)
く[茜ちゃんの頭部]あ
さ[茜ちゃんの胴部]ほ
の並びになるような操作をpostするゲームです。

f:id:naan11235813:20211224032730p:plain
スライドパズルを解いているところ

一般にスライドパズルでは解くことができない盤面が与えられることはありません

f:id:naan11235813:20211224034311p:plain
15パズルの有名な不可能配置 wikipedia「15パズル」より
が、あほくさスライドパズルではランダムな盤面が与えられるため約1/2(1/2より少し大きい)の確率で解けない盤面が与えられます。 このときに「不成立」と指摘することもあほくさスライドパズルの目的です。
f:id:naan11235813:20211224032759p:plain
不成立のスライドパズルを見抜いているところ

2\times3というサイズは非自明な最小のスライドパズルのサイズです。1 TSG の Slack にはあほくさスライドパズルをはじめとした複数のスライドパズルが存在しますが、あほくさスライドパズルが多く遊ばれている理由の一つにこの最小性があると思います。

f:id:naan11235813:20211224035722p:plain
ゲーム「きららファンタジア」のカードを 4x3 に分割したスライドパズル「千矢スライドパズル」もある。難しい

解き方

「あほ」もしくは「くさ」のピースは常に存在するので、存在するほうを取ってきてこれを基準に考えます。以下では「くさ」をベースに考えますが、「あほ」しか存在しない場合は左右反転して考えてください。

f:id:naan11235813:20211224041258p:plain
初期盤面

くさを作る

しばらく、あほや茜ちゃんは無視して、「くさ」を正しくすることに注力します。

f:id:naan11235813:20211224040433p:plain
くさ
こうなると吉です。

向きの正しいくさ

次のようなくさがすぐに作れるとき、ラッキーです。このようなくさができればこれを回す(左2上右2下 を繰り返す)ことで正しいくさを作ることができます。

f:id:naan11235813:20211224040735p:plain
向きの正しいくさ

そうでないくさができているような場合、少し面倒です。

向きの正しくないくさ

そうでないくさがある場合、多少頑張る必要があります。

f:id:naan11235813:20211224041028p:plain
向きの正しくないくさ
今回の初期盤面は向きの正しくないくさです。 解決法ですが、いずれの正しくないくさも(回転させるなどして)左上に持ってきて、これをします。
f:id:naan11235813:20211224041503p:plain
解決法
向きが正しくなりました。

残り

あとは回して、

f:id:naan11235813:20211224041625p:plain
回転してくさを正しい位置に
くさ以外を動かすと解けました。
f:id:naan11235813:20211224041721p:plain
右4つを回す
くさ以外をいくら回しても正しくならない場合、不成立盤面です。

速く、短く解く

上の解き方では23手かかっています。 が、この盤面の最短手数は17手です。 この節では最短手数を出すコツについて話します。

f:id:naan11235813:20211224041911p:plain
最短手順

揃える手順に上のものを採用したとしても「あほ」から揃えるか「くさ」から揃えるか、あるいは「(頭)あ」や「く(頭)」などから揃えることもできるなどの選択肢があります。この中で最も短くなりそうなものを選んで打つのが得です。

また、同じ組から揃え始めるとしても向きの反転を修正する方法は複数あるので、それのどれを選ぶか(他のピースの状態が綺麗になるものを選ぶといいことが多いです)で手数が短くなるかが決まります。

この取捨選択が高速になるとあほくさスライドパズルが高速に解けるようになります。 タイピング速度やスレッドを開くのにかかる時間もありますが、最短がn手の盤面をn秒以内に解けると「速く解けたな」という気になります。

後半雑じゃないか?数やって直感を鍛えよう

どんなスライドパズルも最後に残るのは2x3盤面であることが多いと思うのでここを高速にするとスライドパズルが高速に解ける場合とそうでない場合があるぞい


  1. 1\times n は空きマスを正しい場所に動かすだけで解け、2\times 2 はぐるぐる回しているだけで解けます。