Skip to content

Instantly share code, notes, and snippets.

@reireias

reireias/hako.c

Last active August 6, 2020 11:25
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save reireias/863ef109f23fb7eb0d2fa378e690aff4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save reireias/863ef109f23fb7eb0d2fa378e690aff4 to your computer and use it in GitHub Desktop.
Download ZIP
箱入り娘パズルの最小手を求めるプログラム（C言語）
Raw
hako.c
// 約9年前の学生時代に実装した内容
// これを24時間以内に仕上げたらしい
/**
+----+ +-----------+ +----+
| 父 | | | | 母 |
| | | 箱 入 | | |
| | | り 娘 | | |
| 親 | | | | 親 |
+----+ +-----------+ +----+
+----+ +-----------+ +----+
| 祖 | | 兄 弟 | | 祖 |
| | +-----------+ | |
| | +----+ +----+ | |
| 父 | | 華 | | 書 | | 母 |
+----+ +----+ +----+ +----+
+----+ +----+
| 琴 | | 茶 |
+----+ +----+
**/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//初期配置
int first[5][4]={
{3,2,2,3},
{4,2,2,4},
{3,5,5,3},
{4,1,1,4},
{1,0,0,1}
};
int x[5][4];//現在の状態
int y[5][4];
char con[32];//現在の状態の文字列
int end_flag=0;//解が見つかったか
char solution[200][32];//最後の出力に使う
//状態記憶木、二分木に使用
struct mtree{
char data[32];
int hand;//今何手目か
struct mtree* parent;//前の手はどれかを格納。二分木の親ではない。
struct mtree* left;//二分木の左
struct mtree* right;
struct mtree* next;//キューの次
};
struct mtree *root;//根
struct mtree *now;//現在の手
struct mtree *q_first;//キューの最初
struct mtree *q_last;//キューの最後
struct mtree *kai;//解のポインタ
void condition(int array[5][4]){//状態を文字列に変換する関数,文字列conに現在の状態が記述される
int i,j;
int k=0;
char* r="";
strcpy(con,"");
for(i=0;i<5;i++){
for(j=0;j<4;j++){
con[k]=(char)(array[i][j]+48);
k++;
}
}
//printf("\n%s\n",con);
}
void reverse_con(char *str){//状態を表す文字列から配列yに復元する関数
int i,j,k;
k=0;
for(i=0;i<5;i++){
for(j=0;j<4;j++){
y[i][j]=(int)str[k]-48;
k++;
}
}
}
struct mtree * add_tree(struct mtree *p,char *str){//二分木追加関数
struct mtree *q;
//printf("%s\n",str);
q=(struct mtree *)malloc(sizeof(struct mtree));
if( q == NULL ){
fprintf( stderr, "Out of Memory\n" );
exit( EXIT_FAILURE );
}
strcpy(q->data,str);
q->hand=now->hand+1;
q->parent=now;
q->left=NULL;
q->right=NULL;
q->next=NULL;
q_last->next=q;
q_last=q;
if(str[17]=='2'&&str[18]=='2'){
end_flag=1;
kai=q;
}
return q;
}
struct mtree * find_tree(struct mtree *p,char *str){//二分木探索関数
if(p==NULL){
printf("p=NULL\n");
return 0;
}
if(strcmp(str,p->data)==0){
//printf("同じ物発見\n");
return 0;
}else if(strcmp(str,p->data)<0){
if(p->left!=NULL){
find_tree(p->left,str);
}else{
p->left=add_tree(p->left,str);
}
}else{
if(p->right!=NULL){
find_tree(p->right,str);
}else{
p->right=add_tree(p->right,str);
}
}
return 0;
}
void next_hand(int array[5][4]){//次の手を探す関数
int i,j,k,l;
int zero1[2],zero2[2];//0の位置を記憶する配列
int next_array[5][4];//変化後の配列
zero1[0]=-1;//zero1に座標が入ったかどうかの判定に使う
//next_array[][]をとりあえず現在の手の形にする
for(i=0;i<5;i++){
for(j=0;j<4;j++){
next_array[i][j]=array[i][j];
}
}
//値が0の座標を探す
for(i=0;i<5;i++){
for(j=0;j<4;j++){
if(array[i][j]==0&&zero1[0]==-1){
zero1[0]=i;
zero1[1]=j;
}else if(array[i][j]==0&&zero1[-1]!=-1){
zero2[0]=i;
zero2[1]=j;
}
}
}
//printf("zero1=x[%d][%d]\nzero2=x[%d][%d]\n",zero1[0],zero1[1],zero2[0],zero2[1]);
//１個目の0について
i=zero1[0];
j=zero1[1];
//特殊パターン（L字移動）＋２マス移動の処理
if(i!=4&&array[i+1][j]==0){//下が０
if(j!=3&&array[i][j+1]==1){//右が１
next_array[i+1][j]=1;
next_array[i][j+1]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j!=0&&array[i][j-1]==1){//左が１
next_array[i+1][j]=1;
next_array[i][j-1]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j!=3&&array[i+1][j+1]==1){//右下が１
next_array[i][j]=1;
next_array[i+1][j+1]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j!=0&&array[i+1][j-1]==1){//左下が１
next_array[i][j]=1;
next_array[i+1][j-1]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i!=0&&array[i-1][j]==1){//上が１
next_array[i-1][j]=0;
next_array[i+1][j]=1;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i>1&&array[i-1][j]==4){//上が４
next_array[i-2][j]=0;
next_array[i-1][j]=0;
next_array[i][j]=3;
next_array[i+1][j]=4;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i<3&&array[i+2][j]==1){//下が１
next_array[i][j]=1;
next_array[i+2][j]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i<3&&array[i+2][j]==3){//下が３
next_array[i][j]=3;
next_array[i+1][j]=4;
next_array[i+2][j]=0;
next_array[i+3][j]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
}
if(j!=3&&array[i][j+1]==0){//右が０
if(i!=0&&array[i-1][j]==1){//上が１
next_array[i][j+1]=1;
next_array[i-1][j]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i!=4&&array[i+1][j]==1){//下が１
next_array[i][j+1]=1;
next_array[i+1][j]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i!=0&&array[i-1][j+1]==1){//右上が１
next_array[i][j]=1;
next_array[i-1][j+1]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(i!=4&&array[i+1][j+1]==1){//右下が１
next_array[i][j]=1;
next_array[i+1][j+1]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j!=0&&array[i][j-1]==1){//左が１
next_array[i][j-1]=0;
next_array[i][j+1]=1;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j!=0&&array[i][j-1]==5){//左が５
next_array[i][j-2]=0;
next_array[i][j-1]=0;
next_array[i][j]=5;
next_array[i][j+1]=5;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j<2&&array[i][j+2]==1){//右が１
next_array[i][j]=1;
next_array[i][j+2]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
if(j<2&&array[i][j+2]==5){//右が５
next_array[i][j]=5;
next_array[i][j+1]=5;
next_array[i][j+2]=0;
next_array[i][j+3]=0;
condition(next_array);
find_tree(root,con);
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
}
}
//上を見る
if(i!=0){
switch(array[i-1][j]){
case 0:break;
case 1:next_array[i][j]=1;
next_array[i-1][j]=0;
break;
case 2:if(j!=3&&array[i][j+1]==0&&array[i-1][j+1]==2){
next_array[i][j]=2;
next_array[i][j+1]=2;
next_array[i-2][j]=0;
next_array[i-2][j+1]=0;
}else if(j!=0&&array[i][j-1]==0&&array[i-1][j-1]==2){
next_array[i][j]=2;
next_array[i][j-1]=2;
next_array[i-2][j]=0;
next_array[i-2][j-1]=0;
}
break;
case 3:break;
case 4:next_array[i-2][j]=0;
next_array[i-1][j]=3;
next_array[i][j]=4;
break;
case 5: if(j!=3&&array[i][j+1]==0&&array[i-1][j+1]==5){
next_array[i][j]=5;
next_array[i][j+1]=5;
next_array[i-1][j]=0;
next_array[i-1][j+1]=0;
}else if(j!=0&&array[i][j-1]==0&&array[i-1][j-1]==5){
next_array[i][j]=5;
next_array[i][j-1]=5;
next_array[i-1][j]=0;
next_array[i-1][j-1]=0;
}
break;
default:break;
}
}
//移動があったならば木へぶち込む
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\ntop\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//下を見る
if(i!=4){
switch(array[i+1][j]){
case 0: break;
case 1:next_array[i][j]=1;
next_array[i+1][j]=0;
break;
case 2:if(j!=3&&array[i][j+1]==0&&array[i+1][j+1]==2){
next_array[i][j]=2;
next_array[i][j+1]=2;
next_array[i+2][j]=0;
next_array[i+2][j+1]=0;
}else if(j!=0&&array[i][j-1]==0&&array[i+1][j-1]==2){
next_array[i][j]=2;
next_array[i][j-1]=2;
next_array[i+2][j]=0;
next_array[i+2][j-1]=0;
}
break;
case 3:next_array[i][j]=3;
next_array[i+1][j]=4;
next_array[i+2][j]=0;
break;
case 4:break;
case 5: if(j!=3&&array[i][j+1]==0&&array[i+1][j+1]==5){
next_array[i][j]=5;
next_array[i][j+1]=5;
next_array[i+1][j]=0;
next_array[i+1][j+1]=0;
}else if(j!=0&&array[i][j-1]==0&&array[i+1][j-1]==5){
next_array[i][j]=5;
next_array[i][j-1]=5;
next_array[i+1][j]=0;
next_array[i+1][j-1]=0;
}
break;
default:break;
}
}
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\ndown\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//左を見る
if(j!=0){
switch(array[i][j-1]){
case 0:break;
case 1:next_array[i][j]=1;
next_array[i][j-1]=0;
break;
case 2:if(i!=0&&array[i-1][j]==0&&array[i-1][j-1]==2){
next_array[i][j]=2;
next_array[i-1][j]=2;
next_array[i][j-2]=0;
next_array[i-1][j-2]=0;
}else if(i!=4&&array[i+1][j]==0&&array[i+1][j-1]==2){
next_array[i][j]=2;
next_array[i+1][j]=2;
next_array[i][j-2]=0;
next_array[i+1][j-2]=0;
}
break;
case 3:if(i!=4&&array[i+1][j]==0){
next_array[i][j]=3;
next_array[i+1][j]=4;
next_array[i][j-1]=0;
next_array[i+1][j-1]=0;
}
break;
case 4:break;
case 5: next_array[i][j]=5;
next_array[i][j-2]=0;
break;
default:break;
}
}
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\nleft\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//右を見る
if(j!=3){
switch(array[i][j+1]){
case 0: break;
case 1:next_array[i][j]=1;
next_array[i][j+1]=0;
break;
case 2:if(i!=0&&array[i-1][j]==0&&array[i-1][j+1]==2){
next_array[i][j]=2;
next_array[i-1][j]=2;
next_array[i][j+2]=0;
next_array[i-1][j+2]=0;
}else if(i!=4&&array[i+1][j]==0&&array[i+1][j+1]==2){
next_array[i][j]=2;
next_array[i+1][j]=2;
next_array[i][j+2]=0;
next_array[i+1][j+2]=0;
}
break;
case 3:if(i!=4&&array[i+1][j]==0){
next_array[i][j]=3;
next_array[i+1][j]=4;
next_array[i][j+1]=0;
next_array[i+1][j+1]=0;
}
break;
case 4:break;
case 5: next_array[i][j]=5;
next_array[i][j+2]=0;
break;
default:break;
}
}
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\nright\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//２個目の0について
i=zero2[0];
j=zero2[1];
//上を見る
if(i!=0){
switch(array[i-1][j]){
case 0:break;
case 1:next_array[i][j]=1;
next_array[i-1][j]=0;
break;
case 2:break;
case 3:break;
case 4:next_array[i-2][j]=0;
next_array[i-1][j]=3;
next_array[i][j]=4;
break;
case 5: break;
default:break;
}
}
//移動があったならば木へぶち込む
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\ntop\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//下を見る
if(i!=4){
switch(array[i+1][j]){
case 0:break;
case 1:next_array[i][j]=1;
next_array[i+1][j]=0;
break;
case 2: break;
case 3:next_array[i][j]=3;
next_array[i+1][j]=4;
next_array[i+2][j]=0;
break;
case 4:break;
case 5: break;
default:break;
}
}
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\ndown\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//左を見る
if(j!=0){
switch(array[i][j-1]){
case 0:break;
case 1:next_array[i][j]=1;
next_array[i][j-1]=0;
break;
case 2: break;
case 3: break;
case 4:break;
case 5: next_array[i][j]=5;
next_array[i][j-2]=0;
break;
default:break;
}
}
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
/*
//デバッグ出力
printf("\nleft\n");
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",next_array[k][l]);
}
printf("\n");
}*/
//next_arrayをもとに戻す
for(k=0;k<5;k++){
for(l=0;l<4;l++){
next_array[k][l]=array[k][l];
}
}
//右を見る
if(j!=3){
switch(array[i][j+1]){
case 0:break;
case 1:next_array[i][j]=1;
next_array[i][j+1]=0;
break;
case 2: break;
case 3: break;
case 4:break;
case 5: next_array[i][j]=5;
next_array[i][j+2]=0;
break;
default:break;
}
}
if(next_array[i][j]!=array[i][j]){
condition(next_array);
find_tree(root,con);
}
}
void print_tree(struct mtree *p){
printf("%s\t%d\t%s\t%s\t%s\t%s\n",p->data,p->hand,p->parent->data,p->left->data,p->right->data,p->next->data);
if(p->left!=NULL){
print_tree(p->left);
}
if(p->right!=NULL){
print_tree(p->right);
}
}
void print_kai(struct mtree *r){//解の順序を出力する関数
printf("%d\t%s\n",r->hand,r->data);
strcpy(solution[r->hand],r->data);
if(r->parent!=NULL){
print_kai(r->parent);
}
}
void print_array(char *str){//図を出力する関数
int k,l;
reverse_con(str);
for(k=0;k<5;k++){
for(l=0;l<4;l++){
printf("%d ",y[k][l]);
}
printf("\n");
}
printf("\n");
}
int main(){
int i,j;
char s[32];
for(i=0;i<5;i++){
for(j=0;j<4;j++){
x[i][j]=first[i][j];
}
}
condition(x);
root=malloc(sizeof(struct mtree));
strcpy(root->data,con);
root->hand=0;
root->parent=NULL;
root->left=NULL;
root->right=NULL;
root->next=NULL;
now=root;
q_first=root;
q_last=root;
//キューの最初を処理する
i=0;
while(end_flag==0){
//while(now->hand<2){
now=q_first;
reverse_con(q_first->data);
next_hand(y);
q_first=now->next;
i++;
//printf("hand=%d\n",now->hand);
//print_array(now->data);
}
if(end_flag==1){
printf("success!\n");
printf("%s\t%d\n",kai->data,kai->hand);
print_kai(kai);
}
//printf("%d\n",i);
for(i=0;i<82;i++){
//printf("%s\n",solution[i]);
print_array(solution[i]);
}
//printf("[root]\n%s\nhand:%d\n",root->data,root->hand);
//find_tree(root,"32234224355341141001");
//find_tree(root,"32234224355341141002");
//printf("%s\n",now->data);
//printf("%s\n",root->right->data);
//printf("data\thand\tparent\tleft\tright\tnext\n");
//print_tree(root);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment