ルービックキューブプログラム 続き３

/*前の記事の続き。ソースコードが840行もあるから、具体的な実行例はまた明日。*/

void exception(void)   
 /*ルート展開のあと１回だけ呼び出す。状態遷移を網羅するためあと３つ展開する*/
{
  struct node *leaf;
  char i,j,k,l;


  leaf=(struct node *)malloc(sizeof(struct node)*3);
  if(!leaf){
    printf("メモリ割り当てエラー\a\n");
    exit(1);
  }

  endleaf.revleaf->nextleaf=&leaf[0];
  leaf[0].revleaf=endleaf.revleaf;
  leaf[0].nextleaf=&leaf[1];
  leaf[1].revleaf=&leaf[0];
  leaf[1].nextleaf=&leaf[2];
  leaf[2].revleaf=&leaf[1];
  leaf[2].nextleaf=&endleaf;
  endleaf.revleaf=&leaf[2];

  nodeend.revnode->nodelist=&leaf[0];
  leaf[0].nodelist=&leaf[1];
  leaf[1].nodelist=&leaf[2];
  leaf[2].nodelist=&nodeend;
  nodeend.revnode=&leaf[2];

  for(i=0;i<3;i++){nextleaf){


    if(min>leaf->expectation){
      min=leaf->expectation; 
  /*リーフリストをたどってheuristic+costが最小のものを探す*/
      minG=leaf;
    }

    leaf=leaf->nextleaf;
  }

}





void output(void)     /*解を表示*/
{
  char *buf;
  unsigned int i;

  buf=(char *)malloc(sizeof(char)*min*2);
  if(!buf){
    printf("メモリ割り当てエラー\a\n");
    exit(1);
  }

  for(i=0;i<min;i++){    /*親ノードをたどっていって遷移の履歴を読む*/ope;
    buf[min+i]=minG->opecolor;

    minG=minG->reverse;
  }

  printf("\n\n %d 手で完成\n\n\a",min);

  for(i=min;i;i--)
    switch(buf[i-1]){     /*解法を表示する*/

      case 0:
        printf(" %c 面を: 180°回転\n",buf[min+i-1]);
        break;

      case 1:
        printf(" %c 面を: 90°右に回転\n",buf[min+i-1]);
        break;

      case -1:
        printf(" %c 面を: 左に 90°回転\n",buf[min+i-1]);
    };

  free(buf);
}

/*おわり*/

ルービックキューブプログラム 続き２

/*前の記事のさらに続き*/

