Почему возврат назад работает именно так?

Question

Совсем недавно я начал изучать в контексте CS (в отличие от контекста программирования) простые рекурсивные функции, а также комбинаторные приложения и такие методы, как Backtracking и Divide et Impera.

Пример задачи, которую я выбрал для своих вопросов, — это задача о n ферзях (при 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), но неправильным в целом (например, 1 и 2 относительно 3 расположены правильно, а 1 относительно 2 расположены неправильно)?

Answer 1

например 1 и 2 относительно 3 размещены правильно, а 1 относительно 2 размещены неправильно?

Вы уже проверили, что 1 и 2 расположены правильно, иначе вы бы не звонили backtrack(3).

Напомним, что sol[i] = j означает, что ферзь в столбце $i$ стоит в строке $j$.Позвонив backtrack(k+1) вы уже убедились, что все ферзи в $1 \dots k$ расположены правильно (без коллизий).