[数据结构与算法]回溯：就是一个不断决策的过程!

从八皇后问题说起

八皇后问题是一个古老的非常有意思的问题。时间退回到1848年，国际西洋棋棋手马克斯·贝瑟尔提出了这样的一个问题

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

此时我们就可以枚举所有的可能性，如下图为一个4皇后枚举的过程。
当然枚举的过程我们并不是想到啥就写啥，而是按照一定的规则，枚举所有的可能性。按照行和列依次递增来枚举所有的可能性。

第0行依次在第0，1，2，3列放第一个，接着放第二行。在枚举的过程中，如果我们发现目前的状态已经不符合要求时就没必要按照这种情况接着枚举了，这个技巧叫做剪枝

整个枚举的过程就如下图所示，这个树就叫决策树，演示了你枚举的整个流程。当然这个树是经过剪枝的，不然整个决策树会非常大，降低效率。

好了，我们开始枚举。记住我们需要一边枚举，一遍减枝。而不是等放完8个皇后，再看这8个皇后的放置合理不。

了解本专栏 订阅专栏 解锁全文 学习会员免费看