8パズルの探索

[雷電]

こんにちは。今、学校の課題で困っていることがあります。

「8 パズルを探索により、解を得るプログラムを作成し、種々の初期状態に適用し、
時間計算コストの評価をすること」という内容です。

下のプログラムを実行すると、”初期状態.txt”に書いた8パズルを順路を追って、最短で求めます。
最終的に1，2，3，4，5，6，7，8，0という並びになるのですが、

1 2 3
8 0 4
7 6 5

というゴール状態にしたいです。しかし、どこを変えればいいのか分かりません。
どなたか分かる方いらっしゃいますでしょうか？
時間計算コストの評価というのもよく分かりません･･･。よろしくお願いします。

コード:

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

#define D 3    /*D×D-1 パズル。　このマクロを変えればどんな大きさのパズルでも探索できる*/


struct node{

  int block[D][D];        /*各ノードのブロック状態*/
  char ei;                /*空白の場所*/
  char ej;
  unsigned int nextnum: 3;    /*直属の子ノードの数*/
  int depth;                 /*このノードの深さ*/
  int heuristic;             /*ヒューリスティック値*/
  int exp;                   /*ヒューリスティック値 ＋ 深さ*/
  struct node **next;        /*子ノードへのポインタ*/
  struct node *reverse;      /*親ノードへのポインタ*/
  struct node *nextleaf;     /*リーフだった場合、次のリーフへのポインタ*/
  struct node *reverseleaf;  /*前のリーフへのポインタ*/
};


void init(struct node *root, struct node *goal);         /*ルート初期化、ゴール状態定義*/
void heuristic(struct node *cur, struct node *goal);     /*ヒューリスティック関数*/
int allocate(struct node *cur, struct node *endleaf);   /*メモリを確保してリストにつなげる*/
int rootdev(struct node *cur, struct node *endleaf);   /*allocateのルート版*/
int operate(struct node *cur, char direction);          /*状態遷移関数*/
struct node *search(struct node *leaf);                /*次に展開するノードを探す*/
void output(struct node *cur);                         /*解法を表示*/


void output(struct node *cur)
{
  int i, j, k=0;
  FILE *fp;

  if((fp=fopen("解法.txt","w"))==NULL){
	printf("ファイルを生成できません\n");
    exit(1);
  }


  do{
	cur->reverse->nextleaf = cur;
    cur = cur->reverse;
  }while(cur->reverse);    /*ポインタ再利用*/


  do{
    printf("%d 手目\n", k);//最後以外、常に出てくる手数
    fprintf(fp, " %d 手目\n", k++);//メモ帳に書き写す
    
	for(i=0;i<D;i++){  //iを増やすと、行が上から減る
      for(j=0;j<D;j++){//jを増やすと、列が左から減る。完成だけ普通
        printf("%3d", cur->block[i][j]);       /*解法を表示*/
      											//cur->block[i][j]が数値？1～8+0を全て受け持つ?
      											//%d=数値、%とdの間に数字でスペース
        fprintf(fp, "%3d", cur->block[i][j]);//解法txtに
      }
	  printf("\n");
      fprintf(fp, "\n");//解法txtに(fprintfが、メモ帳に書きこむ役割？)
    }
    fprintf(fp, "\n\n");
    printf("\n\n");

    cur = cur->nextleaf;
  }while(cur->heuristic);

  printf(" %d 手目\n", k);//最後の手数
  fprintf(fp, " %d 手目\n", k);//最後の手数を、解法.txtに写す

  for(i=0;i<D;i++){
    for(j=0;j<D;j++){
      fprintf(fp, "%3d", cur->block[i][j]);
	  printf("%3d(⌒,_ゝ⌒)", cur->block[i][j]);//完成形をあらわす。
    }
    printf("\n");
    fprintf(fp, "\n");
  }
  printf("\n\n");
  fprintf(fp, "\n\n");

  fclose(fp);
}


struct node *search(struct node *leaf)
{
  struct node *nextdev;
  int min=50000;

  leaf = leaf->nextleaf;

  while(leaf->nextleaf){   /*リーフリストをたどってexpが最小のリーフを探す*/
	if(min > leaf->exp){
      nextdev = leaf;
      min = leaf->exp;
    }
    leaf = leaf->nextleaf;
  }

//  printf("\nあと%d 手以下で完成\n\n", nextdev->heuristic);

  return  nextdev;
}


int operate(struct node *cur, char direction)
{
  char i, j;


  for(i=0;i<D;i++)
    for(j=0;j<D;j++)
	  cur->block[i][j] = cur->reverse->block[i][j];

  cur->ei = cur->reverse->ei;
  cur->ej = cur->reverse->ej;

  if(direction == 'u'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei-1][cur->ej];   /*状態遷移を実行*/
    cur->block[--cur->ei][cur->ej] = 0;
  }

  else if(direction == 'd'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei+1][cur->ej];
    cur->block[++cur->ei][cur->ej] = 0;
  }

  else if(direction == 'r'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei][cur->ej+1];
    cur->block[cur->ei][++cur->ej] = 0;
  }

  else if(direction == 'l'){
    cur->block[cur->ei][cur->ej] = cur->block[cur->ei][cur->ej-1];
    cur->block[cur->ei][--cur->ej] = 0;
  }

  else{
    printf("ありえない\n");    /*万が一の例外処理*/
    exit(1);
  }

  return (cur->depth = cur->reverse->depth + 1);
}



