рекурсивное решение не работает должным образом / работает с ошибками

Question

Я ищу некоторую помощь по проблеме, о которой я неопределенно спрашивал ранее, которая рекурсивно решает пасьянс с 15 колышками.Я продолжаю получать странные ошибки, когда я компилирую и запускаю его, большинство из них говорят «переполнение стека» или что я получаю ошибку сегмента.Это то, что я имею до сих пор, где «доска [15]» представляет доску с 15 колышками, а «ходы [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 ++ должно быть испытанием, когда вам нужно освоить управление памятью, чтобы сделать что-нибудь полезное.Вместо этого я бы посоветовал вам вообще не использовать массивы;используйте класс коллекции, который будет работать должным образом при передаче по значению (я думаю, что std :: vector из POD сделает это), и класс коллекции создаст копии ваших массивов так, как, как кажется, ожидает ваш код.

Выможет также возникнуть проблема с поиском по глубине в ChooseMove, когда вы действительно хотите поиск по ширине.

Answer 2

Обычно вы получаете переполнение стека, когда ваше условие выхода не работает, но здесь вы также передаете свои параметры по значению, которое может переполнить ваш стек даже при нормальной работе.

Я предлагаю вам передать ваши массивыпо ссылке или лучше в std::vector.std::vector - это небольшой объект, который содержит реальные данные в выделенном для кучи пространстве.Вы даже можете вернуть их.

Я также предлагаю вам запустить вашу программу в отладчике, это самый простой и эффективный способ выяснить, что именно не так.

Answer 3

Переполнение стека при использовании рекурсивности довольно распространено. Это связано с тем, что возвращаемые значения для вызовов функций хранятся в стеке, и стек продолжает заполняться до тех пор, пока функция не вернется. Если рекурсивность идет слишком глубоко, вы заканчиваете тем, что заполняете весь свой стек и переполняете его, что также вызывает SEGV.