Linux Programming

スライドパズル

今回は基本的な探索手法である「幅優先探索」を使って 15 パズルで有名なスライドパズルを解いてみましょう。なお、幅優先探索の基本は拙作のページ 経路の探索 で説明しています。基本的なことは、そのページをお読みください。

●パズルの説明

参考文献 1 によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。

       図 : 15 パズル

15 パズルは上図に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。

15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 8 までの数字を並べる「8 パズル」を考えることにします。

              図 : 8 パズル

15 パズルは 4 行 4 列の盤ですが、8 パズルは 3 行 3 列と盤を小さくしたパズルです。8 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、9! = 362880 通りあります。15 パズルや 8 パズルの場合、参考文献 2 によると 『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にしか移行できない』 とのことです。

上図 (2) は 7 と 8 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。このような性質を「偶奇性 (パリティ)」といいます。詳しい説明は拙作のページ Puzzle DE Programming 偶奇性 (パリティ) のお話 をお読みください。8 パズルの場合、完成形に到達する局面の総数は 9! / 2 = 181440 個となります。

●データ構造の定義

それでは、プログラムを作りましょう。下図に示すスタートから完成形 (ゴール) に到達するまでの最短手数を幅優先探索で求めます。

              図 : 8 パズル

8 パズルの盤面は配列を使って表します。盤面の位置と配列の添字の対応は下図を見てください。

           図 : 8 パズルの盤面

隣接リストの定義は次のようになります。

リスト : 隣接リスト

int adjacent[N][5] = {
  {1, 3, -1},       // 0
  {0, 2, 4, -1},    // 1
  {1, 5, -1},       // 2
  {0, 4, 6, -1},    // 3
  {1, 3, 5, 7, -1}, // 4
  {2, 4, 8, -1},    // 5
  {3, 7, -1},       // 6
  {4, 6, 8, -1},    // 7
  {5, 7, -1}        // 8
};

-1 で隣接リストの終端を表しています。

次は局面を表す構造体を定義します。

リスト : 局面の定義

typedef struct state {
  char board[N];
  int  space;
  struct state *prev;
} State;

名前は State としました。board は盤面を表す配列、space は空き場所の位置、prev は 1 手前の局面 (State へのポインタ) を格納します。ゴールに到達したら、prev をたどって手順を表示します。

盤面 board の操作には、string.h に定義されているメモリ操作関数を使います。下表にメモリ操作関数を示します。

実際に使うのはメモリの比較を行う関数 memcmp と、メモリをコピーする関数 memcpy です。memcpy は 2 つの領域に重複がない場合にのみ使ってください。重複がある場合の動作は未定義です。その場合は関数 memmove を使ってください。

●キューの定義

次はキューを定義します。

リスト : キューの定義

#define Q 181440

State buff[Q];
int front, rear;

キューの大きさは Q (181440) で、配列 buff がキューの本体です。キューの操作関数を下表に示します。

●同一局面のチェック

同一局面のチェックには二分探索木を使います。

リスト : 二分探索木

typedef struct node {
  State *st;
  struct node *left;
  struct node *right;
} Node;

今回は節 (Node) をそのまま使います。メンバ変数 st に局面を格納します。下表に二分探索木の操作関数を示します。

キューと二分探索木の操作関数は簡単なので説明は割愛します。詳細は プログラムリスト１ をお読みください。

●幅優先探索による解法

それでは幅優先探索のプログラムを作りましょう。次のリストを見てください。

リスト : 幅優先探索

void solver(char *start, char *goal)
{
  Node *root = NULL;
  root = insert_tree(init_queue(start), root);
  while (!is_empty()) {
    State *st = deq();
    if (memcmp(st->board, goal, N) == 0) {
      print_answer(st);
      return;
    }
    for (int i = 0; adjacent[st->space][i] != -1; i++) {
      char new_board[N];
      int x = adjacent[st->space][i];
      memcpy(new_board, st->board, N);
      new_board[st->space] = new_board[x];
      new_board[x] = S;
      if (!search_tree(new_board, root))
        root = insert_tree(enq(new_board, x, st), root);
    }
  }
}