void heuristic(struct node *cube)
{
  char i,j,k,p=1,q;
  unsigned int color[6], cornor=0, edge=0, hash, buff=0;
  struct node *node;

  if(cube->surface[0][0][0]!=goal.surface[0][0][0] || 
/*コーナーキューブの位置,向きが違ってる個数を数える*/
cube->surface[2][2][0]!=goal.surface[2][2][0] || 
cube->surface[1][2][2]!=goal.surface[1][2][2])
    cornor++;

  if(cube->surface[0][0][2]!=goal.surface[0][0][2] || 
cube->surface[2][2][2]!=goal.surface[2][2][2] || 
cube->surface[4][2][0]!=goal.surface[4][2][0])
    cornor++;

  if(cube->surface[0][2][0]!=goal.surface[0][2][0] || 
cube->surface[1][2][0]!=goal.surface[1][2][0] || 
cube->surface[3][0][0]!=goal.surface[3][0][0])
    cornor++;

  if(cube->surface[0][2][2]!=goal.surface[0][2][2] || 
cube->surface[4][2][2]!=goal.surface[4][2][2] || 
cube->surface[3][0][2]!=goal.surface[3][0][2])
    cornor++;

  if(cube->surface[5][0][0]!=goal.surface[5][0][0] || 
cube->surface[3][2][0]!=goal.surface[3][2][0] || 
cube->surface[1][0][0]!=goal.surface[1][0][0])
    cornor++;

  if(cube->surface[5][0][2]!=goal.surface[5][0][2] || 
cube->surface[3][2][2]!=goal.surface[3][2][2] || 
cube->surface[4][0][2]!=goal.surface[4][0][2])
    cornor++;

  if(cube->surface[5][2][0]!=goal.surface[5][2][0] || 
cube->surface[2][0][0]!=goal.surface[2][0][0] || 
cube->surface[1][0][2]!=goal.surface[1][0][2])
    cornor++;

  if(cube->surface[5][2][2]!=goal.surface[5][2][2] || 
cube->surface[2][0][2]!=goal.surface[2][0][2] || 
cube->surface[4][0][0]!=goal.surface[4][0][0])
    cornor++;

  if(cube->surface[0][1][0]!=goal.surface[0][1][0] ||  
 /*エッジキューブの向き,位置が違ってるものを数える*/
cube->surface[1][2][1]!=goal.surface[1][2][1])
    edge++;

  if(cube->surface[0][2][1]!=goal.surface[0][2][1] || 
cube->surface[3][0][1]!=goal.surface[3][0][1])
    edge++;

  if(cube->surface[0][1][2]!=goal.surface[0][1][2] || 
cube->surface[4][2][1]!=goal.surface[4][2][1])
    edge++;

  if(cube->surface[0][0][1]!=goal.surface[0][0][1] || 
cube->surface[2][2][1]!=goal.surface[2][2][1])
    edge++;

  if(cube->surface[2][1][0]!=goal.surface[2][1][0] || 
cube->surface[1][1][2]!=goal.surface[1][1][2])
    edge++;

  if(cube->surface[2][1][2]!=goal.surface[2][1][2] || 
cube->surface[4][1][0]!=goal.surface[4][1][0])
    edge++;

  if(cube->surface[3][1][0]!=goal.surface[3][1][0] || 
cube->surface[1][1][0]!=goal.surface[1][1][0])
    edge++;

  if(cube->surface[3][1][2]!=goal.surface[3][1][2] || 
cube->surface[4][1][2]!=goal.surface[4][1][2])
    edge++;

  if(cube->surface[5][1][0]!=goal.surface[5][1][0] || 
cube->surface[1][0][1]!=goal.surface[1][0][1])
    edge++;

  if(cube->surface[5][2][1]!=goal.surface[5][2][1] || 
cube->surface[2][0][1]!=goal.surface[2][0][1])
    edge++;

  if(cube->surface[5][1][2]!=goal.surface[5][1][2] || 
cube->surface[4][0][1]!=goal.surface[4][0][1])
    edge++;

  if(cube->surface[5][0][1]!=goal.surface[5][0][1] || 
cube->surface[3][2][1]!=goal.surface[3][2][1])
    edge++;

  for(i=0;i<6;i++)surface[k][i][j])
          color[k]++;     /*色が違ってる数を数える*/

  for(i=0;i<6;i++)heuristic=0;

  else if(hash==212)   /*２１２だったらあと１手*/
    cube->heuristic=1;

  else if(hash==1576 || hash==959 || hash==873)   /*あと２手*/
    cube->heuristic=2;

  else if(hash==2610 || hash==2448 || hash==1045 || hash==280 || hash==2529 
|| hash==1808 || hash==1680 || hash==2000 || hash==1088 || hash==1002 || 
hash==314 || hash==2205 || hash==2367 || hash==2124 || hash==1936 || 
  hash==2286 || hash==1552 || hash==246 || hash==1335)   /*あと３手*/
    cube->heuristic=3;

  else if(hash==2691 || hash==3900 || hash==3312 || hash==3134 || hash==3401 
|| hash==3223 || hash==3706 || hash==2956 ||  hash==3512 || hash==2514 || 
hash==1131 || hash==530 || hash==1872 || hash==1174 || hash==556 || 
hash==2064 || hash==504 || hash==163 || hash==1554 || hash==631 || hash==410 
|| hash==1364 || hash==3609 || hash==3045 || hash==2772 || hash==1611 || 
hash==3318 || hash==1440 || hash==2280 || hash==2934 || hash==2096 || 
hash==2689 || hash==3579 || hash==3015 || hash==2853 || hash==2226 || 
hash==3124 || hash==3490 || hash==693 || hash==2867 || hash==1217 || 
hash==724 || hash==2778 || hash==2128 || hash==2192 || hash==1260 || 
hash==1414 || hash==1214 || hash==662 || hash==1500 || hash==248 || 
hash==600 || hash==732 || hash==2739 || hash==3027 || hash==916 || 
hash==3221 || hash==1541 || hash==3096 || hash==2356 || hash==2930 || 
hash==2736 || hash==1665 || hash==2358 || hash==2511 || hash==189 || 
  hash==1497 || hash==485)    /*あと４手*/
    cube->heuristic=4;

  else if(hash==2207 || hash==1164 || hash==2360 || hash==1337 || hash==738 
|| hash==2353 || hash==4094 || hash==3803 || hash==3997 || hash==4191 || 
hash==2426 || hash==1744 || hash==3164 || hash==1383 || hash==2909 || hash==2218 
|| hash==2147 || hash==1288 || hash==591 || hash==4288 || hash==3415 || hash==2431
 || hash==2289 || hash==1386 || hash==997 || hash==1901 || hash==1256 || hash==2134 
|| hash==2436 || hash==3249 || hash==2994 || hash==2228 || hash==1771 || hash==1826 
|| hash==1435 || hash==1190 || hash==2499 || hash==2824 || hash==2592 || hash==1239 
|| hash==1555 || hash==1390 || hash==1706 || hash==2500 || hash==2161 || hash==1602 
|| hash==1668 || hash==1038 || hash==1641 || hash==1663 || hash==715 || hash==1785 
|| hash==2572 || hash==2645 || hash==608 || hash==582 || hash==1445 || hash==202
 || hash==263 || hash==1725 || hash==1314 || hash==1782 || hash==755 || hash==3177 
|| hash==2718 || hash==786 || hash==817 || hash==804 || hash==1720 || hash==2320 || 
hash==1839 || hash==1303 || hash==2256 || hash==1896 || hash==1079 || hash==2076 || 
hash==639 || hash==876 || hash==452 || hash==478 || hash==752 || hash==569 || hash==789
 || hash==1616 || hash==705 || hash==956 || hash==1072 || hash==2904 || hash==2748 
|| hash==1210 || 
hash==1118 || hash==3668 || hash==3757 || hash==1464 || hash==672 || hash==3846 
|| hash==3258 || hash==2791 || hash==1934 || hash==2654 || hash==2094 || 
hash==2826 || hash==3060 || hash==3079 || hash==1484 || hash==974 || hash==297 
|| hash==1011 || hash==900 || hash==348 || hash==1846 || hash==3339 || hash==2864
 || hash==840 || hash==948 || hash==2384 || hash==1953 || hash==1830 || hash==2031 
|| hash==634 || hash==264 || hash==229 || hash==1092 || hash==1614 || hash==1419 
|| hash==2484 || hash==408 || hash==2833 || hash==1759 || hash==707 || hash==863 
|| hash==1863 || hash==2005 || hash==475 || hash==538 || hash==826 || hash==937 
|| hash==1141 || hash==1043 || hash==2061 || hash==938 || hash==1960 || hash==830 
|| hash==696 || hash==1188 || hash==1514 || hash==753 || hash==1225 || hash==2362 
|| hash==2281 || hash==331 || hash==3334 || hash==2569 || hash==562 || hash==1775
 || hash==3504 || hash==1564 || hash==984 || hash==1120 || hash==660 || hash==3419 
|| hash==2354 || hash==606 || hash==1388 || hash==1114 || hash==864 || hash==1488 
|| hash==1968 || hash==2062 || hash==2208 || hash==2027 || hash==1885 || hash==1326
 || hash==2046 || hash==540 || hash==998 || hash==1094 || hash==834)
   cube->heuristic=5;   /*あと５手*/ 

  else
    cube->heuristic=6;

  cube->expectation=cube->heuristic+cube->cost;

  cube->hash=1.0;
  for(i=0;i<6;i++)hash*=sin(color[i]+i*0.5); 
    /*前と同じノードを展開しないためのハッシュ値を計算*/

  cube->hash*=edge*cornor;

  node=root.nodelist;    /*ノードリストをたどる*/

  while(node!=cube && p){
    if(node->hash==cube->hash){    /*同じハッシュ値をもつノードがあったら*/
      q=0;

      for(k=0;k<5;k++)surface[k][i][j]!=node->surface[k][i][j])    /*状態を詳しく比較して*/
      q++;

      if(!q){
        p=0;
        cube->revleaf->nextleaf=cube->nextleaf;  
  /*全く同じなら,このノードをリーフリストからはずす*/
        cube->nextleaf->revleaf=cube->revleaf;
      }
    }
  
    node=node->nodelist;
  }
}

