# Backtracking

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

## N Queens

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

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUisBAVoggyZVzIbo4%2F-LZUlfsPpf7OQ0emnGRY%2FScreen%20Shot%202019-02-24%20at%209.51.33%20PM.jpg?alt=media\&token=9fec9b41-aaef-41ff-9702-14961c875759)

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

![4 Queens Problem](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUisBAVoggyZVzIbo4%2F-LZUllPFMSKDsDefXs87%2FScreen%20Shot%202019-02-24%20at%209.52.07%20PM.jpg?alt=media\&token=5115fe05-5e93-433d-800b-190030442063)

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