0

私はC＃でいくつかのコーディングを開始し、わずかな変更でn-queenの問題を試しました（queenにはknightの力もあります）。制限の後、関数を何度も呼び出すため、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（関数によって返される）は、クイーンが配置されている列番号を持つ配列です。4-queen のようqueenPosition に (2->0->3->1) になります。4x4 チェス盤の位置。

  2. CheckValid関数は、位置が適切かどうかを検証します。

  3. 私が気付いていない概念がいくつかあり、メモリが無駄になっています。

4

1 に答える 1

-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

幸運を！

于 2012-07-30T19:09:57.293 に答える