c# - 我如何避免 BackTrack 算法（n-queens）中的函数堆栈内存使用

Question

我开始在 C# 上进行一些编码，并尝试了 n-queen 的问题，并稍作改动（queen 也有骑士权力）。在限制之后，由于一次又一次地调用该函数，它开始显示 stackoverflow 问题。

谁能帮我理解我面临的问题。下面是 n-queens 问题的代码。

private int[] BackTrack(int queenRow, int column)
{
    for (int i = column; i < size; i++)
    {
        if (CheckValidMove(queenRow, i))
        {
            queenPosition[queenRow++] = i;
            if (queenRow < size)
                return BackTrack(queenRow, 0);
            else
            {
                done = true;
                return queenPosition;   
            }
        }
        else
            continue;
    }
    if ((queenRow - 1) >= 0 && ((queenPosition[queenRow - 1] + 1) <= size))
    {
        return BackTrack(queenRow - 1, queenPosition[queenRow - 1] + 1);
    }
    else
    {
        return queenPosition;
    }
}

1. 这里queenPosition（由函数返回）是具有放置女王的列号的数组。就像queenPosition 4-queen 将是 (2->0->3->1)。4x4 棋盘中的位置。

2. CheckValid函数验证位置是否合适。

3. 有一些我不知道的概念，内存被浪费了。

Answer 1

尝试改变

    if ((queenRow - 1) >= 0 && ((queenPosition[queenRow - 1] + 1) <= size))
    {
       return BackTrack(queenRow - 1, queenPosition[queenRow - 1] + 1);
    }
    else
    {
        return queenPosition;
    }

至

    if (!((queenRow - 1) >= 0 && ((queenPosition[queenRow - 1] + 1) <= size)))
    {
       return queenPosition;
    }

    return BackTrack(queenRow - 1, queenPosition[queenRow - 1] + 1);

您需要帮助编译器并将其优化为尾 递归。

它可能根本没有得到优化，这取决于参数和返回值，但值得一试。

Lauschke Consulting 的关于这个问题的好读物N-Queens Problem Solutions

祝你好运！