我看到了下面的代码并试图理解它是如何工作的。我陷入了回溯。有人能解释一下 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() 将被压入堆栈。
考虑到将女王放在第 3 行的 N 个位置中的任何一个都是不安全的,并且
-
if (isSafe(mat, r, i))
将为所有列 0 到 N 返回 false。 - 最终循环
for (int i = 0; i < N; i++)
将结束r == 2
堆栈将展开。 - 堆栈将删除最顶层的调用,我们将在堆栈中留下函数调用(返回步骤 1)。
- 然后循环
for (int i = 0; i < N; i++)
将尝试重新定位第二个女王。
关于c++ - 回溯N皇后算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59122621/