递归回溯解释

Question

我找到了 N 皇后谜题的源代码，但我无法理解它。我是递归函数的新手。如果有人可以为我简化这部分代码并解释这如何属于回溯。我找了一圈也没弄明白

void solve(int k)
{
    if (k == N) /// We placed N-1 queens (0 included), problem solved!
    {
        ///Solution found!
        cout << "Solution: ";
        for (int i = 0; i < N; i++)
            cout << position[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i = 0; i < N; i++) /// Generate ALL combinations
        {
            /// Before putting a queen (the k-th queen) into a row, test it for safeness
            if (isSafe(k, i))
            {
                position[k] = i;
                /// Place another queen
                solve(k + 1);
            }
        }
    }
}

Answer 1

算法的工作原理如下：

为棋盘上的皇后找到下一个可用位置。放在那里。
重复步骤 1，直到 A) 您已成功放置 k 个皇后或 B) 没有有效的皇后放置。
如果没有有效的放置，返回到您放置的前一个棋子并重复步骤 1（即为前一个女王找到不同的位置，然后重试）。

你可以清楚地看到回溯发生在第3步。如果你走到了死胡同，那么继续修改你之前的作品的位置，直到你找到一个有效的解决方案。

递归回溯解释

Recursive Backtracking explaination

c++

backtracking