15パズル問題

[RyukyuOB]

こんにちは。今スライドパズルの解法について研究しています。
このスレッドの過去ログを参照していたところ、
http://dixq.net/forum/viewtopic.php?f=3&t=7158
このスレッドを見つけました。
なのでこのスレッドのコード通りにコンパイルしてみたところ、3x3の8パズルなら解けたのですが、
4x4の15パズルになると解答を出してくれません。
コンパイルは問題なく通ってしまうためさらに問題点が分からなくなりました。
ここが違うんじゃないの？程度でよろしいので解答してくださると嬉しいです。

コード:

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

#define D 4    /*D×D-1 パズル。　このマクロを変えればどんな大きさのパズルでも探索できる*/
int goal_state[16] = {
1,2,3,4,
5,6,7,8,
9,10,11,12,
13,14,15,16 
}; // ゴールのリスト

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++){
            for(j=0;j<D;j++){
                printf("%3d", cur->block[i][j]);       /*解法を表示*/
                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++;
            goal->block[i][j] = goal_state[i*3+j];
            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, 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;
}

[RyukyuOB]

自己解決しました。