15パズルってご存知ですか？
知ってても知らなくても15パズルの話をするんですが。はい。
あと、本記事は数学的な厳密な証明はせずに感覚的にエイッヤッ～とやっているので正確じゃないです。
でもたぶんあってる。はい。
これ
簡単に言いますと、1マス空いている4×4のマスでセルを移動させながら、 左上から順に数字を並べるパズルです。
アルゴリズムも単純でプログラミング初心者でも割と簡単に実装できるゲームです。
と思っていた時期が私にもありました。
15パズルの欠陥
というのは半分冗談で、ゲームのアルゴリズム自体は別に難しくないです。 問題はこの15パズルというゲームが持つ本質的な欠陥についてです。
端的に言うと、絶対に完成できない形が存在します。
これが完成形です。
そして、次が完成不可能な形の一例です。
このように完成形から1つだけ入れ替えた形は、どれだけパズルをグルグルまわしても 絶対に完成形にはならないことが知られています。
証明とかは省略します、というより私が知りません。昔の偉い人がそう言ったので信じます。
これをベースに、完成できる条件とは何かを考えていきます。
完成可能条件
先ほどの、完成形から隣接する2つのセルを1度だけ入れ替えたものを、完成形からの距離D=1と呼ぶことにします。
D=1状態が完成不可能なので、D=2の形について考えます。
D=2はD=1からもう一度隣接するセルを入れ替えた形の集合です。
D=2はD=1のところと同じ2セルを入れ替えた形も含むので、つまり完成形もD=2に含まれます。
ということは再帰的にD=2nは完成形を含むため、距離が偶数なら完成可能、奇数なら完成不能です。
(数学徒からは全然証明になってないので受精卵から人生やりなおせと言われそうですが、私は厳密な証明できないのでこの記事執筆後、受精卵からやり直します)
では次のような斜めの2つを入れ替えた形に距離を考えます。
完成形から順に入れ替えを手順を追っていきます。
# D=0 9 10 11 12 13 14 15 __ ↓ 14, 15を入れ替え # D=1 9 10 11 12 13 15 14 __ ↓ 10, 15を入れ替え # D=2 9 15 11 12 13 10 14 __ ↓ 14, 10を入れ替え # D=3 9 15 11 12 13 14 10 __
つまり、斜めのセルの入れ替えはD=3です。つまり完成形からは奇数距離です。
このように拡張していくと、任意の2つのセルの入れ替えは奇数距離であることが分かります。
ここから分かることは、任意の入れ替えが奇数距離であるため、入れ替え回数が偶数回なら偶数距離を保てるということです。
つまり、解ける15パズルとは、完成形から偶数回の「任意の2セル入れ替え」で得られる集合に含まれる形です。
なので、ランダムに初期状態を生成すると1/2の確率で完成不能なパズルができるということですね。。。。
おしまい
二度とVBなんか書かねぇ
