例2八皇后问题 ◆在八皇后问题中,处理过程不是根 据某种确定的计算法则,而是利用试 探和回溯的探索技术求解。为了求得 合理布局,在计算机中要存储布局的 当前状态。从最初的布局状态开始, 步步地进行试探,每试探一步形成 个新的状态,整个试探过程形成了 棵隐含的状态树。如图1.2所示(为 了描述方便,将八皇后问题简化为四 皇后问题) 回溯法求解过程实质上就是一个遍 历状态树的过程。在这个问题中所出 现的树也是一种数据结构,它可以应 用在许多非数值计算的问题中。 图1.2四皇后问题中隐含的状态树 2021年1月21日 数据结构讲义2021年1月21日 数据结构讲义 7 在八皇后问题中，处理过程不是根 据某种确定的计算法则，而是利用试 探和回溯的探索技术求解。为了求得 合理布局，在计算机中要存储布局的 当前状态。从最初的布局状态开始， 一步步地进行试探，每试探一步形成 一个新的状态，整个试探过程形成了 一棵隐含的状态树。如图1.2所示（为 了描述方便，将八皇后问题简化为四 皇后问题）。 回溯法求解过程实质上就是一个遍 历状态树的过程。在这个问题中所出 现的树也是一种数据结构，它可以应 用在许多非数值计算的问题中。 例2 八皇后问题