c++ - 递归解决方案未按预期运行/出现错误

我正在寻找一些有关我之前曾隐约询问过的问题的帮助，该问题以递归方式解决了15钉纸牌。编译和运行它时，我总是收到奇怪的错误，其中大多数都说“堆栈溢出”，或者我遇到了段错误。这就是我到目前为止的内容，其中“ 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;
}

最佳答案

快速浏览显示了很多潜在的问题，但是我认为这可能归结为您传递数组的方式。数组是按引用而不是按值传递的，因此递归函数正在处理数组的单个副本，我认为这不是您想要的。因此，您永远都找不到最终的举动，这将使您从无限递归中获得堆栈溢出。

尝试在每个递归级别分配新的数组副本。有些人会希望您为此使用new或malloc，因为他们认为对C ++的介绍应该是一次尝试，您必须掌握内存管理才能做任何有用的事情。相反，我建议您不要使用任何数组。使用一个集合类，该集合类在按值传递时将正常工作（我认为POD的std :: vector会做到这一点），并且该集合类将按照代码似乎期望的方式创建数组的副本。

当您确实想要广度优先搜索时，您可能还存在在chooseMove中进行深度优先搜索的问题。

关于c++ - 递归解决方案未按预期运行/出现错误，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9196487/