/*まだまだ続く*/

ルービックキューブプログラム 続き

/*前の記事の続き*/

void operate(struct node *cube)      /*各ノードで状態遷移を行う*/
{
  struct node *nextcube;
  char i, k=0;

  if(cube->opecolor!='o'){

    nextcube=cube->next[k++];

    for(i=0;i<D;i++){     /*orange面を右回転*/surface[0][i][2]=cube->surface[3][i][2];
      nextcube->surface[2][i][2]=cube->surface[0][i][2];
      nextcube->surface[5][i][2]=cube->surface[2][i][2];
      nextcube->surface[3][i][2]=cube->surface[5][i][2];
    }

    Rrot(nextcube, cube, 4);

    nextcube->ope=1;    /*右回転を１とする*/
    nextcube->opecolor='o';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][i][2]=cube->surface[5][i][2];
      nextcube->surface[2][i][2]=cube->surface[3][i][2];
      nextcube->surface[5][i][2]=cube->surface[0][i][2];
      nextcube->surface[3][i][2]=cube->surface[2][i][2];
    }

    rot(nextcube, cube, 4);

    nextcube->ope=0;   /*180度回転を０とする*/
    nextcube->opecolor='o';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][i][2]=cube->surface[2][i][2];
      nextcube->surface[2][i][2]=cube->surface[5][i][2];
      nextcube->surface[5][i][2]=cube->surface[3][i][2];
      nextcube->surface[3][i][2]=cube->surface[0][i][2];
    }

    Lrot(nextcube, cube, 4);

    nextcube->ope=-1;   /*左回転を-1とする*/
    nextcube->opecolor='o';
  }


  if(cube->opecolor!='r'){

    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][i][0]=cube->surface[3][i][0];
      nextcube->surface[2][i][0]=cube->surface[0][i][0];
      nextcube->surface[5][i][0]=cube->surface[2][i][0];
      nextcube->surface[3][i][0]=cube->surface[5][i][0];
    }

    Lrot(nextcube, cube, 1);

    nextcube->ope=-1;
    nextcube->opecolor='r';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][i][0]=cube->surface[5][i][0];
      nextcube->surface[2][i][0]=cube->surface[3][i][0];
      nextcube->surface[5][i][0]=cube->surface[0][i][0];
      nextcube->surface[3][i][0]=cube->surface[2][i][0];
    }

    rot(nextcube, cube, 1);

    nextcube->ope=0;
    nextcube->opecolor='r';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][i][0]=cube->surface[2][i][0];
      nextcube->surface[2][i][0]=cube->surface[5][i][0];
      nextcube->surface[5][i][0]=cube->surface[3][i][0];
      nextcube->surface[3][i][0]=cube->surface[0][i][0];
    }

    Rrot(nextcube, cube, 1);

    nextcube->ope=1;
    nextcube->opecolor='r';

  }

  if(cube->opecolor!='b'){

    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][2][D-1-i]=cube->surface[1][D-1-i][0];
      nextcube->surface[4][i][2]=cube->surface[0][2][D-1-i];
      nextcube->surface[5][0][i]=cube->surface[4][i][2];
      nextcube->surface[1][D-1-i][0]=cube->surface[5][0][i];
    }

    Rrot(nextcube, cube, 3);

    nextcube->ope=1;
    nextcube->opecolor='b';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][2][D-1-i]=cube->surface[5][0][i];
      nextcube->surface[4][i][2]=cube->surface[1][D-1-i][0];
      nextcube->surface[5][0][i]=cube->surface[0][2][D-1-i];
      nextcube->surface[1][D-1-i][0]=cube->surface[4][i][2];
    }

    rot(nextcube, cube, 3);

    nextcube->ope=0;
    nextcube->opecolor='b';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][2][D-1-i]=cube->surface[4][i][2];
      nextcube->surface[4][i][2]=cube->surface[5][0][i];
      nextcube->surface[5][0][i]=cube->surface[1][D-1-i][0];
      nextcube->surface[1][D-1-i][0]=cube->surface[0][2][D-1-i];
    }

    Lrot(nextcube, cube, 3);

    nextcube->ope=-1;
    nextcube->opecolor='b';

  }

  if(cube->opecolor!='w'){

    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][0][D-1-i]=cube->surface[1][D-1-i][2];
      nextcube->surface[4][i][0]=cube->surface[0][0][D-1-i];
      nextcube->surface[5][2][i]=cube->surface[4][i][0];
      nextcube->surface[1][D-1-i][2]=cube->surface[5][2][i];
    }

    Lrot(nextcube, cube, 2);

    nextcube->ope=-1;
    nextcube->opecolor='w';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][0][D-1-i]=cube->surface[5][2][i];
      nextcube->surface[4][i][0]=cube->surface[1][D-1-i][2];
      nextcube->surface[5][2][i]=cube->surface[0][0][D-1-i];
      nextcube->surface[1][D-1-i][2]=cube->surface[4][i][0];
    }

    rot(nextcube, cube, 2);

    nextcube->ope=0;
    nextcube->opecolor='w';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[0][0][D-1-i]=cube->surface[4][i][0];
      nextcube->surface[4][i][0]=cube->surface[5][2][i];
      nextcube->surface[5][2][i]=cube->surface[1][D-1-i][2];
      nextcube->surface[1][D-1-i][2]=cube->surface[0][0][D-1-i];
    }

    Rrot(nextcube, cube, 2);

    nextcube->ope=1;
    nextcube->opecolor='w';
  }


  if(cube->opecolor!='g'){

    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[4][0][i]=cube->surface[3][2][D-1-i];
      nextcube->surface[2][0][i]=cube->surface[4][0][i];
      nextcube->surface[1][0][i]=cube->surface[2][0][i];
      nextcube->surface[3][2][D-1-i]=cube->surface[1][0][i];
    }

    Rrot(nextcube, cube, 5);

    nextcube->ope=1;
    nextcube->opecolor='g';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[4][0][i]=cube->surface[1][0][i];
      nextcube->surface[2][0][i]=cube->surface[3][2][D-1-i];
      nextcube->surface[1][0][i]=cube->surface[4][0][i];
      nextcube->surface[3][2][D-1-i]=cube->surface[2][0][i];
   }

    rot(nextcube, cube, 5);

    nextcube->ope=0;
    nextcube->opecolor='g';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[4][0][i]=cube->surface[2][0][i];
      nextcube->surface[2][0][i]=cube->surface[1][0][i];
      nextcube->surface[1][0][i]=cube->surface[3][2][D-1-i];
      nextcube->surface[3][2][D-1-i]=cube->surface[4][0][i];
    }

    Lrot(nextcube, cube, 5);

    nextcube->ope=-1;
    nextcube->opecolor='g';

  }

  if(cube->opecolor!='y'){

    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[4][2][i]=cube->surface[3][0][D-1-i];
      nextcube->surface[2][2][i]=cube->surface[4][2][i];
      nextcube->surface[1][2][i]=cube->surface[2][2][i];
      nextcube->surface[3][0][D-1-i]=cube->surface[1][2][i];
    }

    Lrot(nextcube, cube, 0);


    nextcube->ope=-1;
    nextcube->opecolor='y';


    nextcube=cube->next[k++];

    for(i=0;i<D;i++){surface[4][2][i]=cube->surface[1][2][i];
      nextcube->surface[2][2][i]=cube->surface[3][0][D-1-i];
      nextcube->surface[1][2][i]=cube->surface[4][2][i];
      nextcube->surface[3][0][D-1-i]=cube->surface[2][2][i];
    }

    rot(nextcube, cube, 0);

    nextcube->ope=0;
    nextcube->opecolor='y';


    nextcube=cube->next[k];

    for(i=0;i<D;i++){surface[4][2][i]=cube->surface[2][2][i];
      nextcube->surface[2][2][i]=cube->surface[1][2][i];
      nextcube->surface[1][2][i]=cube->surface[3][0][D-1-i];
      nextcube->surface[3][0][D-1-i]=cube->surface[4][2][i];
    }

    Rrot(nextcube, cube, 0);

    nextcube->ope=1;
    nextcube->opecolor='y';
  }

}



