Backtracking

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

N Queens

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

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

4 Queens Problem

具体可参考 LeetCode Problem#51