c++ - 回溯N Queen算法

我正在看下面的代码，试图理解它的工作原理。我陷入了回溯的困境。有人可以解释一下，当r找不到适合的女王位置时，r值如何从2变为1。
`
以下是调试部分:

nQueen (mat=0x7fffffffddb0, r=2) at N_Queens_problem.cpp:47
47      for (int i = 0; i < N; i++)
(gdb) print i
$1 = 3
(gdb) n
62  }
(gdb) print i
No symbol "i" in current context.
(gdb) print i
No symbol "i" in current context.
**(gdb) print r
$2 = 2**
(gdb) n
nQueen (mat=0x7fffffffddb0, r=1) at N_Queens_problem.cpp:47
47      for (int i = 0; i < N; i++)
**(gdb) print r
$3 = 1**
(gdb)

下面是nqueen函数:

void nQueen(char mat[][N], int r)
{
    // if N queens are placed successfully, print the solution
    if (r == N)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
                cout << mat[i][j] << " ";
            cout << endl;
        }
        cout << endl;

        return;
    }

    // place Queen at every square in current row r
    // and recur for each valid movement
    for (int i = 0; i < N; i++)
    {
        // if no two queens threaten each other
        if (isSafe(mat, r, i))
        {
            // place queen on current square
            mat[r][i] = 'Q';

            // recur for next row
            nQueen(mat, r + 1);

            // backtrack and remove queen from current square
            mat[r][i] = '-';
        }
    }
}

以下是检查女王是否安全放置的功能:

bool isSafe(char mat[][N], int r, int c)
{
    // return false if two queens share the same column
    for (int i = 0; i < r; i++)
        if (mat[i][c] == 'Q')
            return false;

    // return false if two queens share the same \ diagonal
    for (int i = r, j = c; i >= 0 && j >= 0; i--, j--)
        if (mat[i][j] == 'Q')
            return false;

    // return false if two queens share the same / diagonal
    for (int i = r, j = c; i >= 0 && j < N; i--, j++)
        if (mat[i][j] == 'Q')
            return false;

    return true;
}

最佳答案

假设您放置了两个皇后，然后放置了第三个皇后。

到目前为止，堆栈中将有两个递归调用nQueens()。一个用于女王0，一个用于女王3。

nQueen(mat, r + 1);将使用nQueen(mat, 2)调用，第三个nQueens()将被压入堆栈。

考虑到将女王放置在第三排的N个位置中的任何一个和

if (isSafe(mat, r, i))将对所有0到N的列返回false。

最终，循环for (int i = 0; i < N; i++)将以r == 2结尾，并且堆栈将展开。

Stack将删除最上面的调用，并且我们将在堆栈中保留函数调用(不执行步骤1)。

然后循环for (int i = 0; i < N; i++)将尝试重新定位第二个皇后。