> For the complete documentation index, see [llms.txt](https://zhenghe.gitbook.io/open-courses/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenghe.gitbook.io/open-courses/mit-6.006/backtracking.md).

# Backtracking

backtracking 其实是一种暴力算法，通常应用在答案由一系列动作构成的问题中，如走迷宫、数独、N Queens 等，假设每次动作都有多种选项，那么就分别尝试，直到找到答案为止。

## N Queens

假设有一个 8 x 8 的棋盘，要在该棋盘上放入 8 个 Queens，使得 Queens 之间不同行，不同列，不在互相的对角线上，找到所有符合条件的放法。

![](/files/-LZUlfsPpf7OQ0emnGRY)

解法很简单，必然每行都有且仅有一个 Queen，因此就从第一行开始遍历每种可能即可，如下图所示：

![4 Queens Problem](/files/-LZUllPFMSKDsDefXs87)

具体可参考 [LeetCode Problem#51](https://leetcode.com/problems/n-queens/)。