Mam trudny czas na zrozumienie rekursji i cofania się, chociaż zrobiłem kilka prostych ćwiczeń (np. Fibonacci). Pozwólcie, że przedstawię tutaj mój „przepływ mózgu”:

Przeczytałem podręcznik i wiem, że możesz użyć cofania, aby usunąć poprzednią królową, jeśli jej obecna pozycja eliminuje możliwość umieszczenia następnej królowej w następnej kolumnie. Więc wydaje się to być łatwe i wszystko, co muszę zrobić, to je usunąć i pozwolić programowi zdecydować o następnym możliwym miejscu.

Po jakimś czasie odkryłem, że program utknął w szóstej królowej, więc doszedłem do wniosku, że jeśli po prostu usunęłem piątą królową, program po prostu odłożył ją z powrotem do aktualnej pozycji (tj. Biorąc pod uwagę pierwsze cztery królowe, piąta królowa zawsze wpada w to samo miejsce, co nie jest zaskakujące). Pomyślałem więc, że muszę śledzić pozycję ostatniej królowej.

To wtedy byłem zdziwiony. Gdybym miał śledzić pozycję ostatniej królowej (tak, że kiedy cofnę się, program NIE może umieścić królowej w tym samym miejscu), są dwie potencjalne trudności:

a) Powiedz, że usuwam piątą królową i muszę napisać kod decydujący o jej następnej możliwej pozycji. Można to rozwiązać, ignorując jego aktualną pozycję (przed usunięciem) i kontynuuje wyszukiwanie możliwych miejsc w kolejnych wierszach.

b) Czy powinienem śledzić wszystkie poprzednie królowe? Tak się wydaje. Powiedzmy, że faktycznie muszę usunąć nie jedną królową, ale dwie królowe (lub nawet więcej), z pewnością muszę śledzić wszystkie ich aktualne pozycje. Ale jest to o wiele bardziej skomplikowane niż się wydaje.

Zacząłem więc szukać odpowiedzi w podręczniku. Niestety nie ma kodu śledzenia wstecznego, ale tylko kod rekurencji. Potem znalazłem kod tutaj:

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

Bardzo mnie to zadziwiło, bo to takie proste, a jednak działa! Jedyną częścią cofania jest usunięcie ostatniej królowej! Tak więc pytanie brzmi: w jaki sposób poniższy kod zapewnia, że ​​gdy dana pozycja 4 królowych, piąta nie zawsze wpada w to samo miejsce raz za razem? Myślę, że to, czego nie rozumiem, jest to, w jaki sposób możesz cofnąć się rekursywnie (powiedz, że musisz usunąć więcej królowych). Nie mam problemu, kiedy rekurencyjnie posuwam się do przodu, ale jak mogę się cofać rekurencyjnie?

/* 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;
}

DOBRZE. Teraz mam jakiś kod, który działa, ale głównie zmodyfikowałem własne kody zgodnie z powyższymi, więc jestem dość chwiejny:

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;
}

Powiedzmy, że numQueen wynosi 5, więc w pętli for sprawdzimy, czy można umieścić szóstą królową. Jak wiemy, jest to niemożliwe dla wszystkich wierszy, więc funkcja zwraca false. Zakładam, że następnie „kurczy się” z powrotem do miejsca, w którym został wywołany, czyli gdy numQueen wynosi 4. Więc wywoływana jest ClearQueen (4) i ostatnia królowa (5.) zostaje usunięta. Najwyraźniej pętla for nie została zakończona, więc spróbujemy wykonać następny wiersz, aby sprawdzić, czy pozwala to na dalszy rozwój. tj. sprawdzamy, czy piątą królową można umieścić w następnym rzędzie, a jeśli tak się stanie, sprawdzimy, czy szósta królowa może zostać umieszczona i tak dalej.

Tak, wydaje się, że działa, cóż, tak, tak.