在 DFS 中使用递归来解决使用 C 的逻辑游戏？

Question

我有以下问题：这个游戏的目标是从棋盘上移除除一个以外的所有钉子。完美的游戏只在中间位置留下一个钉子（黑色的）。基本上，通过用另一个钉子跳过每个钉子来移除钉子。如果另一边有一个空的 space 并且我就在它前面，我只能跳过它。

我试图理解以下尝试使用深度优先搜索解决问题的递归函数。虽然我有点熟悉这个问题在正常情况下是如何工作的，这意味着当我需要移除钉子时。我无法很好地掌握递归步骤，当我最终无法消除钉子的情况时，在接下来的步骤中我不得不提出旧的消除钉子（回溯）以便我会找到解决方案的另一条途径。这似乎消耗了大量的执行时间。

函数的大致流程是：

使用嵌套的 for 循环遍历棋盘。
如果满足以下条件，找到要移动的钉子：
左上右下都有一个直接相邻的。
移除要移除的钉子后，有一个自由的地方可以移动。
如果所有这些条件都成立，我们将更改钉子的状态
如果没有移动钉子的可能性，恢复以前的板配置并寻找另一条路径。

这是预处理器指令：

#include <stdio.h>
#define N 11
/****** Accepted or unaccepted solution ******/
#define YES 1
#define NO 0

/****** Representation of the board ******/
/* 0 - the position is free: no peg is in the position
   1 - a peg is in the postion
   2 - an obstacle is in the position (not part of the board) */  

#define OCCUPIED 1
#define FREE 0
#define WALL 2

/****** Stack size ******/
#define MAXST 5000

typedef char boolean;
/****** Directions where to move *****/
enum dir{NORTH,EAST,SOUTH,WEST};
/****** Directions horizentally ******/
int dx[]={0, 1,0,-1};
/****** Directions Vertically ******/
int dy[]={-1,0,1, 0};

/****** Board Representation ******/
char b[N][N]={
{2, 2,2,2,2,2,2,2,2,2, 2},

{2, 2,2,2,1,0,0,2,2,2, 2},
{2, 2,2,2,0,0,1,2,2,2, 2},
{2, 2,2,2,0,0,0,2,2,2, 2},
{2, 0,0,1,0,0,0,1,1,1, 2},
{2, 0,0,0,0,0,0,0,0,0, 2},
{2, 0,1,0,0,1,0,0,0,0, 2},
{2, 2,2,2,1,0,0,2,2,2, 2},
{2, 2,2,2,0,0,0,2,2,2, 2},
{2, 2,2,2,1,0,0,2,2,2, 2},

{2, 2,2,2,2,2,2,2,2,2, 2}
};

这里是负责寻找解决方案的函数：

    /****** move finds the next move to perform in order to advance in the search ******/
    boolean move(int pegs){
    /****** x - the x position of the peg examined on the board
            y - the y position of the peg examined on the board
            xnear - the x position of the adjascent peg to be removed
            ynear - the y position of the adjascent peg to be removed
            xnew - the new x position of the peg that expelled the removed previous peg
            ynew - the new x position of the peg that expelled the removed previous peg ****/
    int x,y,xnear,ynear,xnew,ynew;

    enum dir d;

    /* Base case 1: solution = one peg left on the whole board */

    /* if(pegs==1){
        return(YES);
    } */

    /* Base case 2: solution = one peg at the center of the board (5,5) */
        if(pegs==1) {
            if (b[5][5]==OCCUPIED)
                return(YES);
            else return(NO);
        }
        /*Scanning the board from top to bottom, left to right*/
        for(x=0;x<N;x++)
            for(y=0;y<N;y++)
            /* In order for the move to occur you need to 1. have a peg in a position */
                if(b[y][x] == OCCUPIED){
                    /**************/
                    /* Finding adjascent pegs to remove from the board */ 
                    for(d=NORTH;d<=WEST;d++){
                        xnear=x+dx[d];
                        ynear=y+dy[d];
                        /*****************/
                        /* 2. Have another peg adjascent to the peg making the move */
                        if(b[ynear][xnear]== OCCUPIED){
                            xnew=xnear+dx[d];
                            ynew=ynear+dy[d];
                            /****************/
                            /* 3. Have the position where the peg will be moving empty */
                            if(b[ynew][xnew]==FREE){
                                b[y][x]=FREE; /* do move */
                                b[ynear][xnear]=FREE;   
                                b[ynew][xnew]=OCCUPIED;
                                pegs--;
                                print_board(b);
                                push(b,x,y,d); // Pushing the action to a stack
                                if(move(pegs)){
                                    return(YES);
                                }

                                b[y][x]=OCCUPIED; /* undo move */
                                b[ynear][xnear]=OCCUPIED;
                                b[ynew][xnew]=FREE;

                                pegs++;
                                pop(); 
                            }
                        }
                    }
                }
            return(NO);
        }

我的问题是：

boolean move(int pegs)函数的递归部分在代码中是如何工作的，它如何跟踪已经扩展到死胡同的案例？我的猜测是在 boolean move(int pegs) 函数中并且准确地说：

        if(move(pegs)){
             return(YES);
        }
        b[y][x]=OCCUPIED; /* undo move */
        b[ynear][xnear]=OCCUPIED;
        b[ynew][xnew]=FREE;
        print_board(b);
        pegs++;
        pop();

执行时间过长才找到解决方案（好几个小时还没找到解决方案）正常吗？有没有办法改善执行时间？

Answer 1

会生成很多状态。最初，有四种可能的移动。这些动作中的每一个都会导致几种可能的动作等等。当你使用回溯时，你必须实际存储这些状态空间。

你可以把这个搜索想象成一棵树，根是初始状态。（所以，初始状态生成四个 children...等等！）

使用回溯时

每当到达死胡同时，应该有一个布尔函数来判断是否可以移动，如果没有任何可能的移动，我们就从死胡同开始 parent到达并尝试 parent 的另一个 children。

我们继续执行上述过程，直到找到解决方案。

在 DFS 中使用递归来解决使用 C 的逻辑游戏？

Using recursion in DFS to solve a logic game using C?

c

recursion

search

artificial-intelligence

depth-first-search

使用回溯时