幅優先を改良してA*探索にする

###問題
8パズルという問題を，C言語，A*探索で解く
8パズル

###理想とする挙動

###現状のコード
幅優先探索とh1の評価関数をそれぞれ作ることはしましたが，この二つを組み合わせてどのようにA*にするのかが分かっていません．

C
1#include <stdio.h>
2#include <string.h>
3#include <time.h>
4
5#define TRUE  1
6#define FALSE 0
7#define GOAL  2
8#define SIZE  9
9
10/* 状態数 (9! / 2) */
11#define MAX_STATE 181440
12
13/* 隣接リスト */
14const char adjacent[SIZE][5] = {
15  1, 3,-1,-1,-1,
16  0, 4, 2,-1,-1,
17  1, 5,-1,-1,-1,
18  0, 4, 6,-1,-1,
19  1, 3, 5, 7,-1,
20  2, 4, 8,-1,-1,
21  3, 7,-1,-1,-1,
22  4, 6, 8,-1,-1,
23  5, 7,-1,-1,-1,
24};
25
26/* キュー */
27char state[MAX_STATE + 1][SIZE];      // +1 はワーク領域 
28char space_postion[MAX_STATE];
29int  prev_state[MAX_STATE];
30
31/* 同一局面チェックテーブル */
32char check_table[MAX_STATE * 2];
33
34char init_state[SIZE] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
35char final_state[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
36
37int h1(char state[]){
38    int count = 0;
39    for(int i = 0;i < 9;i++){
40        if(state[i] != final_state[i]) count++;
41    }
42    return count;
43}
44
45
46
47/* 結果を出力 */
48void print_answer(int n){
49  int i, j;
50  if( n != 0 ) print_answer( prev_state[n] ); //再帰で最初から描いていく
51  for( i = 0; i < 3; i++ ){
52    for( j = 0; j < 3; j++ ){
53      printf("%d ", state[n][i * 3 + j] );
54    }
55    printf("\n");
56  }
57  printf("\n");
58}
59
60/* 番号に変換 */
61int change_number( char *board ){
62  char work[SIZE];
63  static int fact_table[SIZE] = {40320, 5040, 720, 120, 24, 6, 2, 1, 0,};
64  int j, k, value = 0;
65  memcpy( work, board, SIZE );
66  for( j = 0; j < SIZE - 1; j++ ){
67    value += fact_table[j] * work[j];
68    for( k = j + 1; k < SIZE; k++ ){
69      if( work[j] < work[k] ) work[k]--;
70    }
71  }
72  //printf("value:%d\n",value);
73  return value;
74}
75
76/* 探索 */
77void search( void ){
78  int front = 0, rear = 1; //rearは深さを示す
79  /* 初期化 */
80  memcpy( state[0], init_state, SIZE );
81  space_postion[0] = 7;       //変更が必要
82  prev_state[0] = -1;
83  check_table[ change_number( init_state ) ] = TRUE;
84  check_table[ change_number( final_state ) ] = GOAL;
85
86  /* キューにデータがある間繰り返す */
87  while( front < rear ){
88    int s = space_postion[front];
89    int i, k, n;
90    for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
91      /* 前の状態をコピー */
92      memcpy( state[rear], state[front], SIZE );
93      /* 移動 */
94      state[rear][s] = state[rear][n]; //スペースがあった場所にnにあったものを移動
95      state[rear][n] = 0; //nをスペースにする
96      space_postion[rear] = n; //スペースの位置を示す変数にnを格納
97      prev_state[rear] = front; 
98      k = change_number( state[rear] ); //状態を番号に変換
99      if( check_table[k] == GOAL ){ //goalの番号を一致したら発見
100        print_answer( rear );
101        printf("状態数 %d 個\n", rear );
102        return;
103      } else if( !check_table[k] ){ //なったことがあればすでにTRUE=1が入ってる
104	    /* キューに登録 */
105        check_table[k] = TRUE;
106	    rear++;
107      }
108    }
109
110    front++;
111  }
112}
113
114int main(){
115  /* 
116   * 静的変数が 0 に初期化される場合は不用だが
117   * 初期化することは悪いことではない。
118   */
119  memset( check_table, 0 , MAX_STATE * 2 );
120  clock_t time = clock();
121  search();
122  double result = (double)(clock() - time)/CLOCKS_PER_SEC;
123  printf("%.3fsec \n", result );
124  return 0;
125}