c - 限定DFS、スライドパズルアプリ、経路探索

Question

シンプルなスライド パズル (Loyd) ソルバーを書いています。3 x 3 以上の寸法のパズルの任意の解決可能な構成を解決したいと考えています。しかし、再帰の実装に行き詰まりました。私はツリーとスタックを持っています。

  typedef struct Node{
    int **array;
    struct Node *left;
    struct Node *right;
    struct Node *up;
    struct Node *down;
    struct Node *parent;
    }Node;

Node* newNode(Node *parent, int **array){
    Node* u;
    u = malloc(sizeof(Node));
    if (u == NULL){
    printf("OUT OF MEMORY!");
    /* Free memory here.*/
    exit(1);
    }
    u->array = array;
    u->down = NULL;
    u->right = NULL;
    u->up = NULL;
    u->left = NULL;
    u->parent = parent;
    return u;
}

void setLeftNode(Node *parent, Node *child) {
  parent->left = child;
    }
/* setRightNode,Up,Down...*/


int isLeftChild (Node *node){
    if (node->parent == null) {return 0;}
    else{
        if (node->parent->left == node){return 1;}
        else{return 0;}
    }
}
/*is Right,Up,Down...*/

スタックには静的サイズがあります。今、私は解決策を見つける方法を持っています。しかし、再帰を実装する方法と、作成されたノードを保存してパスを見つける方法がわかりません。これまでのところ、私は持っています：

int trySolvePuzzle(stack *z, stack *tz, int size_array, int limit){
    int x,y;
    int duplicate = 1;
    Node *parent = NULL;
    Node *helper = NULL;
    returnPeak(z,&parent);

    /* SOLVED?*/
    if ((isSolved(parent->array, size_array)) == 1){return 1;}

    x = findCoordinatesZeroX(parent->array,size_array);
    y = findCoordinatesZeroY(parent->array,size_array);


        if(y!=0){
            helper = newNode(parent, toLeft(parent->array, size_array, x, y));
            setLeftNode(parent, helper);
            duplicate = searchForDuplicate(z, tz, helper, size_array);
            }
            else{
                /*????*/
            }

    /* It is NOT in PATH*/
    if (duplicate == 0){
        push(z, &helper);
        if (trySolvePuzzle(z, tz, size_array, limit+1) == 1){
            return 1;
        }
    }
        /*BACKTRACK*/
        pop(z, &parent);

            x = findCoordinatesZeroX(parent->array,size_array);
            y = findCoordinatesZeroY(parent->array,size_array);

    if (y!=size_array-1){
    helper = newNode(parent, toRight(parent->array, size_array, x, y));
                setRightNode(parent, helper);
                duplicate = searchForDuplicate(z, tz, helper, size_array);
                }
                else{
                    /*????*/
                }

        if (duplicate == 0){
            push(z, &helper);
            if (trySolvePuzzle(z, tz, size_array, limit+1) == 1){
                return 1;
            }}

        pop(z, &parent);
            x = findCoordinatesZeroX(parent->array,size_array);
            y = findCoordinatesZeroY(parent->array,size_array);


        if (x != 0){
        helper = newNode(parent, toUp(parent->array, size_array, x, y));
                    setUpNode(parent, helper);
                    duplicate = searchForDuplicate(z, tz, helper, size_array);}
                    else{
                    /*????*/
                    }

            if (duplicate == 0){
                push(z, &helper);
                if (trySolvePuzzle(z, tz, size_array, limit+1) == 1){
                    return 1;
                }   
                }
            pop(z, &parent);

            x = findCoordinatesZeroX(parent->array,size_array);
            y = findCoordinatesZeroY(parent->array,size_array);

                if (x!=size_array-1){

            helper = newNode(parent, toDown(parent->array, size_array, x, y));
                        setDownNode(parent, helper);

                        duplicate = searchForDuplicate(z, tz, helper, size_array);}else{
                        /* ???? */
                        }


                if (duplicate == 0){
                    push(z, &helper);
                    if (trySolvePuzzle(z, tz, size_array, limit+1) == 1){
                        return 1;
                    }}
                pop(z, &parent);

                /*CAN NOT CONTINUE*/
            return 0;
    }

ではどうすればいいのか、例えば。y = 0 なので、新しい左構成を作成できません。私は戻る必要があります。しかし、そうすると、無限ループに陥ります。任意のサイズのパズル > 2 を解きたいことに注意してください。

そして、スタック内の重複を検索する私の関数は次のとおりです。

int searchForDuplicate(stack *z, stack *tz, Node *helper, int size_array){
    int duplicate = 1;
    int q,w = 0;
    Node *temp = NULL;
    while ((pop(z, &temp))==1){
        //pop(z, &temp);
        for (q = 0; q < size_array; q++){
            for (w = 0; w < size_array; w++){
                if (temp->array[q][w]!= helper->array[q][w]){duplicate = 0;}

            }
        }
        push(tz, &temp);
    }

    while ((pop(tz, &temp))==1){
    //pop(tz, &temp);
        push(z, &temp);
    }

    return duplicate;
}

誰でも助けることができますか？お時間をいただきありがとうございます。:)