15パズルは何故解けないのか？

15パズルは誰でも知ってるだろう。プログラミングの練習がてらに誰もが一度は作ったことがあるかも知れない。しかし、右図の15パズルは解けない。

この問題は超古典であって、高木先生の「数学小景」にも載っている有名なものである。私は、これは誰でも知ってるものだとばかり思っていたが、先日うちのプログラマにあるゲームのための15パズルを実装してもらったとき、ゼンゼンわかってなかったので驚いた。

何故解けないのか、簡単に説明しておく。以下のスライドを参考にどぞ。

http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/text/14-15.pdf

あと、線形代数の教科書をお持ちなら行列式の定義のあたりを見て欲しい。「偶置換」と「奇置換」の説明が出てくる。

(スライドの要約)
15パズルのゴールを(1 2……14 15)とおく。右図の(1 2……15 14)はゴールを奇置換して与えられる。また、15パズルで、2箇所のピースを入れ替えると奇置換になる。奇置換は二度繰り返すと偶置換なる。そして、15パズルで空白ピースの移動は偶置換なのである。よって、初期配置がゴールを奇置換したものだと、空白ピースをいくら移動させても(偶置換を繰り返しても)決してゴールへは到達できない。

なんのことだかサッパリわからない人は、15パズルに偶数の状態と奇数の状態との二つがあると思えばヨロシイ。空白ピースの移動をさせてもこの状態は変わらない。だもんで、奇数の状態のまま、いくら空白ピースを移動させても偶数の状態にはならないということだ。

15パズルの問題を生成したい場合、解答図から、空白ピースをでたらめに移動させるという方法が採られる場合がある。これはこれでゲームのビジュアル的にはいいのだけど、そういう処理をはしょって、ともかく問題だけを生成したい、ということがある。

そのためには、奇置換(自分以外のピースとswapすれば奇置換になる)をカウントしていき、最終的に奇置換ならば、どこかのピースをさらに1回入れ替えれば良い。コードで示すと以下のようになる。

void swap(int& i,int &j){

    int t=i;

    i=j;

    j=t;

}
void make_16puzzle()

{

    const int n=16;

    // 15パズル(便宜上、数字は0〜14とする。15は空白ピース)

    int a[n];

    bool b=false; // 奇置換か？

    for(int i=0;i<n;++i) a[i] = i;

    for(int i=0;i<n-2;++i) {

        int r=rand()%(n-i-1);

        if (r!=0) { swap(a[i],a[r+i]); b=!b; }

    }

    if (b) swap(a[n-3],a[n-2]); // 奇置換なので最後のところで調整

    //    本当はここで初期配置と全く同じになっていないかはチェックしたほうがいい

}

補足。解けない15パズルのわかりやすいサイトを紹介してもらったので追記。
http://hp.vector.co.jp/authors/VA010128/math/puzzle/P15-1.html