関数 solver の引数 start がスタートの盤面、goal がゴールの盤面です。変数 root は二分探索木のルートです。root は NULL に初期化します。次に、init_queue で start の盤面を格納した局面を生成してキューに追加します。それを insert_tree で root に挿入します。あとは while ループで、ゴール (goal) に到達するまで探索を繰り返します。キューが空になり while ループが終了する場合、start は goal に到達できない、つまり解くことができなかったことになります。

まず、deq でキューから局面を取り出して変数 st にセットします。st->board が goal と等しい場合、ゴールに到達したので print_answer で手順を表示して処理を終了します。そうでなければ、駒を動かして新しい局面を生成します。動かせる駒の位置は空き場所の隣なので、隣接リスト adjacent[st->space] で求めることができます。動かす駒の位置を変数 x にセットします。

次に、元の局面 st->board を配列 new_board にコピーします。あとは、new_board[st->space] に new_board[x] を、new_board[x] に S (0) をセットします。これで新しい盤面を生成することができます。

新しい盤面を作ったら、同一局面がないか search_tree でチェックします。同一局面がない場合は、enq で盤面 new_board を格納する局面を生成してキューに追加します。そして、生成した局面を insert_tree で二分木 root に挿入します。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト１ をお読みください。

●実行結果

これでプログラムは完成です。それでは実行してみましょう。

$ clang -O2 eight.c
$ ./a.out
8 6 7 2 5 4 3 0 1 
8 6 7 2 0 4 3 5 1 
8 0 7 2 6 4 3 5 1 
0 8 7 2 6 4 3 5 1 
2 8 7 0 6 4 3 5 1 
2 8 7 3 6 4 0 5 1 
2 8 7 3 6 4 5 0 1 
2 8 7 3 6 4 5 1 0 
2 8 7 3 6 0 5 1 4 
2 8 0 3 6 7 5 1 4 
2 0 8 3 6 7 5 1 4 
2 6 8 3 0 7 5 1 4 
2 6 8 0 3 7 5 1 4 
2 6 8 5 3 7 0 1 4 
2 6 8 5 3 7 1 0 4 
2 6 8 5 3 7 1 4 0 
2 6 8 5 3 0 1 4 7 
2 6 0 5 3 8 1 4 7 
2 0 6 5 3 8 1 4 7 
2 3 6 5 0 8 1 4 7 
2 3 6 0 5 8 1 4 7 
2 3 6 1 5 8 0 4 7 
2 3 6 1 5 8 4 0 7 
2 3 6 1 5 8 4 7 0 
2 3 6 1 5 0 4 7 8 
2 3 0 1 5 6 4 7 8 
2 0 3 1 5 6 4 7 8 
0 2 3 1 5 6 4 7 8 
1 2 3 0 5 6 4 7 8 
1 2 3 4 5 6 0 7 8 
1 2 3 4 5 6 7 0 8 
1 2 3 4 5 6 7 8 0 
0.414

実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
最適化オプション : -O2

31 手で解くことができました。生成した局面は全部で 181440 通りで、実行時間は 0.414 秒かかりました。今回は同一局面のチェックに二分探索木を使いましたが、ハッシュ法だともう少し速くなると思います。興味のある方は試してみてください。

8 パズルの場合、最長手数は 31 手で、下図に示す 2 通りの局面があります。スタートの局面はその一つです。

      図 : 31 手で解ける局面

最長手数の局面は、幅優先探索を使って求めることができます。これはあとで試してみましょう。

●双方向探索

ところで、今回の 8 パズルようにゴールの状態が明確な場合、スタートから探索するだけではなくゴールからも探索を行うことで、幅優先探索を高速化することができます。これを「双方向探索 (bi-directional search)」といいます。

その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。

これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。

生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の探索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。

それではプログラムを作りましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な修正が必要になります。ここは、探索方向を示すフラグを用意することで、一つのキューだけで処理することにしましょう。局面を表す State に方向を格納するメンバ変数 dir を追加します。

