Решить проблему тура рыцаря на огромной доске? - PullRequest
Новая
       17

Решить проблему тура рыцаря на огромной доске?

0 голосов
/ 13 января 2019

Я нашел этот код, который решает проблему «Рыцарского путешествия».

Если я, например, захочу решить плату размером 800x800, я получу следующую ошибку: Исключительная ситуация: 0x00007FF6345D3778 в файле test.exe: 0xC00000FD: переполнение стека (параметры: 0x0000000000000001, 0x00000082140C3000). Необработанное исключение в 0x00007FF6345D3778 в test.exe: 0xC00000FD: переполнение стека (параметры: 0x0000000000000001, 0x00000082140C3000).

Как мне избежать этой ошибки? Как мне изменить класс доски так, чтобы он мог решать такую ​​большую доску? Я хочу иметь возможность написать: доска <800> b6 например.

PS. Этот код работает для небольших досок.

Большое спасибо. 

class Board
{
public:
    array<pair<int, int>, 8> moves;
    array<array<int, N>, N> data;

    Board()
    {
        moves[0] = make_pair(2, 1);
        moves[1] = make_pair(1, 2);
        moves[2] = make_pair(-1, 2);
        moves[3] = make_pair(-2, 1);
        moves[4] = make_pair(-2, -1);
        moves[5] = make_pair(-1, -2);
        moves[6] = make_pair(1, -2);
        moves[7] = make_pair(2, -1);
    }

    array<int, 8> sortMoves(int x, int y) const
    {
        array<tuple<int, int>, 8> counts;
        for (int i = 0; i < 8; ++i)
        {
            int dx = get<0>(moves[i]);
            int dy = get<1>(moves[i]);

            int c = 0;
            for (int j = 0; j < 8; ++j)
            {
                int x2 = x + dx + get<0>(moves[j]);
                int y2 = y + dy + get<1>(moves[j]);

                if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= N)
                    continue;
                if (data[y2][x2] != 0)
                    continue;

                c++;
            }

            counts[i] = make_tuple(c, i);
        }
        sort(counts.begin(), counts.end());
        array<int, 8> out;
        for (int i = 0; i < 8; ++i)
            out[i] = get<1>(counts[i]);
        return out;
    }

    void solve(string start)
    {
        for (int v = 0; v < N; ++v)
            for (int u = 0; u < N; ++u)
                data[v][u] = 0;

        int x0 = start[0] - 'a';
        int y0 = N - (start[1] - '0');
        data[y0][x0] = 1;

        array<tuple<int, int, int, array<int, 8>>, N*N> order;
        order[0] = make_tuple(x0, y0, 0, sortMoves(x0, y0));

        int n = 0;
        while (n < N*N - 1)
        {
            int x = get<0>(order[n]);
            int y = get<1>(order[n]);

            bool ok = false;
            for (int i = get<2>(order[n]); i < 8; ++i)
            {
                int dx = moves[get<3>(order[n])[i]].first;
                int dy = moves[get<3>(order[n])[i]].second;

                if (x + dx < 0 || x + dx >= N || y + dy < 0 || y + dy >= N)
                    continue;
                if (data[y + dy][x + dx] != 0)
                    continue;

                ++n;
                get<2>(order[n]) = i + 1;
                data[y + dy][x + dx] = n + 1;
                order[n] = make_tuple(x + dx, y + dy, 0, sortMoves(x + dx, y + dy));
                ok = true;
                break;
            }

            if (!ok) // Failed. Backtrack.
            {
                data[y][x] = 0;
                --n;
            }
        }
    }

    template<int N>
    friend ostream& operator<<(ostream &out, const Board<N> &b);
};

template<int N>
ostream& operator<<(ostream &out, const Board<N> &b)
{
    for (int v = 0; v < N; ++v)
    {
        for (int u = 0; u < N; ++u)
        {
            if (u != 0) out << ",";
            out << setw(3) << b.data[v][u];
        }
        out << endl;
    }
    return out;
}

int main{
Board<800> b2;
b2.solve("b5");
cout << b2 << endl;
return 0
}

1 Ответ

0 голосов
/ 13 января 2019

array<array<int, N>, N> data с N, равным 800, требует около 2,5 МБ памяти.

Board<800> b2 выделяется в стеке.

В зависимости от платформы размер стека по умолчанию составляет около 2-8 МБ. Похоже, вы находитесь на окнах, где размер стека обычно составляет 2 МБ. Поскольку ваш массив больше размера стека, вы получаете переполнение стека.

Вам нужно выделить Board в куче. e.g.:

int main{
    auto b2 = std::make_unique<Board<800>>();
    b2->solve("b5");
    cout << *b2 << endl;
    return 0
}

В функции solve вы также выделяете order в стеке. Это должно быть изменено на что-то вроде этого, чтобы выделить его в куче: 

auto orderPointer = std::make_unique<array<tuple<int, int, int, array<int, 8>>, N*N>>();
// dereference the pointer to make array indexes easier
auto& order = *orderPointer;
...