バックトラッキングがそのように機能するのはなぜですか？

Question

私は最近、単純な再帰関数、組み合わせアプリケーション、およびバックトラッキングや分割ET Imeraなどの技術について、（プログラミングのコンテキストとは対照的に）CSコンテキストで（プログラミングコンテキストとは対照的に）学習を始めました。

私の質問に私が選んだ問題の例は、n女王の問題です（n女王と*nチェスボードを考えると、クイーンがお互いを攻撃できないようにどのようにクイーンを配置しますか？）。基本的なアイデアは、可能なすべての配置を生成すること（デカルト製品を生成することによって）であり、それらが無効である場合（検証関数を介して）それらを捨てるだけで単純に破棄することであることを理解しました。

これが私のサンプルの実装です：

    int valid (int k)
    {
    for (int i = 1; i < k; i++)
    {
        if (sol[i] == sol[k]) return 0;
        if (abs(sol[i] - sol[k]) == abs(i - k)) return 0;
    }
    return 1;
}

void print ()
{
    for (int i = 1; i <= n; i++)
    {
        cout << sol[i];
    }
    cout << endl;
    how++;
}

void backtrack (int k)
{
    if (k == n+1) print();
    else
    {
        sol[k] = 0;
        while (sol[k] < n)
        {
            sol[k]++;
            if (valid(k)) backtrack(k+1);
        }
    }
}

1. 検証関数では、1をK、2でKなどでチェックすることにより、ソリューションのチェックが徐々に行われるのはなぜですか。ソリューションは（i、k）のペアで正しいが、全体的に間違っていると思います（たとえば、3に対する1と2は正しく配置されますが、2と比較して1は間違って配置されます）？

Answer 1

たとえば、3に対する1と2は正しく配置されますが、2に対する1は間違って配置されますか？

あなたはすでに1と2が正しく配置されていることをテストしています、そうでなければあなたは電話しません backtrack(3).

それを思い出します sol[i] = j 列$ i $の女王が行$ j $に置かれることを意味します。電話することによって backtrack(k+1) $ 1 dots k $のすべての女王が正しく配置されていることをすでに確認しています（非collinging）。