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

#define M 4     /* 行の数 */
#define N 4     /* 列の数 */

void init(void);
void shuffle(void);
void show(void);
int find_zero(void);
void loop(void);

int a[M*N];

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

void init(void) {       /* 初期化 */
  int i;

  for (i = 0; i < M*N; i++) {   /* 配列を初期化 */
    a[i] = i;
  }
}

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

  srand((unsigned)time(NULL));  /* 乱数の種を初期化 */

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

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

void show(void) {       /* 画面出力 */
  int i;

  for (i = 0; i < M*N; i++) {
    if (a[i] == 0) {
      printf("  ");     /* 0 は空白で示す */
    } else {
      printf("%2d", a[i]);
    }
    if (i % N == N - 1) {
      printf("\n");
    } else {
      printf(" ");
    }
  }
}

int find_zero(void) {   /* 0 の位置を探す */
  int i;

  for (i = 0;        ; i++) {
    if (a[i] == 0) {
      return i;
    }
  }
}

void loop(void) {       /* メインのループ */
  int zero, input;

  for (  ;  ;  ) {              /* 無限ループ */
    show();
    zero = find_zero();
    printf("2 ... 下へ，4 ... 左へ，6 ... 右へ，8 ... 上へ，0 ... 終了> ");
    scanf("%d", &input);
    if (input == 2) {           /* 下へ */
      if (zero >= N) {
        a[zero] = a[zero - N];
        a[zero - N] = 0;
      } else {
        printf("動かせません.\n");
      }
    } else if (input == 4) {    /* 左へ */
      if (zero % N != N - 1) {
        a[zero] = a[zero + 1];
        a[zero + 1] = 0;
      } else {
        printf("動かせません.\n");
      }
    } else if (input == 6) {    /* 右へ */
      if (zero % N != 0) {
        a[zero] = a[zero - 1];
        a[zero - 1] = 0;
      } else {
        printf("動かせません.\n");
      }
    } else if (input == 8) {    /* 上へ */
      if (zero < M*N - N) {
        a[zero] = a[zero + N];
        a[zero + N] = 0;
      } else {
        printf("動かせません.\n");
      }
    } else if (input == 0) {
      return;
    } else {
      printf("入力が間違っています.\n");
    }
  }
}