基于四皇后问题的回溯法求解及算法实现

聂 华

（陕西职业技术学院,陕西 西安,710100）

0 引言

回溯法是一种非常有效，适用范围相当广泛的算法设计思想。许多复杂的问题，规模较大的问题都可以使用回溯法求解，因此回溯法又有“通用解题方法”的美称。本文将利用四皇后问题作为实例，讨论回溯法的求解过程。

1 基本思想

回溯法解决皇后问题的基本思想是：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度探索解空间树。当探索到某一节点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。

如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树被探索到才结束。如果只要求解问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。

2 四皇后问题的求解过程

许多复杂的问题都可以用回溯法的思想来求解，例如经典的N皇后问题。

N皇后问题的描述为：求解如何在一个N×N的棋盘上无冲突的摆放N个皇后棋子。在国际象棋里，皇后的移动方式为横竖交叉的，因此在任意一个皇后所在位置的水平、竖直，以及45°斜线上都不能出现皇后棋子

N皇后问题的解法很多，可以用回溯法解决N皇后问题。……