Me cuesta entender la recursión y el retroceso, aunque he hecho algunos ejercicios simples (por ejemplo, Fibonacci). Así que permítanme presentar mi "flujo de cerebro" aquí:

Leí el libro de texto y sé que puedes usar la función de retroceso para eliminar la reina anterior si su posición actual elimina la posibilidad de colocar la próxima reina en la siguiente columna. Así que esto parece ser fácil y todo lo que tengo que hacer es eliminarlo y dejar que el programa decida el siguiente lugar posible.

Después de un tiempo, descubrí que el programa se había estancado en la sexta reina, así que me di cuenta de que si simplemente eliminaba a la quinta reina, el programa simplemente volvía a su posición actual (es decir, dadas las primeras cuatro reinas, la quinta reina siempre cae en la misma posición). lugar, que no es de extrañar). Así que pensé que necesitaba rastrear la posición de la última reina.

Esto es cuando me desconcerté. Si tuviera que rastrear la posición de la última reina (de modo que cuando retroceda, el programa NO tenga permitido colocar a la reina en el mismo lugar), existen dos posibles dificultades:

a) Diga que quito la 5ta reina y tengo que escribir el código para decidir cuál es la siguiente posición posible. Esto se puede resolver ignorando su posición actual (antes de ser eliminado) y continúa buscando posibles lugares en las siguientes filas.

b) ¿Debo seguir todas las reinas anteriores? Parece ser así. Digamos que en realidad no tengo que eliminar una reina, sino dos reinas (o incluso más), seguramente necesito rastrear todas sus posiciones actuales. Pero esto es mucho más complejo de lo que parece ser.

Así que empecé a buscar respuestas en el libro de texto. Lamentablemente no tiene el código de seguimiento, pero solo tiene el código de recursión. Entonces encontré el código aquí:

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

Me sorprendió mucho porque es muy simple y, sin embargo, ¡funciona! ¡La única parte de dar seguimiento es quitar la última reina! Entonces, la pregunta es: ¿cómo garantiza el siguiente código que, cuando se le da la posición de 4 reinas, la quinta no siempre cae en el mismo lugar una y otra vez? Creo que lo que no entiendo es cómo puede retroceder de forma recursiva (digamos que necesita eliminar más reinas). No tengo ningún problema cuando avanzo recursivamente, pero ¿cómo puedo retroceder recursivamente?

/* A recursive utility function to solve N Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
/* base case: If all queens are placed then return true */
if (col >= N)
    return true;

/* Consider this column and try placing this queen in all rows
   one by one */
for (int i = 0; i < N; i++)
{
    /* Check if queen can be placed on board[i][col] */
    if ( isSafe(board, i, col) )
    {
        /* Place this queen in board[i][col] */
        board[i][col] = 1;

        /* recur to place rest of the queens */
        if ( solveNQUtil(board, col + 1) == true )
            return true;

        /* If placing queen in board[i][col] doesn't lead to a solution
           then remove queen from board[i][col] */
        board[i][col] = 0; // BACKTRACK
    }
}

 /* If queen can not be place in any row in this colum col
    then return false */
return false;
}

DE ACUERDO. Ahora tengo un código que SÍ funciona, pero en su mayoría modifiqué mis propios códigos de acuerdo con los anteriores, así que estoy bastante inestable:

bool EightQueen(int& numQueen)  {   

if (numQueen == 8)  {
    return true;
}
if (numQueen == 0)  {
    PlaceQueen(0, 0);
    numQueen ++;
    EightQueen(numQueen);
}

int row = 0;

for (row = 0; row <= 7; row ++) {
    if (CheckThis(row, numQueen))   {   //Check if next queen can be  put
        PlaceQueen(row, numQueen);  //Place next queen
        numQueen ++;
        DisplayQueen();
        cout << endl;
        if (EightQueen(numQueen))   {   //Try next queen
            return true;
        }
        ClearQueen(numQueen - 1);
        numQueen --;
    }
}
return false;
}

Digamos que numQueen es 5, por lo que en el bucle for vamos a verificar si la 6ta reina puede colocarse. Como sabemos, esto es imposible para todas las filas, por lo que la función devuelve false. Asumo que luego se "contrae" de nuevo a donde se llamó, es decir, cuando numQueen es 4. Así que se llama a ClearQueen (4) y se elimina la última reina (la 5ta). Aparentemente, el bucle for no ha terminado, así que intentaremos la siguiente fila para ver si permite un mayor desarrollo. es decir, verificamos si la 5ta reina puede colocarse en la siguiente fila y si lo hace, verificaremos si la sexta reina puede colocarse y así sucesivamente.

Sí, parece funcionar, bueno, eh, sí.