いずれ子供が大きくなればスライドパズルで遊ぶだろうから、そのときに舐められないようにスライドパズルの必勝法を書く。
ここでいうスライドパズルとは以下のようなもの。 8 パズルとか 15 パズルなどとも呼ばれる。
具体的には 群論 を用いた理論的なアプローチと A* アルゴリズムを用いた最適化のアプローチの 2 つについて説明する。
群論を使う
「そもそも、そのスライドパズルは完成させらるのか？」
一度思いつけばそれ以外のことを考えることが難しいほどに、スライドパズルは群論の良い example になっていた。ルービックキューブよりもわかりやすい。
群論の概念を用いると面白いのは そもそもそのスライドパズルを完成させられるのか？ という疑問に答えてくれること。
例えば、以下のように 2 と 1 だけが入れ替わった状態から、上手にパネルをスライドさせて完成した状態に持っていくことはできるか？
2 1 3
4 5 6 7
8 9 10 11
12 13 14 15
答えは「不可能」。つまりどんなにパネルを動かしても永遠に完成しない。
こういうことがあらかじめ分かってしまうところが、こうした理論的なアプローチの面白いところ。
完成させることができるかを調べる方法
以下、簡単のため 8 パズルで考える。以下のように完成形のスライドパズルのパネルそれぞれに番号をつけて考える。ここで 0 は空白を意味している。
0 1 2
3 4 5
6 7 8
つまりベクトル (0, 1, 2, ..., 7, 8) が一つの状態と対応している。
パネルを動かす行為はこのベクトルにある 2 つの成分を入れ替えることを意味するから、自然と 9 次の対称群として考えることができる。
よく知られたことに、対称群の任意の置換は互換の積で表現できる。
さらによく知られたことに、そして群論を勉強したときの最初の面白いところでもあるけれど、互換の積の表現方法は一意でないものの、その 互換の数の偶奇は不変 である。
この置換の偶奇が後にポイントになるので、まずはその調べ方について述べる。
とはいってもやり方は簡単で、少なくとも一つの互換の積の表現を見つければよいだけ。
そのためのアルゴリズムとしては、例えば以下のようなバブルソートっぽいものを考えればよい。あるいは転倒数を数えるだけでも OK。
def count_swap(vector):
count = 0
for i in range(len(vector)):
for j in range(i + 1, len(vector)):
if vector[i] > vector[j]:
count += 1
return count
さて、今度は空白、つまり 0 の移動について考える。
スライドパズルでパネルを操作する行為は、対称群として考えれば互換に相当するし、また空白の位置に注目すれば、それは空白の移動、とみなすことができる。
操作を繰り返して完成状態に持っていけたとする。その回数を $N$ とする。この $N$ は、初期状態から完成状態に互換の積の数であれば、 空白が移動した回数にもなる。
唐突だが、以下のようなチェスボードを考える。
(Wikipedia のチェスボードのページから画像を引用した https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%82%B9%E3%83%9C%E3%83%BC%E3%83%89)
この濃い茶色のマスに駒があって、特別ルールでこの駒は上下左右に1マスずつしか動けないとする。
さてこのとき「偶数回だけ動いて」と言われたら、この駒の到着地点に共通して言える特徴はなにか？
実際にイメージしてみるとわかるが、 濃い茶色のマスから偶数回動かしてたどり着けるところは濃い茶色のマスだけである。また同様に考えると、奇数回動かしてたどり着ける場所は薄い茶色のマスだけである。
これは逆も言える。「自分が今いるマスの色と同じ色のマスに行きたいならば、必ず偶数回動かすこと」「自分が今いるマスと異なる色のマスに行きたいならば、必ず奇数回動かすこと」
これを マンハッタン距離 という言葉を使って言い換える: 「自分が今いるマスの色と同じ色のマスに行けるかは、その行き先のマンハッタン距離の偶奇によって決まる」
スライドパネルの話に戻る。初期状態から完成状態に持っていったときの操作は、互換の積の数であり、また空白の移動回数であった。そしてその数の偶奇と、初期状態から完成状態それぞれの空白の場所の間のマンハッタン距離の偶奇は、一致していないとおかしい。
ということで、以下のような主張が成立する:
「初期状態から完成状態に至る(なにか一つの)互換の積の数の偶奇と、空白の初期状態の位置と本来あるべき位置とのマンハッタン距離の偶奇が一致していれば、そのスライドパズルは完成させることができる」
ちなみに、初期状態から完成状態の置換すべての集合を考えたとき、その置換の偶奇によってきれいに集合を二分割できる。したがって、スライドパズルをバラバラにしてテキトーにパネルを当てはめると、 1/2 の確率で解けないパズルができあがる。
完成までの手順
さて、上の方法で完成させる方法の存在性が保証されているとする。
このとき、具体的どのような手順でスライドさせれば完成状態に持っていくことができるのか？
面倒になったので、以下の解説のポイントだけ書く。
- 任意の 3 つのパネルを入れ替える操作(巡回置換)の存在性を構成的に示すことができる
- この巡回置換を使えば、任意の 2 つの互換の積を表現できる
- ところで、偶置換は偶数個の互換の積で表現できる
- → 偶置換ならば、 3 つのパネルを入れ替える操作で完成状態に持っていける
なお、初期状態が奇置換ならば、一つだけスライドを動かして偶置換からスタートしたことにすればよい。
この手順ならば、必ず完成形に持っていける。これが必勝法。
A* アルゴリズムを使う
「迷路の壁に沿って歩けば必ずゴールにたどり着ける、けどだるい」というかんじ
上の群論的アプローチは確実に完成させられるのだけど、操作としてはかなり冗長。「迷路の壁に沿って歩けば必ずゴールにたどり着ける、けどだるい」というかんじと似ている。
もっと小さい操作回数で完成状態に持っていけないか？ という問題を考える。
これは 最短経路問題 として考えることと同じ。
ちなみに、素朴に全探索したら、ベクトルの次元を $N$ とすれば $O(N!)$ となるため、 15 パズルの $N=16$ を考えると絶対終わらない。効率の良い探索方法を見つけなければならない。
ダイクストラ法
パネルの状態を node、スライド操作による変換を edge ととらえると、巨大なグラフとみなすことができる。さらに、パネルをスライドさせる 1 回の操作を各 edge の weight として考えれば重み付きグラフになる。
この問題設定ならば、ダイクストラ法がそのまま適用できる。
と思ったので、最初にダイクストラ法で実装して試してみた。
このグラフは、 edge と node の数のオーダーがあんまり変わらない($|E| = O(|V|)$)疎グラフにある。たしかにある node から生えてる edge の本数はたかだか 4 本だ。
したがって、ダイクストラ法の中で未探索 node から最小コストの node を選択したりするアルゴリズムにヒープを用いることにした。そうすれば、素朴に線形探索するときに比べて計算量は $O(|V|^2)$ から $O(|E| \log |V|)$ になる。
まず 8 パズルまでならば、ダイクストラ法でいけた。ダイクストラ法は全探索なので、その解が最小のステップ数であることが保証されている。たかだか $|V| = 9! = 362880$ 回の探索なので、まだまだいける。
同じ実装法で 15 パズルをやったけれども、これは一晩かけても終わらなかった。それはそうで、 $|V| = 16! \approx 10^{13}$ なので、やっぱ時間はかかる。
なので、必ず最小のステップになることを諦めた。
その代わりに、 なるべく最小のステップになる操作 を見つけることにする。つまり最適化問題として捉え直す。
A* アルゴリズム
A* アルゴリズムについては Wikipedia 以上の知識を持っていないが、それでも説明すると、ざっくり言えばダイクストラ法 + ヒューリスティクス。
ダイクストラ法とは違い、全探索ではなく、解を見つけたらそこでプログラムをストップさせる。
weight を比較するときに、スタート地点からのコストと、ゴールからの「遠さ」をヒューリスティック関数として定義し、それらを同時に考える。今回の場合、その node からゴールの node までの、パネルとしてみたときのマンハッタン距離をヒューリスティック関数にした。
それを実装したのが以下。
これをすると、 15 パズルが解けた。それが以下の gif. 解を見つけるのにだいたい 2 分くらい。ただし、この時間は安定しない。もっと長い場合もあった。
54 ステップ。
本質的ではないが、上の gif を作ったときに書いたコード。
A* アルゴリズムのわかってないところ
上のコードは Wikipedia を見て実装した。
https://ja.wikipedia.org/wiki/A*
これの 7.2 の 3 番目の「 m が Close リストにある場合〜」の文。
自分の実装を完成させた後に ChatGPT に聞いたのだけど、この 3 番目の Close リストからまた Open リストに移すのは普通は行われてません、という風に怒られた。怒られたというのは本当で、提案してきたコードに対して Close リストから Open リストに移す操作もちゃんと入れてと指示しても、色々言い訳をつけてコードをそもそも書き直してすらこない。ちょっと頑固。
たしかに、ダイクストラ法ではこんな操作はしない。むしろ、しなくても良いというが理論的に保証されていて、それが理由で計算量を下げられている。Close リストから Open リストに移す、ということをやってしまうとスタックしそうなかんじもして、適度に breaking a tie しなきゃいけない気もする。でもそういう記述があるようでもない。
このあたりはちゃんとわかってない。
おわり