void Lrot(struct node *next, struct node *original, char s)
{
  char i,j;

  for(i=0;i<D;i++)surface[s][i][j]=original->surface[s][j][D-1-i];   /*左回転*/
}

void Rrot(struct node *next, struct node *original, char s)
{
  char i, j;

  for(i=0;i<D;i++)surface[s][i][j]=original->surface[s][D-1-j][i];    /*右回転*/
}


void rot(struct node *next, struct node *original, char s)
{
  char i,j;

  for(i=0;i<D;i++)surface[s][i][j]=original->surface[s][D-i-1][D-1-j];    /*180度回転*/
}

/*まだ続く*/

ルービックキューブプログラム

/*人工知能の授業で習った知識を総動員して書いた、3x3x3 のルービックキューブを解くＣプログラム。

A*（エースター）探索、双方向探索、ヒューリスティック関数、ハッシュ関数の合わせ技。

人間がやるようなパターンをなぞる方法じゃなくて、常に最短手順を見つけることを保証する。*/

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

#define D 3   
   /*3x3x3のルービックキューブ。ここを４にしても4x4x4が解けるわけじゃない*/

 
struct node{
  char surface[6][D][D];    
  /*ルービックキューブ各面の情報*/

  unsigned int cost;        
   /*今の状態に何手で来たかを各ノードに記憶*/
  unsigned int heuristic;    
  /*このノードのヒューリスティック値*/
  unsigned int expectation;  
  /*heuristic+cost*/
  long double hash;         
  /*前に展開したノードと同じノードを展開しないためにハッシュ値を使う*/

