c++ - 递归解决方案未按预期工作/遇到错误

Question

我正在寻求一些帮助，以解决我之前模糊询问过的问题，即递归地解决 15-peg 纸牌游戏。当我编译和运行它时，我不断收到奇怪的错误，其中大多数说“堆栈溢出”或者我遇到段错误。这是我目前所拥有的，其中“board[15]”代表 15 钉板，“moves[36]”代表所有可能的移动。递归应该在只剩下一个钉子时发现。

#include <iostream>

using namespace std;                               

void solveGame(int a[15], int b[36][3], int c[15][4]);

void chooseMove (int a[15], int b[36][3], int openSpace, int c[15][4]);

int findEmpty (int a[15]);

int pegCount (int a[15]);

bool isPeg (int peg, int a[15]);

int usedVals[15] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

int d = 0;

int index = 0;

int main ()
{
    int openSpace = 5;

    int board[15]= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

    board[openSpace] = 0;

    int alreadyMoved[15][4];                                                                                                        

    int moves[36][3] = {{0, 1, 3},
                        {0, 2, 5},
                        {1, 3, 6},
                        {1, 4, 8},
                        {2, 4, 7},
                        {2, 5, 9},
                        {3, 6, 10},
                        {3, 7, 12},
                        {3, 1, 0},
                        {3, 4, 5},
                        {4, 7, 11},
                        {4, 8, 13},
                        {5, 9, 14},
                        {5, 8, 12},
                        {5, 2, 0},
                        {5, 4, 3},
                        {6, 3, 1},
                        {6, 7, 8},
                        {7, 4, 2},
                        {7, 8, 9},
                        {8, 4, 1},
                        {8, 7, 6},
                        {9, 5, 2},
                        {9, 8, 7},
                        {10, 6, 3},
                        {10, 11, 12},
                        {11, 7, 4},
                        {11, 12, 13},
                        {12, 7, 3},
                        {12, 8, 5},
                        {12, 11, 10},
                        {12, 13, 14},
                        {13, 8, 4},
                        {13, 12, 11},
                        {14, 9, 5},
                        {14, 13, 12}};


    solveGame(board, moves, alreadyMoved);

    for (int i = 0; i < 13; i++)
        cout << alreadyMoved[i][0] << " " << alreadyMoved[i][1] << " " < <alreadyMoved[i][2] << endl;

    return 0;
}

// main recursive function
void solveGame (int a[15], int b[36][3], int c[15][4]
{
int empSpace;
int moveIndex;

    if (pegCount(a) < 2) {
        cout<<"game over"<<endl;
    } else {
        empSpace = findEmpty(a);
        chooseMove(a, b, empSpace, c);
        solveGame(a, b, c);
    }
}

// supposed to pick a move that is applicable to the board otherwise it find a new move
void chooseMove (int a[15], int b[36][3], int openSpace, int c[15][4])
{
int i = 0;

    while (1) {
        if (i < 36 && b[i][2] == openSpace && isPeg(b[i][0],a) && isPeg(b[i][1],a)) {
            a[b[i][0]] = 0;
            a[b[i][1]] = 0;
            a[b[i][2]] = 1;

            c[d][0] = b[i][0];
            c[d][1] = b[i][1];
            c[d][2] = b[i][2];
            c[d][3] = i;

            d++;

            index = 0;

            for (int v = 0; v < 15; v++)
                usedVals[v] = -1;

            break;
        } else if (i > 35) {
            a[b[c[d-1][3]][0]] = 1;
            a[b[c[d-1][3]][1]] = 1;
            a[b[c[d-1][3]][2]] = 0;

            c[d-1][0] = 0;
            c[d-1][1] = 0;
            c[d-1][2] = 0;
            c[d-1][3] = 0;

            usedVals[index] = openSpace;

            index++;

            int newOpen = findEmpty(a);

            chooseMove(a, b, newOpen, c);
        }

        i++;
    }
}

// counts the pegs on the board in order to cancel recursion
int pegCount (int a[15])
{
    int count = 0;
    for (int i = 0; i < 15; i++)
        if (a[i] == 1)
            count++;
    return count;
}

// finds an empty space that hasn't already been found faulty 
int findEmpty (int a[15])
{
    for (int i = 0; i < 15; i++) {
        for(int j = 0; j < 15; j++) {
            if(a[i] == 0 && i != usedVals[j] && usedVals[j] > -1)
                return i;
        }
    }
}


// tests if current index is a peg 
bool isPeg (int peg, int a[15])
{
    return a[peg] == 1;
}

Answer 1

快速浏览会发现很多潜在问题，但我认为这可能归结为您传递数组的方式。数组通过引用而不是值传递，因此递归函数使用数组的单个拷贝，我认为这不是您想要的。因此，您永远找不到结束移动，这将使您从无限递归中获得计算器溢出。

尝试在每个递归级别分配数组的新拷贝。有些人会希望你为此使用 new 或 malloc，因为他们觉得介绍 C++ 应该是一场火上浇油的考验，你必须掌握内存管理才能做任何事情有用。相反，我会建议您根本不要使用数组；使用一个在按值传递时可以正常工作的集合类(我认为 POD 的 std::vector 会这样做)并且集合类将按照您的代码似乎期望的方式创建数组的拷贝。

当您真正想要广度优先搜索时，您可能还会遇到在 chooseMove 中进行深度优先搜索的问题。