15 パズルの問題を生成する

paiza オンラインハッカソンというイベントで、15 パズルを解くプログラムの作成に挑戦してみました。イベントの公式サイトはこちらです。
Rena and Minami International Programming Competition |Paiza Online Hackathon 5

イベントでは、あらかじめ決められた 5 種類の盤面を対象にして、それらを解くのに要した手数の短さを競う形式になっています。イベントの性格上、問題を固定しているのだと思いますが、実装したプログラムの動作を確認したり性能を評価したりするためには、イベントで用意された盤面だけではなく、より多くの盤面を解かせてみたいところです。

そこで今回、15 パズルの問題をランダムに生成するプログラムを PHP で実装してみました。以下のように書けます。プログラムを実行すると、解ける問題をランダムに一つ生成して、オンラインハッカソンの入力フォーマットに合わせた形で出力します。

<?php
function main() {
    $problem = range(0, 15);
    shuffle($problem);
    if (!isSolvable($problem)) {
        $problem = flipLR($problem);
    }
    printProblem($problem);
}

function isSolvable(array $problem) {
    $i = 0;
    while (!is_null($n = array_shift($problem))) {
        if ($n > 0) {
            $i += count(array_filter($problem, function ($m) use ($n) {
                return $m != 0 && $m < $n;
            }));
        } else {
            $i += intval(count($problem) / 4);
        }
    }
    return $i % 2 == 0;
}

function flipLR(array $problem) {
    return array_map(function ($i) use ($problem) {
        return $problem[$i];
    }, [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12]);
}

function printProblem(array $problem) {
    foreach ($problem as $i => $n) {
        printf("%s%s", $n ?: '*', $i % 4 < 3 ? ' ' : "\n");
    }
}

main();

15 パズルの問題生成で難しいのは、適当な盤面を与えたときに、それが解ける問題かどうかを判定することです。ウェブで調べてみたところ、これは簡単に判定可能だということが分かり面白かったので、紹介します。下記のウェブページに判定方法が記載されています。
15 Puzzle -- from Wolfram MathWorld

以下の盤面を例にして、具体的に説明します。

10	8	4	14
	15	12	13
7	11	6	1
5	9	2	3

まず、この盤面の数字を左から右、上から下の順に一直線に並べます。このとき空白のマスは無視します。次のようになります。

(10, 8, 4, 14, 15, 12, 13, 7, 11, 6, 1, 5, 9, 2, 3)

このように並べた状態で、それぞれの数字について、自分より右側に、自分より小さな数字がいくつあるかを数えます。先頭の 10 について調べると

(8, 4, 7, 6, 1, 5, 9, 2, 3)

の合計 9 個、次の 8 について調べると

(4, 7, 6, 1, 5, 2, 3)

の 7 個、その次の 4 について調べると

(1, 2, 3)

の 3 個、といった具合です。これを最後の数字まで続けて、すべてを合計します。今回の例では

9 + 7 + 3 + 10 + 10 + 8 + 8 + 5 + 6 + 4 + 0 + 2 + 2 + 0 + 0 = 74

と求まります。

次に、元の盤面で空白のマスが何行目にあったかを調べて、この数字に足し合わせます。今回の例では 2 行目に空白があったので、

74 + 2 = 76

となります。

こうして得られた数字が偶数なら、その 15 パズルは解けます。奇数なら解けません。

何とも不思議な話ですが、以下のページでは、この方法で判定できる理由が丁寧に説明されています*1。空白のマスを上下左右のいずれかに動かす操作を考えると、左右の移動では数字は変わらず、上下の移動では数字は必ず偶数だけ変わる (大小関係による数字の合計が奇数だけ変わり、空白の行番号が 1 変わるので、全体としては偶数だけ変わる) ということです。解けている盤面の数字は偶数なので、奇数の盤面からいくら空白を動かしても、解けることはありません。
Solvability of the Tiles Game

さて、ウェブページにも以下のように記載されているとおり、これは「奇数の盤面が解けない」ことの証明にはなりますが、「偶数の盤面が必ず解ける」ことの証明にはなっていません。そのためには、偶数の盤面同士はお互いに行き来できることを示します。

So you have shown that all solvable states have the stated property. But could there be some unsolvable states that have it too?

これに関しては、次のウェブページの説明が参考になります。このウェブページでは、決まった手順に沿って 15 パズルを解く方法が具体的に説明されています。まず上半分を揃え、次に左下の 4 マスを揃え、最後に右下の 4 マスを揃えるという手順になっています。
About the 15 Puzzle

このウェブページの説明で、左下の 4 マスを揃えるところまでは、解ける問題でも解けない問題でもまったく同じ手順で進められます。左下の 4 マスが揃った時点で、右下の 4 マスに 11, 12, 15, 空白が残った状態になっています。ここから空白を適当に動かして 15 を正しい位置に持っていけば、どんな盤面からスタートしても、必ず以下のどちらかに到達できます。

3 行目の 3, 4 列目に 11, 12 の順番で入っている状態 (解けている)

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

3 行目の 3, 4 列目に 12, 11 の順番で入っている状態 (解けていない)

1	2	3	4
5	6	7	8
9	10	12	11
13	14	15

ここで先ほどの解けるかどうかを判定する数字を計算してみると、解けている状態は偶数の盤面、解けていない状態は奇数の盤面になっています。整理すると

• どんな盤面からスタートしても、上記のどちらか片方の盤面に到達できる
• 偶数の盤面から奇数の盤面には到達できない
• 解けていない盤面は奇数の盤面である

となり、したがって、どんな偶数の盤面からスタートしても必ず「解けている」方の盤面に到達できることが言えます。

冒頭のプログラムでは、ランダムに生成した盤面が解けるかどうかを isSolvable 関数で判定し、解けない問題だった場合には flipLR 関数で左右を反転します。盤面の左右を反転させると数字の偶奇が入れ替わるので、解けない問題の左右を反転させたものは解ける問題になります。

*1:最初に示したウェブページにも、このことを証明した論文への参照がありますが、論文の証明は私には少し難しく、こちらのウェブページの説明の方が簡単に理解できました。