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

Question

我正在寻求一些帮助来解决我之前隐约询问过的问题，即递归解决 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;
}

Answer 1

快速浏览一下会发现很多潜在的问题，但我认为这可能归结为传递数组的方式。数组是按引用传递的，而不是按值传递的，因此递归函数正在处理数组的单个副本，我认为这不是您想要的。因此，你永远找不到结束动作，这将使你因无限递归而导致堆栈溢出。

尝试在每个递归级别分配一个新的数组副本。有些人会希望你为此使用 new 或 malloc ，因为他们觉得 C++ 入门应该是一场激烈的考验，你必须掌握内存管理才能做任何事情有用。相反，我建议你根本不要使用数组；使用按值传递时可以正常工作的集合类（我认为 POD 的 std::vector 会执行此操作），并且集合类将按照代码预期的方式创建数组的副本。

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

Answer 2

使用递归时堆栈溢出很常见。这是因为函数调用的返回值存储在堆栈中，并且只要函数不返回，堆栈就会一直填满。如果递归太深，最终会填满整个堆栈并使其溢出，这也会导致 SEGV。

Answer 3

通常，当退出条件不起作用时，您会遇到堆栈溢出，但在这里您还按值传递参数，即使在正常操作中，这也可能会溢出堆栈。

我建议您通过引用或更好地在 std::vector 中传递数组。 std::vector 是一个小对象，它将实际数据保存在堆分配的空间中。您甚至可以退回这些。

我还建议您在调试器中启动程序，这是找出到底出了什么问题的最简单、最有效的方法。