两个阶段

• 抽象问题，描绘问题分支
• 列出所有备选项，挨个遍历找到最优，不是最优就回溯到前一分支，删除不必要的枝条

回溯优劣

• 适用于各种问题，不会出现漏解，空间复杂度较低
• 时间复杂度高，难以优化，由于全都遍历，可能出现空间时间爆炸

回溯法案例

数独

• 问题描述：给定一个9x9的数独棋盘，其中已经填入一部分数字，要求通过回溯法填写剩余的空格，使得每行、每列和每个小九宫格内的数字都不重复
• 分析：解决本问题的思路和游戏的基本方法一样，玩数独时，不断的在脑中试错改正，就是回溯法的体现，当然在玩数独时，并不只有这一种方法。（ps：由这个问题可以做一个数独小游戏，不过仅仅是所给的代码是不够的，还有一些问题需要解决）
• 题目代码：
  • sudoku.cpp
  • sudoku.py