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

/*2x2x2のルービックキューブを解くＣプログラム。この場合、探索空間が3x3x3に比べてかなり小さくて、どんな状態からでも解ける。アルゴリズムや入力データなどは昨日のと同じ考え方。実行結果はまたこんど。*/

ソースはこちら

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

#define D 2      /*2x2x2のルービックキューブ。ここを４にしても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[6];     
 /*ここから展開される子ノードへのポインタ*/
  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)*6);  /*メモリ確保*/
  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<5;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[5]=&nextcube[5];
  nextcube[5].reverse=cube;
  nextcube[5].nodelist=&nodeend;
  nodeend.revnode=&nextcube[5];

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

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

}




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


  if(cube->opecolor!=1){

    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=1;


    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=1;


    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=1;

  }


  if(cube->opecolor!=2){

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

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

    Lrot(nextcube, cube, 2);

    nextcube->ope=-1;
    nextcube->opecolor=2;


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

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

    rot(nextcube, cube, 2);

    nextcube->ope=0;
    nextcube->opecolor=2;


    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][1][i];
      nextcube->surface[5][1][i]=cube->surface[1][D-1-i][1];
      nextcube->surface[1][D-1-i][1]=cube->surface[0][0][D-1-i];
    }

    Rrot(nextcube, cube, 2);

    nextcube->ope=1;
    nextcube->opecolor=2;
  }


  if(cube->opecolor!=0){

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

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

    Lrot(nextcube, cube, 0);


    nextcube->ope=-1;
    nextcube->opecolor=0;


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

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

    rot(nextcube, cube, 0);

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


    nextcube=cube->next[k];

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

    Rrot(nextcube, cube, 0);

    nextcube->ope=1;
    nextcube->opecolor=0;
  }

}



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度回転*/
}

/*続く*/