リスト : 局面の定義 (双方向からの探索)

#define BACK 1
#define FORE 2

typedef struct state {
  char board[N];
  int  dir;
  int  space;
  struct state *prev;
} State;

スタートからの探索を BACK で、ゴールからの探索を FORE で表ます。双方向探索のプログラムは次のようになります。

リスト : 双方向探索

void solver(char *start, char *goal)
{
  Node *root = NULL;
  root = insert_tree(init_queue(start, BACK), root);
  root = insert_tree(init_queue(goal, FORE),  root);
  while (!is_empty()) {
    State *st = deq();
    for (int i = 0; adjacent[st->space][i] != -1; i++) {
      char new_board[N];
      int x = adjacent[st->space][i];
      memcpy(new_board, st->board, N);
      new_board[st->space] = new_board[x];
      new_board[x] = S;
      State *st1 = search_tree(new_board, root);
      if (st1 == NULL) {
        root = insert_tree(enq(new_board, x, st), root);
      } else if (st1->dir != st->dir) {
        print_answer(st, st1);
        return;
      }
    }
  }
}

スタートとゴールの局面を生成してキューにセットして、それらを二分木 root に挿入します。init_queue には探索方向を表す引数を追加しています。最初に、スタートの状態から 1 手目の局面が生成され、次にゴールの状態から 1 手目の局面が生成されます。あとは、交互に探索が行われます。それから、同一局面を見つけたとき、その局面の方向 dir を比較する必要があるので、search_tree の返り値を State * に変更しています。見つからない場合は NULL を返します。

駒の移動と局面の生成処理は幅優先探索と同じです。search_tree で同一局面をチェックします。見つけた場合、st1->dir と st->dir の値が異なっていれば解を見つけることができました。print_answer で手順を表示して return で処理を終了します。同じ探索方向であれば、キューへの追加は行いません。

あとのプログラムなので説明は割愛いたします。詳細は プログラムリスト２ をお読みください。

さっそく実行してみると、生成された局面数は 16088 個で、実行時間は 0.014 秒でした。局面数は約 1 / 11 になり、実行時間も約 30 倍と高速になりました。

●最長手数の求め方

今度は最長手数の局面を求めてみましょう。最長手数の求め方ですが、181440 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかし、この方法では時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。

まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。

このプログラムの目的は、いちばん長い手数となる配置を求めることなので、その手順を表示することは行いません。このため、一つ前の局面を格納するインスタンス変数 prev は削除します。そのかわり、その局面までの手数を格納するメンバ変数 move を用意します。一つ前の局面の手数を move から求め、それに 1 を足せば現在の局面の手数となります。

●プログラムの作成

それではプログラムを作ります。次のリストを見てください。

リスト : 8 パズルの最長手数を求める

void solver(char *start)
{
  Node *root = NULL;
  root = insert_tree(init_queue(start), root);
  while (!is_empty()) {
    State *st = deq();
    for (int i = 0; adjacent[st->space][i] != -1; i++) {
      char new_board[N];
      int x = adjacent[st->space][i];
      memcpy(new_board, st->board, N);
      new_board[st->space] = new_board[x];
      new_board[x] = S;
      if (!search_tree(new_board, root))
        root = insert_tree(enq(new_board, x, st), root);
    }
  }
  print_answer();
}

関数 solver には goal をチェックする処理がないことに注意してください。生成できる局面がなくなるまで、つまりキューにデータがなくなるまで処理を繰り返します。

enq で新しい局面を生成するときは、1 手前の局面 st の手数 st->move を +1 します。while ループを終了したあと、print_answer で最長手数の局面を表示します。キューの本体 buff の末尾 (rear - 1 番目) の状態が最長手数の局面になります。buff の末尾から最長手数と同じ手数の局面を取り出して表示するだけです。

あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト３ をお読みください。

●実行結果 (2)

これでプログラムは完成です。さっそく実行してみましょう。

$ clang -O2 eight2.c
$ ./a.out
31, 8 6 7 2 5 4 3 0 1
31, 6 4 7 8 5 0 3 2 1
0.443

