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;
}

任何人都可以帮忙吗？感谢您的时间。:)