すのものの「15 パズルを解く C プログラム」

このページは，英語で書いた a C program solving the 15 puzzle の日本語訳として置いたもので， 15 パズルを解く C プログラムを提供するものだったが， 検索で上のほうにくるようになったので， 実用的な解き方を求めてきた人をがっかりさせないよう， それをここに記しておくことにした。

15 個のコマを下のループに沿って動かす。

↓←↓←
↓↑←↑
↓→↓↑
→↑→↑

ゲームの目的を，このループに沿って 1, 2, 3, ..., 15 と並べること，に取り換えてもよい。 （仮の番号をコマの上にはり，目的を達成してからそれをはがせばよい。）

このループに沿って 15 個のコマを動かしている限り，何も変わらない。

112↓←
 9←↑
↓→↓↑
→↑→↑

上のようになったとき，「9 を左に動かす」という， 例外的な動きが考えられる。 もしもこれを実行すると，9 は 11 と 2 とを飛び越えることになる。

（これが可能なところは，ほかに 5 か所がある。どこで考えても，同じである。）

これを，「飛び越えられる二つのコマのうち少なくとも片方が， 飛び越えるコマよりも大きければ，飛び越す」というルールの元で，実行する。 ただし，「1 は飛び越えてはいけない」「1 を飛び越えてはいけない」 というルールも追加する。

すると，何も考えずにこれをくり返してゆくうち， コマは 1, 2, 3, ..., 15, または 1, 3, 2, ..., 15 の順に並ぶ。

（次の行から， a C program solving the 15 puzzle の日本語版が始まる。）

このページを読む前に， 《すのものの「15 パズル（およびその拡張）を解く」》 と 《すのものの「風変わりなソートアルゴリズム（15 パズルに関連）」》 をお読みいただきたい。

15 個のコマを下のループに沿って動かす。

↓←↓←
↓↑←↑
↓→↓↑
→↑→↑

ゲームの目的を，このループに沿って 1, 2, 3, ..., 15 と並べること，に取り換えてもよい。

マスと配列 a[ ] の添え字との対応は以下の通りとする。 

 a[1]  a[2]  a[5]  a[6]
 a[0]  a[3]  a[4]  a[7]
a[15] a[12] a[11]  a[8]
a[14] a[13] a[10]  a[9]

i を 0, 2, 4, 8, 10, 12 のどれかとする。 もしも a[i] が空いている場合， 次の例外的な手を指すことができる。 すなわち，a[i+3] を水平に動かし， a[i+1] と a[i+2] を飛び越させる。 この手は，a[i+1] と a[i+2] の少なくとも片方が a[i+3] より大きく， コマ 1 がこれら三つのコマに現れていないときにおこなう。 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 16

void initialize(void);
void shuffle(void);
void show(void);
void loop(void);

int a[N];
int z;          /* コマ 0（＝空白）の位置 */

int main() {
    initialize();
    shuffle();
    loop();
}

void initialize(void) {
    int i;

    for (i = 0; i < N; i++) {
        a[i] = i;
    }
}

void shuffle(void) {    /* コマをシャッフル */
    int i;

    srand((unsigned)time(NULL));

    for (i = N; i > 0; i--) {
        int tmp;
        int r;

        r = rand() % i;
        tmp = a[i-1]; a[i-1] = a[r]; a[r] = tmp;
    }

    for (i = 0; i < N; i++) {
        if (a[i] == 0) {
            z = i;
        }
    }
}

void show(void) {       /* 配列を印字 */
    int i;

    for (i = 0; i < N; i++) {
        if (a[i] == 0) {
            printf("   ");    /* 0 means the empty square */
        } else {
            printf(" %2d", a[i]);
        }
    }
    putchar('\n');
}


void loop(void) {
    int i;

    for (  ;  ;  ) {
        show();
        switch (z) {
            case 0: case 2: case 4: case 8: case 10: case 12:
                     if (a[z+1] != 1 && a[z+2] != 1 && a[z+3] != 1 && (a[z+1] > a[z+3] || a[z+2] > a[z+3])) {
                         a[z] = a[z+3], a[z+3] = 0; z = z+3;
                     } else {
                         a[z] = a[z+1], a[z+1] = 0; z = z+1;
                     }
                     break;
            case 15: a[15] = a[0], a[0] = 0; z = 0; break;
            default: a[z] = a[z+1], a[z+1] = 0; z++;
        }

        for (i = 4; i < N && a[i] == i; i++) {
            ;
        }
        if (i == N && a[0] == 0 && a[1] == 1) {
            show(); break;
        }
    }
}

このプログラムは，次のどちらかを表示して止まる。 

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

または 

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