  struct node *next[15];   
   /*ここから展開される子ノードへのポインタ*/
  struct node *reverse;    
   /*親ノードへのポインタ。最後に解へのパスをたどるめに使う*/
  struct node *nextleaf;   
   /*現在のリーフをリスト構造でつなぐ。次のリーフへのポインタ*/
  struct node *revleaf;     
  /*前のリーフへのポインタ*/
  struct node *nodelist;  
    /*ハッシュ値を比べるために,生成したノードをすべてリニアにつなぐ。次のノードへのポインタ*/
  struct node *revnode;   
    /*一つ前のノードへのポインタ*/

  char ope;                
  /*親ノードから,どんな状態変化をされて来たのかを記憶*/
  char opecolor;          
   /*親ノードからこの状態に来るときに,どの面を回したのか記憶*/

}root, goal, *minG, leaflist, endleaf, nodeend;

unsigned int min;      /*heuristic+costの最小値*/


void start(void);         
 /*rootの初期化など*/
void develop(struct node *cube); 
     /*ノードを展開する*/
void allocate(struct node *cube);  
   /*ノードを展開するための,メモリを確保*/
void heuristic(struct node *cube);  
  /*ヒューリスティック関数*/
void operate(struct node *cube);   
   /*生成したノードにの状態遷移を行う*/
