８パズルプログラム

８パズルプログラムを書いた。

ソースはこちら(SlidingBlockPuzzle (C))





このまえのルービックキューブプログラムと考え方は同じで、ヒューリスティック関数を使ってA*探索をする。


ルービックキューブプログラムに比べたらずいぶんあっさりと組めてしまった。

マクロを変えてコンパイルすれば８パズルでも１５パズルでも２４パズルでも３５パズルでも、原理的には解ける。


いまのところ試した初期状態では最長３２手で全部解けてるけど、探索木の深さが３０以上になるとなかなか返ってこなくなる。


どうやら１５パズルの最短最長手数は８０前後らしいので、まだまだ。



ルービックキューブよりもヒューリスティック関数がかなり作りやすいから、もっと行けると思ったけど。




実行例

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

#define D 4    /*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++){block[i][j]);       /*解法を表示*/
        fprintf(fp, "%3d", cur->block[i][j]);
      }
      printf("n");
      fprintf(fp, "n");
    }
    fprintf(fp, "nn");
    printf("nn");
    
    cur = cur->nextleaf;
  }while(cur->heuristic);

  printf(" %d 手目n", k);
  fprintf(fp, " %d 手目n", k);

  for(i=0;i<D;i++){block[i][j]);
      printf("%3d", cur->block[i][j]);
    }
    printf("n");
    fprintf(fp, "n");
  }
  printf("nn");
  fprintf(fp, "nn");

  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 手以下で完成nn", nextdev->heuristic);

  return  nextdev;
}


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


  for(i=0;i<D;i++)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 || 3next = (struct node **)malloc(sizeof(struct node *)*(int)k); 
  cur->nextnum = (unsigned int)k;
 
  for(i=0;i<k;i++){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 || 4next = (struct node **)malloc(sizeof(struct node *)*(int)k); 
  cur->nextnum = (unsigned int)k;
 
  for(i=0;i<k;i++){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++){block[i][j] == k)
          goto breakpoint;              /*オペレータの制限を緩めてゴールまでの手数を見積もる*/
    breakpoint:

    for(gi=0;gi<D;gi++)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);
  }


  for(i=0;i<D;i++){block[i][j]);
      printf("%3d", (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ルートの初期化、ゴール状態の定義完了nn");

/*
  for(i=0;i<D;i++){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++)nextnum);i++)
      heuristic(next->next[i], &goal);
  }

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

  return 0;
}