a C program solving the 15 puzzle

Before reading this page, please read «a simple proof on the solvability of the 15 puzzle (and the extended ones)» and «a strange sort algorithm related to the 15 puzzle (and the extended ones)».

Slide 15 pieces along the loop shown below.

We may replace the aim of the puzzle by the following: Arranging the pieces 1, 2, 3, ..., 15 along this loop.

The correspondence between the squares and the indices of the array a[ ] is as follows.

 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]

Assume that i is one of 0, 2, 4, 8, 10, 12. If a[i] is empty, then, we may apply an exceptional move, i.e. a[i+3] moves horizontally leaping a[i+1] and a[i+2]. This move is applied if at least one of a[i+1] and a[i+2] is larger than a[i+3] and the piece 1 does not appear in these three pieces.

#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;          /* index of the piece 0 (= empty) */

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

void initialize(void) {
    int i;

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

void shuffle(void) {    /* shuffle the pieces */
    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) {       /* print the array */
    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;
        }
    }
}

This program ends after showing one of the following.

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

or

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