int allocate(struct node *cur, struct node *endleaf)
{
  char k = 0, i, direction[3];
  int depth=0, buf;


  if(cur->ei != 0 && cur->reverse->ei+1 != cur->ei)   /*遷移できる状態とその数を調べる*/
    direction[k++] = 'u';

  if(cur->ei != D-1 && cur->reverse->ei != cur->ei+1)
	direction[k++] = 'd';

  if(cur->ej != 0 && cur->reverse->ej+1 != cur->ej)
    direction[k++] = 'l';

  if(cur->ej != D-1 && cur->reverse->ej != cur->ej+1)
    direction[k++] = 'r';

  if(k<1 || 3<k){
    printf("ありえない\n");
	exit(1);
  }

  cur->next = (struct node **)malloc(sizeof(struct node *)*(int)k); 
  cur->nextnum = (unsigned int)k;

  for(i=0;i<k;i++){
    cur->next[i] = (struct node *)malloc(sizeof(struct node));
    if(!cur->next[i]){
      printf("メモリ割り当てエラー");
	  exit(1);
    }

    cur->next[i]->reverse = cur;

    cur->next[i]->reverseleaf = endleaf->reverseleaf;   /*リストにつなげる*/
	endleaf->reverseleaf->nextleaf = cur->next[i];
    cur->next[i]->nextleaf = endleaf;
    endleaf->reverseleaf = cur->next[i];

    if(depth < (buf=operate(cur->next[i], direction[i])))
      depth = buf;
  }

  cur->reverseleaf->nextleaf = cur->nextleaf;
  cur->nextleaf->reverseleaf = cur->reverseleaf;

  return depth;
}



int rootdev(struct node *cur, struct node *endleaf)
{
  char k = 0, i, direction[4];
  int buf, depth=0;

  if(cur->ei != 0)
    direction[k++] = 'u';

  if(cur->ei != D-1)
    direction[k++] = 'd';

  if(cur->ej != 0)
    direction[k++] = 'l';

  if(cur->ej != D-1)
    direction[k++] = 'r';

  if(k<2 || 4<k){
    printf("ありえない\n");
    exit(1);
  }


  cur->next = (struct node **)malloc(sizeof(struct node *)*(int)k); 
  cur->nextnum = (unsigned int)k;

  for(i=0;i<k;i++){
    cur->next[i] = (struct node *)malloc(sizeof(struct node));
    if(!cur->next[i]){
	  printf("メモリ割り当てエラー");
      exit(1);
    }

	cur->next[i]->reverse = cur;

    cur->next[i]->reverseleaf = endleaf->reverseleaf;
	endleaf->reverseleaf->nextleaf = cur->next[i];
    cur->next[i]->nextleaf = endleaf;
    endleaf->reverseleaf = cur->next[i];

    if(depth < (buf = operate(cur->next[i], direction[i])))
      depth = buf;
  }

  cur->reverseleaf->nextleaf = cur->nextleaf;
  cur->nextleaf->reverseleaf = cur->reverseleaf;

  return depth;
}



void heuristic(struct node *cur, struct node *goal)
{
  char i, j, gi, gj, k, d = D*D;


  cur->heuristic = 0;
  
  for(k=1;k<d;k++){

    for(i=0;i<D;i++)
      for(j=0;j<D;j++)
		if(cur->block[i][j] == k)
          goto breakpoint;              /*オペレータの制限を緩めてゴールまでの手数を見積もる*/
    breakpoint:

    for(gi=0;gi<D;gi++)
      for(gj=0;gj<D;gj++)
		if(goal->block[gi][gj] == k)
          goto breakpoint2;
	breakpoint2:


    cur->heuristic += (int)(fabs((double)(i-gi)) + fabs((double)(j-gj)));
  }
  cur->exp = cur->heuristic + cur->depth;

}



void init(struct node *root, struct node *goal)
{
  FILE *fp;
  char i, j, k=1;

  if((fp=fopen("初期状態.txt","r"))==NULL){
    printf("初期状態ファイルを開けませんでした。\n");
	exit(1);
  }

	printf("--初期状態--\n");
  for(i=0;i<D;i++){
	for(j=0;j<D;j++){
      fscanf(fp, "%d", &root->block[i][j]);
      printf(" %2d", (int)root->block[i][j]);
	  goal->block[i][j] = k++;
      if(!root->block[i][j]){
        root->ei = i;
        root->ej = j;
	  }
    }
    printf("\n");
  }

  root->depth = 0;
  root->reverse = NULL;
  goal->block[D-1][D-1] = 0;

  printf("\nルートの初期化、ゴール状態の定義完了\n\n");

/*
  for(i=0;i<D;i++){
    for(j=0;j<D;j++)
      printf("%3d", goal->block[i][j]);
    printf("\n");
  }
*/

}



int main(void)
{
  struct node root, *cur, goal, startleaf, endleaf, *next;
  int i, depth=0, buf;


  startleaf.nextleaf = &root;
  root.nextleaf = &endleaf;
  endleaf.reverseleaf = &root;
  root.reverseleaf = &startleaf;
  endleaf.nextleaf = NULL;
 
  init(&root, &goal);

  heuristic(&root, &goal);
  if(!(root.heuristic)){
    printf("すでにゴール状態です\n");
	return 0;
  }

  if(depth < (buf = rootdev(&root, &endleaf)))
    depth = buf;
  printf("\n深さ 1 まで展開");

  for(i=0;i<(int)(root.nextnum);i++)
    heuristic(root.next[i], &goal);


  while((next = search(&startleaf))->heuristic){
    if(depth < (buf = allocate(next, &endleaf))){
        depth = buf;
	  for(buf=0;buf<30;buf++)
        printf("\b");
      printf("深さ %d まで展開", depth);
	}

    for(i=0;i<(int)(next->nextnum);i++)
	  heuristic(next->next[i], &goal);
  }

  printf("\n\n%d 手で完成\n\n", next->depth);
  output(next);

  return 0;
}