動かして考えるパズル

駒や自分を動かして、ゴールをめざすパズルです。4つとも見た目はやさしいのに、「1手って何だろう」「どこまで先を読めばいいだろう」と考えはじめると、奥が深くなります。

渋滞パズル（このサイトの「渋滞パズル」）

すき間の少ない盤で、車をずらして赤い車を出口へ出します。車は向いている方向にしか動けません。 このサイトでは、1台を一度に何マス動かしても1手と数えます。40問の最短手数は、幅優先探索（近い局面から順に全部調べるやり方）で確かめました。 このサイトのプログラムで確かめた数字です（traffic-jam/engine.test.ts）。

この種類のパズルは、日本のパズル作家の吉原伸（1936〜2004）が考案したものが、1990年代に海外で発売されて広く知られるようになった、とされています。考案の時期は、1970年代とする資料と1970年代後半とする資料があり、はっきりしません。 駒をずらして目的の駒を出口へ出す遊びは、昔からある「箱入り娘」と同じ系統のパズルです。ただし、一方がもう一方の元になったと言えるほどの証拠はありません。

研究者は、この種のスライドブロックのパズルを、盤をいくらでも大きくした形で考えると、「解けるか」を決めるのがとても難しい問題の仲間（PSPACE完全）に入ることを示しました。 とはいえ、このサイトのような小さな盤なら、全部調べて最短を出せます。「難しい」と言いすぎないのも大切です。

すべる氷の床（このサイトの「すべる氷の床」）

氷の上では、止まりたいところで止まれません。壁か盤の端に当たるまですべり続けます。ゴールを通りすぎるだけではクリアになりません。止まれたときだけです。 このサイトでは、1回のすべりが1手です。

この仕掛けは、コンピューターゲームでよく見かけるパズルの型です。いつ、だれが最初に作ったかは、はっきり分かっていません。

解き方のコツは、「止まれる場所だけを数える」ことです。すべって止まる場所だけが、次の局面になります。 そうすると、ふつうの盤よりずっと少ない点を、順に調べればよくなります。24問の最短手数（2手から9手まで、3問ずつ）は、この考え方の幅優先探索で確かめました。このサイトのプログラムで確かめた数字です（ice-slide/engine.test.ts）。

箱押しパズル（このサイトの「箱押しパズル」）

倉庫の中を歩いて、箱を押して、全部の箱をゴールの位置まで運びます。箱は押せますが、引けません。ここが難しさのもとです。一度壁ぎわの角に押しこむと、もう動かせなくなります。 このサイトでは、歩くのも押すのも1マスで1手と数えます。12問の最短歩数（6〜16歩）は、幅優先探索で確かめました。このサイトのプログラムで確かめた数字です（box-pusher/engine.test.ts）。

このジャンルは、日本で1981〜82年ごろに生まれたとされています。 1997年にジョセフ・カルバーソンが、この種のパズルは「解けるかどうか」を決める問題として、とても難しい仲間（PSPACE完全）に入ることを示しました。 見た目は子どものおもちゃのようでも、コンピューター科学では最も難しい部類の問題です。もちろん、小さな盤なら、ふつうに解けます。

ライト反転（このサイトの「ライト反転」）

マスを押すと、そのマスと上下左右のあかりが反転します。全部消せばクリアです。3×3と5×5を選べます。 似た遊びは、1970〜80年代の電子玩具にもあった、と言われています。

ここには、数学が隠れています。 同じマスを2回押すと元に戻ります。しかも、押す順番は結果に関係しません。ですから、各マスは「押す」か「押さない」かの2つだけで考えられます。 このサイトのプログラムで、この2つの性質（2回押すと元に戻ること、順番を入れかえても同じこと）を確かめました（toggle-lights/engine.test.ts）。

0と1だけで、1+1=0になる世界の計算を使うと、盤面全体を連立方程式として解けます。2元体の線形代数と呼ばれる考え方で、1998年のアンダーソンとフェイルの論文でも紹介されています。

もっと手軽な解き方が、「上から順に消す」やり方です。一番上の行で押す場所を決めたら、2行目からは「真上のあかりを消す」押し方が自動的に決まります。 最上段の押し方は、5×5なら2の5乗で32通りしかありません。このサイトのプログラムは、この32通りを全部試して最短を調べ、問題の答えと一致することを確かめました。 3×3は、512通りの盤面すべてについて、別の方法（幅優先探索）で調べた最短と一致しています。

そして、5×5には全部は消せない盤面があります。たとえば、左上の角のあかりが1つだけ点いている盤面は、どう押しても消せません。これもテストで確かめました。

「1手」は、ゲームごとにちがう

• 渋滞パズル：同じ車を何マス動かしても1手。
• すべる氷の床：止まるまですべって1手。
• 箱押しパズル：1マス歩くたびに1手。箱を押す1マスも1手。
• ライト反転：1回押して1手。

数え方が変わると、「最短」の答えも変わります。「箱入り娘」で最短81手と116手の2つの数字が出てくるのも、同じ理由です。数字を見たら、まず「何を1手と数えているか」を確かめましょう。

どの作品も、ヒントは考え方から順に出ます。まずは、考え方だけ見て、もう一度自分で試してみてください。