void Rrot(struct node *next, struct node *original, char s); 
   /*一面を右に90度回転*/
void Lrot(struct node *next, struct node *original, char s); 
   /*一面を左に90度回転*/
void rot(struct node *next, struct node *original, char s); 
    /*一面を180度回転*/
void search(void);     
    /*heuristic+costが最小のリーフを探す*/
void output(void);    
     /*解へのパスをたどって解法を表示*/
void exception(void);    
  /*rootを展開するときだけちょっと特別*/


int main(void)
{
  unsigned int depth=0;


  start();    /*いろんなものを初期化*/

  develop(&root);  /*rootを展開*/

  exception();   /*rootを展開その２*/

  search();     /*展開すべきリーフを探す*/

  while(minG->heuristic){    /*ゴール状態でない限りループ*/

    if(minG->cost>depth)
      printf("%dn",++depth);  /*現在展開した一番深いノードの深さを表示*/

    develop(minG); /*リーフを展開*/
    search();      /*次に展開するリーフを探す*/

  }

  output();    /*解法を表示*/

  return 0;
}



void start(void)
{
  char i,j,k;

  for(i=0;i<6;i++)next[i]);   /*展開した各ノードのヒューリスティック値を計算*/

}



void allocate(struct node *cube)
{
  char i,j,k,l;
  struct node *nextcube;

  nextcube=(struct node *)malloc(sizeof(struct node)*15);  /*メモリ確保*/
  if(!nextcube){
    printf("メモリ割り当てエラーan");
    exit(1);
  }

  nodeend.revnode->nodelist=&nextcube[0];    /*ノードリストにつなげる*/

  cube->revleaf->nextleaf=&nextcube[0];     /*リーフリストにつなげる*/
  nextcube[0].revleaf=cube->revleaf;



  for(i=0;i<14;i++){    /*生成したノードをリストにつなげて,親と同じ状態をコピー*/next[i]=&nextcube[i];
    nextcube[i].reverse=cube;
    nextcube[i].nodelist=&nextcube[i+1];

    for(k=0;k<6;k++)surface[k][j][l];

    nextcube[i].cost=1+cube->cost;
    nextcube[i].nextleaf=&nextcube[i+1];
    nextcube[i+1].revleaf=&nextcube[i];

  }

  cube->next[14]=&nextcube[14];
  nextcube[14].reverse=cube;
  nextcube[14].nodelist=&nodeend;
  nodeend.revnode=&nextcube[14];

  for(k=0;k<6;k++)surface[k][j][l];

  nextcube[14].cost=cube->cost+1;
  nextcube[14].nextleaf=cube->nextleaf;
  cube->nextleaf->revleaf=&nextcube[14];

}

/*続く*/