最長手数は 31 手で、その配置は全部で 2 通りになります。実行時間は 0.443 秒になりました。

今回はここまでです。次回は「反復深化」を使ってスライドパズルを解いてみましょう。

●参考文献

1. 井上うさぎ, 『世界のパズル百科イラストパズルワンダーランド』, 東京堂出版, 1997
2. 三木太郎, 『特集コンピュータパズルへの招待 スライディングブロック編』, C MAGAZINE 1996 年 2 月号, ソフトバンク
3. 高橋謙一郎, 『特集 悩めるプログラマに効くアルゴリズム』, C MAGAZINE 2000 年 11 月号, ソフトバンク

●プログラムリスト１

/*
 * eight.c : 8 パズル
 *
 *           Copyright (C) 2015-2023 Makoto Hiroi
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define N 9
#define Q 181440
#define S 0

// 隣接リスト
int adjacent[N][5] = {
  {1, 3, -1},       // 0
  {0, 2, 4, -1},    // 1
  {1, 5, -1},       // 2
  {0, 4, 6, -1},    // 3
  {1, 3, 5, 7, -1}, // 4
  {2, 4, 8, -1},    // 5
  {3, 7, -1},       // 6
  {4, 6, 8, -1},    // 7
  {5, 7, -1}        // 8
};

// 局面
typedef struct state {
  char board[N];
  int  space;
  struct state *prev;
} State;

// キュー
State buff[Q];
int front, rear;

State *init_queue(char *board)
{
  State *st = &buff[rear++];
  st->prev = NULL;
  for (int i = 0; i < N; i++) {
    if (board[i] == S) st->space = i;
    st->board[i] = board[i];
  }
  return st;
}

State *enq(char *board, int space, State *st)
{
  if (rear == Q) {
    fprintf(stderr, "Queue is full\n");
    exit(1);
  }
  State *new_st = &buff[rear++];
  memcpy(new_st->board, board, N);
  new_st->space = space;
  new_st->prev = st;
  return new_st;  
}

State *deq(void)
{
  if (front == rear) {
    fprintf(stderr, "Queue is empty!\n");
    exit(1);
  }
  return &buff[front++];
}

bool is_empty(void)
{
  return front == rear;
}

// 二分探索木
typedef struct node {
  State *st;
  struct node *left;
  struct node *right;
} Node;

// 節の生成
Node *make_node(State *st)
{
  Node *node = malloc(sizeof(Node));
  if (node == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(1);
  }
  node->st = st;
  node->left = NULL;
  node->right = NULL;
  return node;
}

// 探索
bool search_tree(char *board, Node *node)
{
  while (node != NULL) {
    int r = memcmp(board, node->st->board, N);
    if (r == 0)
      return true;
    else if (r < 0) 
      node = node->left;
    else 
      node = node->right;
  }
  return false;
}

// 挿入
Node *insert_tree(State *st, Node *node)
{
  if (node == NULL) return make_node(st);
  int r = memcmp(st->board, node->st->board, N);
  if (r < 0)
    node->left = insert_tree(st, node->left);
  else if (r > 0)
    node->right = insert_tree(st, node->right);
  return node;
}


// 手順の表示
void print_answer(State *st)
{
  if (st->prev != NULL)
    print_answer(st->prev);
  for (int i = 0; i < N; i++) printf("%d ", st->board[i]);
  printf("\n");
}

// 幅優先探索
void solver(char *start, char *goal)
{
  Node *root = NULL;
  root = insert_tree(init_queue(start), root);
  while (!is_empty()) {
    State *st = deq();
    if (memcmp(st->board, goal, N) == 0) {
      print_answer(st);
      return;
    }
    for (int i = 0; adjacent[st->space][i] != -1; i++) {
      char new_board[N];
      int x = adjacent[st->space][i];
      memcpy(new_board, st->board, N);
      new_board[st->space] = new_board[x];
      new_board[x] = S;
      if (!search_tree(new_board, root))
        root = insert_tree(enq(new_board, x, st), root);
    }
  }
}

int main(void)
{
  char start[N] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
  char goal[N] =  {1, 2, 3, 4, 5, 6, 7, 8, 0};
  clock_t s = clock();
  solver(start, goal);
  printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
  return 0;
}

●プログラムリスト２

/*
 * eight1.c : 8 パズル (双方向探索)
 *
 *           Copyright (C) 2015-2023 Makoto Hiroi
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define N 9
#define Q 181440
#define S 0
#define BACK 1
#define FORE 2

// 隣接リスト
int adjacent[N][5] = {
  {1, 3, -1},       // 0
  {0, 2, 4, -1},    // 1
  {1, 5, -1},       // 2
  {0, 4, 6, -1},    // 3
  {1, 3, 5, 7, -1}, // 4
  {2, 4, 8, -1},    // 5
  {3, 7, -1},       // 6
  {4, 6, 8, -1},    // 7
  {5, 7, -1}        // 8
};

// 局面
typedef struct state {
  char board[N];
  int  dir;
  int  space;
  struct state *prev;
} State;

// キュー
State buff[Q];
int front, rear;

State *init_queue(char *board, int dir)
{
  State *st = &buff[rear++];
  st->dir = dir;
  st->prev = NULL;
  for (int i = 0; i < N; i++) {
    if (board[i] == S) st->space = i;
    st->board[i] = board[i];
  }
  return st;
}

State *enq(char *board, int space, State *st)
{
  if (rear == Q) {
    fprintf(stderr, "Queue is full\n");
    exit(1);
  }
  State *new_st = &buff[rear++];
  memcpy(new_st->board, board, N);
  new_st->dir = st->dir;
  new_st->space = space;
  new_st->prev = st;
  return new_st;  
}

State *deq(void)
{
  if (front == rear) {
    fprintf(stderr, "Queue is empty!\n");
    exit(1);
  }
  return &buff[front++];
}

bool is_empty(void)
{
  return front == rear;
}

// 二分探索木
typedef struct node {
  State *st;
  struct node *left;
  struct node *right;
} Node;

// 節の生成
Node *make_node(State *st)
{
  Node *node = malloc(sizeof(Node));
  if (node == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(1);
  }
  node->st = st;
  node->left = NULL;
  node->right = NULL;
  return node;
}

// 探索
State *search_tree(char *board, Node *node)
{
  while (node != NULL) {
    int r = memcmp(board, node->st->board, N);
    if (r == 0)
      return node->st;
    else if (r < 0) 
      node = node->left;
    else 
      node = node->right;
  }
  return NULL;
}

// 挿入
Node *insert_tree(State *st, Node *node)
{
  if (node == NULL) return make_node(st);
  int r = memcmp(st->board, node->st->board, N);
  if (r < 0)
    node->left = insert_tree(st, node->left);
  else if (r > 0)
    node->right = insert_tree(st, node->right);
  return node;
}


// 手順の表示
void print_answer_back(State *st)
{
  if (st->prev != NULL)
    print_answer_back(st->prev);
  for (int i = 0; i < N; i++) printf("%d ", st->board[i]);
  printf("\n");
}

void print_answer_fore(State *st)
{
  while (st != NULL) {
    for (int i = 0; i < N; i++) printf("%d ", st->board[i]);
    printf("\n");
    st = st->prev;
  }
}

void print_answer(State *st1, State *st2)
{
  if (st1->dir == BACK) {
    print_answer_back(st1);
    print_answer_fore(st2);
  } else {
    print_answer_back(st2);
    print_answer_fore(st1);
  }
}

// 幅優先探索
void solver(char *start, char *goal)
{
  Node *root = NULL;
  root = insert_tree(init_queue(start, BACK), root);
  root = insert_tree(init_queue(goal, FORE),  root);
  while (!is_empty()) {
    State *st = deq();
    for (int i = 0; adjacent[st->space][i] != -1; i++) {
      char new_board[N];
      int x = adjacent[st->space][i];
      memcpy(new_board, st->board, N);
      new_board[st->space] = new_board[x];
      new_board[x] = S;
      State *st1 = search_tree(new_board, root);
      if (st1 == NULL) {
        root = insert_tree(enq(new_board, x, st), root);
      } else if (st1->dir != st->dir) {
        print_answer(st, st1);
        return;
      }
    }
  }
}

int main(void)
{
  char start[N] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
  char goal[N] =  {1, 2, 3, 4, 5, 6, 7, 8, 0};
  clock_t s = clock();
  solver(start, goal);
  printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
  return 0;
}

●プログラムリスト３

/*
 * eight2.c : 8 パズル (最長手数の探索)
 *
 *            Copyright (C) 2015-2023 Makoto Hiroi
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define N 9
#define Q 181440
#define S 0

// 隣接リスト
int adjacent[N][5] = {
  {1, 3, -1},       // 0
  {0, 2, 4, -1},    // 1
  {1, 5, -1},       // 2
  {0, 4, 6, -1},    // 3
  {1, 3, 5, 7, -1}, // 4
  {2, 4, 8, -1},    // 5
  {3, 7, -1},       // 6
  {4, 6, 8, -1},    // 7
  {5, 7, -1}        // 8
};

// 局面
typedef struct state {
  char board[N];
  int  space;
  int  move;
} State;

// キュー
State buff[Q];
int front, rear;

State *init_queue(char *board)
{
  State *st = &buff[rear++];
  st->move = 0;
  for (int i = 0; i < N; i++) {
    if (board[i] == S) st->space = i;
    st->board[i] = board[i];
  }
  return st;
}

State *enq(char *board, int space, State *st)
{
  if (rear == Q) {
    fprintf(stderr, "Queue is full\n");
    exit(1);
  }
  State *new_st = &buff[rear++];
  memcpy(new_st->board, board, N);
  new_st->space = space;
  new_st->move = st->move + 1;
  return new_st;  
}

State *deq(void)
{
  if (front == rear) {
    fprintf(stderr, "Queue is empty!\n");
    exit(1);
  }
  return &buff[front++];
}

bool is_empty(void)
{
  return front == rear;
}

void print_answer(void)
{
  int i = Q - 1;
  int m = buff[i].move;
  for (; buff[i].move == m; i--) {
    printf("%d, ", m);
    for (int j = 0; j < N; j++) printf("%d ", buff[i].board[j]);
    printf("\n");
  }
}

// 二分探索木
typedef struct node {
  State *st;
  struct node *left;
  struct node *right;
} Node;

// 節の生成
Node *make_node(State *st)
{
  Node *node = malloc(sizeof(Node));
  if (node == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(1);
  }
  node->st = st;
  node->left = NULL;
  node->right = NULL;
  return node;
}

// 探索
bool search_tree(char *board, Node *node)
{
  while (node != NULL) {
    int r = memcmp(board, node->st->board, N);
    if (r == 0)
      return true;
    else if (r < 0) 
      node = node->left;
    else 
      node = node->right;
  }
  return false;
}

// 挿入
Node *insert_tree(State *st, Node *node)
{
  if (node == NULL) return make_node(st);
  int r = memcmp(st->board, node->st->board, N);
  if (r < 0)
    node->left = insert_tree(st, node->left);
  else if (r > 0)
    node->right = insert_tree(st, node->right);
  return node;
}

// 幅優先探索
void solver(char *start)
{
  Node *root = NULL;
  root = insert_tree(init_queue(start), root);
  while (!is_empty()) {
    State *st = deq();
    for (int i = 0; adjacent[st->space][i] != -1; i++) {
      char new_board[N];
      int x = adjacent[st->space][i];
      memcpy(new_board, st->board, N);
      new_board[st->space] = new_board[x];
      new_board[x] = S;
      if (!search_tree(new_board, root))
        root = insert_tree(enq(new_board, x, st), root);
    }
  }
  print_answer();
}

int main(void)
{
  char goal[N] =  {1, 2, 3, 4, 5, 6, 7, 8, 0};
  clock_t s = clock();
  solver(goal);
  printf("%.3f\n", (double)(clock() - s)/CLOCKS_PER_SEC);
  return 0;
}