スライドパズルとはこんなヤツである。
15パズルとか言われているアレである。 プログラム的には4×4である必要はないので、スライドパズルと呼んでみた。 プログラミングをある程度勉強した人にはちょうどいい練習問題と思う。 中級者の中には1日で作れる人もいるだろう。上級者だと1日あれば画像が動いてたりする。
プログラミング技術としてはいろいろな要素がある。 たとえば、まず「どうやってタイルの移動を表現するか？」である。 大きくふたつの方法があり、ひとつはタイルの中身を書き換える方法、もうひとつはタイルそのものを移動する方法である。 前者はこんな感じ。
タイルを動かす場合、数字を消して、マーカーで書き直す。
JavaScriptで言えば、innerHTMLを書き換える。
一方、タイルそのものを移動する方法はこんな感じ。
タイルを動かす場合は数字の書いてある紙を文字通り「動かす」。
JavaScriptでは、たとえば、positionを適当に設定しておいて、topやleftを適当に書き換える。
どちらが楽かと言えば、当然前者の方が楽である。
ホワイトボードとマーカーさえあれば実装できるし（違う）。
ただ、前者には決定的な欠点があって、アニメーションができない。
これはリアル盤面を見れば納得だろう。
後者はtopなんかをスクリプトで書き換えればアニメーションが可能だし、なんならCSSを1行書くだけで勝手にアニメーションする。
上にあるサンプルもCSSでアニメーションしている。
「アニメーションする」という要件がある場合、前者の方法である程度作り込んでしまうと、「さてアニメーションを実装するか」となった段階で困ってしまう。 先を見越した設計は大事である。
上の例は必ず解けるようになっているが、適当にシャッフルしているとある一定の割合で「解けない」盤面ができる。 詳しいことは検索すれば出てくる。 「置換で見る『14-15パズル』の不思議」あたりが詳しくて分かりやすい。 結論だけ書くと、次のふたつの操作に必要な回数
前者の回数は揃える時に「ズル」をしてもよい、ということだ。 ただし、自分自身との入れ替えは禁止である。 この条件ならば左上の1から順に『入れ替え』て埋めていけばいいので、計算するのは簡単だろう。 後者の回数はわざわざ動かす必要はなくて、現在の空き位置と最終的な空き位置の間にある、横方向と縦方向のタイル数を足せばいい。 上の絵の状態で空き位置が「10」の場所にあったなら、横方向に2枚分、縦方向に1枚分動かす必要があるから、移動回数は3だ。
条件がわかったところで、世の中のパズルを見るとだいたいは
に分かれる。
最初のは運が悪いと解けない（確率的には半分の配置は解けない）。 「〇秒以内に解けたら〇〇をプレゼント！」なんて場合にはクレームモノである。
2番目は絶対に解ける状態にしかならないので検証の必要はないが、盤面がゴチャゴチャになるまでにある程度の回数が必要だ。 16セルくらいなら大したことないが、セル数が増えると飛躍的に増大することが予想できる（解くのも大変だが）。
3番目がまっとうな実装と思うが、まず、実は再シャッフルする必要はない。 偶奇が合えばいいのだから、合っていなかったらひと組だけ入れ替えればいい。 このとき、空き部分と入れ替えてしまうと、空き部分の偶奇も反転してしまうので、空き部分ではない2枚を選ぶ必要がある。
たとえば1と2の位置を入れ替えることにして、1が空白なら入れ替えの対象を5、2が空白なら6に変更すればいい。 パズルは2×2の大きさがないと成立しないので、大きさを自由に設定できるようにした場合でも、意味のあるパズルならこの位置のタイルは必ず存在している。 こういう検討も大事である。
次が検証方法だが、「シャッフル」と『入れ替え』と聞いて何か閃いた人はいないだろうか。 そう、「入れ替え」を使ったシャッフルの方法がある。 「Fisher-Yates法」と言われているもので、シャッフルアルゴリズムを勉強した人なら、名前は知らなくても方法は知ってる人が多いだろう。
簡単に説明すると、シャッフル対象の配列の前の方を「シャッフル済み」、残りを「未シャッフル」の部分と分けて、未シャッフルの部分から乱数でひとつ要素を取り出し、その要素を未シャッフル部分の先頭と「入れ替え」、入れ替えられた要素は「シャッフル済み」の方にくっつける。 初期状態ではすべて未シャッフル（つまり整列した状態）であり、1回入れ替えるごとにシャッフル済みの要素がひとつ増え、未シャッフルの要素が減っていく。 要素がN個あればN-1回だけ乱数を引けばシャッフルが完了している。
いくつかバリエーションはあるが、まぁ言葉で説明するより適当に検索して図を見た方がよいだろう。 もっと簡単に言えば、ビンゴで箱から数字の書かれた球を取り出して、一列に並べているのと同じである。 箱が「未シャッフル」、並べたものが「シャッフル済み」である。 これで数字は重複せず、順番はランダムになっているだろう。
で、よく考えてみると「入れ替えて揃えている」部分は、Fisher-Yatesシャッフルの逆手順だということが分かる。 このシャッフル方法では自分自身との入れ替えになった場合（上の説明だと未シャッフル部分の先頭要素が選び出された場合）でも特別扱いしないのだが、パズルの検証の場合はこの回数は数えてはいけない。 それさえ注意すれば、実はシャッフルが終わった時点で、完成に必要な入れ替え回数は判明している。 あらためて検証のために数える必要はないわけだ。
あとはふたつの回数の偶奇を調べて、一致していなければタイルをひと組入れ替えればいい。 技術者は考えてなんぼ。 ちょっとしたことを閃くかどうかが大切なこともある。 組み込み関数に頼り切りでアルゴリズムを知らない人はそもそも気づくこともないだろう。 車輪の再発明は避けたいが、アルゴリズムの勉強は大事である。
先のサンプルはこれをほぼ忠実に実装している（インラインフレームになっているので、ソースはブラウザのメニューから持っていってください）。 タイルが2次元に並んでいるのでシャッフル時に入れ替え対象セルを選ぶのが少し面倒で、未シャッフル部分の枚数で乱数を発生させ、それをセルの座標に変換する必要がある。
回数は真面目には数えてなくて、偶奇の一致だけ分かればいいので、parity変数を0・1ひっくり返すだけにしている。
^=はXORである。
念のため。
先のコンソールでは偶奇の計算結果をコンソールに出力している。
1と表示されていたら、あぁ、シャッフル後にひと組入れ替えたんだな、と思っていただければ。
あとは、クリックされた時に動かせるかどうかの判定で変なことをやっている。 普通はif文を4つ並べると思う。 この4つのif文が同じような形をしていて面倒臭いのでこう書いてみた。 この書き方がいいかと言われると、同じことの繰り返しは避けられるが、見てすぐに理解できるコードにはなっていないので、説明はしないことにする。
配列をもうひとつ使って良いのならもう少し楽に実装できて、1次元配列にタイルの「もと」を作っておき、乱数で選び出して盤面のセルに並べればよい。 先ほどの「ビンゴ」の例に近い。 下の例では配列先頭から要素を取り出したあとに先頭の要素を取り除いてしまい、乱数の発生の計算を簡単にしている。
クラスの書き方とかは好みの問題だと思うので突っ込まんといてw
15 Jan 2023: 自由なサイズで生成するフォームを追加
09 Jan 2023: 初稿
Copyright (C) 2023 akamoz.jp
$Id: slide-puzzle.htm,v 1.8 2023/01/16 16:03:40 you Exp $