¿Por qué funciona el retroceso como lo hace?

Question

Recientemente comencé a aprender en un contexto de CS (a diferencia de un contexto de programación) sobre funciones recursivas simples, junto con las aplicaciones combinatorias y técnicas como el retroceso y la división ET impera.

El problema de ejemplo que elegí para mis preguntas es el problema de N Queens (dado N Queens y An*n Chessboard, ¿cómo colocas a las reinas de tal manera que no pueden atacarse entre sí?). Entendí que la idea básica es generar todas las ubicaciones posibles (generando un producto cartesiano) y luego simplemente descartarlas a medida que aparecen si no son válidas (a través de la función de validación).

Aquí está mi implementación de muestra:

    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. ¿Por qué en la función de validación, la verificación de la solución se realiza progresivamente verificando 1 con K, 2 con K y así sucesivamente? Creo que la solución puede ser correcta en pares de (i, k) pero incorrecto en general (por ejemplo 1 y 2 en relación con 3 se colocan correctamente, pero 1 en relación con 2 se coloca incorrectamente)?

Answer 1

Por ejemplo, 1 y 2 en relación con 3 se colocan correctamente, pero 1 en relación con 2 se coloca incorrectamente?

Ya ha probado que 1 y 2 se colocan correctamente, de lo contrario no llamaría backtrack(3).

Recordar que sol[i] = j significa que la reina en la columna $ i $ se pone en la fila $ j $. Llamando backtrack(k+1) Ya ha verificado que cada reina en $ 1 dots k $ se coloca correctamente (no colidía).