我遇到了以下问题：这个游戏的目标是从棋盘上移除所有棋子，只留下一个。完美的游戏应该只在中心位置（黑色棋子）留下一个棋子。基本规则是通过一个棋子跳过另一个棋子来移除棋子。我只能在棋子的另一侧有空位，并且我就在棋子之前时跳过它。
我试图理解以下递归函数，它试图使用深度优先搜索来解决这个问题。虽然我对问题在正常情况下的工作原理有一定的了解，也就是说，当我有棋子要移除时。但我很难理解在没有可能继续消除棋子的情况下，递归步骤是如何进行的，在接下来的步骤中，我不得不恢复之前移除的棋子（回溯），以便找到另一条通往解决方案的路径。这似乎消耗了大量的执行时间。
函数的一般过程如下：
- 使用嵌套的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 5000typedef 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(); -
执行时间过长（几小时仍未找到解决方案）是否正常？有没有办法提高执行时间？
回答：
将会生成很多状态。最初，有四种可能的移动。每种移动都会导致几种可能的移动，依此类推。当使用回溯时，你必须实际存储这些状态空间。
你可以将这种搜索视为一棵树，根是初始状态。（所以，初始状态生成四个子节点…依此类推！）
使用回溯时
每当到达死胡同时，应该有一个布尔函数来找出是否可能移动，如果没有可能的移动，我们就回到导致死胡同的父节点，并尝试父节点的其他子节点。
我们一直重复上述过程，直到找到解决方案。
