巡逻的骑士

在实现深度优先搜索（DFS）时，为了确保骑士不会走出棋盘外，我在代码中添加了对新位置坐标的合法性检查。具体来说，对于每个可能的移动方向，我计算出新的位置坐标 (nr, nc)，然后检查这些坐标是否满足 nr >= 0、nr < m、nc >= 0 和 nc < n 来保证新的位置仍在棋盘范围内。此外，还需要检查目标位置是否已经被访问过，即 board[nr][nc] 是否大于等于0。只有当新的位置合法且未被访问时，才会继续执行DFS。这样，通过边界检查，可以确保骑士的每次移动都不会超出棋盘的边界。

回溯是一种通过试错来寻找所有（或部分）解的问题解决方法。在深度优先搜索中，如果从当前位置出发的所有可能的移动都不能完成对棋盘的完整遍历，即所有的递归DFS调用都返回了False，则当前路径不能构成解决方案。在这种情况下，我们需要撤销最近的移动，并尝试其他可能的移动。具体到本题，当DFS无法通过当前路径完成棋盘遍历时，我会将当前位置的访问标记（即 board[r][c]）重置为-1（表示未访问），然后返回False给上一层递归，表示当前路径不可行。这样，算法会回到上一个位置，尝试其他的移动方向。回溯的过程是解决这类搜索问题的核心，它使得算法能够探索棋盘上的所有可能路径，直到找到一个成功遍历整个棋盘的路径或确认没有解决方案。

在选择深度优先搜索（DFS）而非广度优先搜索（BFS）来解决骑士巡逻问题的主要考虑是问题的性质和目标。DFS通过探索尽可能深的路径，有助于快速找到一个可能的解决方案，即一条能覆盖所有棋盘格子的路径。相比之下，BFS以层级方式广泛搜索，更适合于找到最短路径问题，而在本问题中，我们不仅需要找到覆盖所有格子的路径，而且路径的长度固定为棋盘格子的数量。此外，DFS在空间复杂度上通常比BFS更优，因为BFS需要存储在搜索过程中的所有状态，而DFS仅需存储一条路径上的状态。因此，考虑到问题的需求和资源效率，DFS是更合适的选择。