什么是搜索

很多问题没有现成公式，比如"迷宫能不能从起点走到终点""8 个皇后怎么摆才不互相攻击"。这时只能一种一种地试——把所有可能的走法系统地枚举一遍，这就是搜索。

关键在"系统"两个字：不重、不漏。最朴素的搜索就是嵌套枚举，比如试遍所有三位密码：

for (int a = 0; a < 10; a++)
    for (int b = 0; b < 10; b++)
        for (int c = 0; c < 10; c++)
            check(a, b, c);   // 逐一检验

但可能的方案数往往随规模指数级增长，$n$ 位密码就有 $10^n$ 种。所以搜索通常配合递归和剪枝来写，后面几节讲的就是这些。