解空间树及其相关算法

在处理诸多现实问题时，往往需要找出符合特定要求的所有解或最优解，例如广为人知的N皇后问题以及旅行商问题。
这类问题通常缺乏明确的计算法则来直接求解，因此我们常常借助试探性的策略，在涵盖所有潜在解的解空间树中进行全面搜索，以获取期望的某一个或多个解，通常是符合特定条件的最优解或者全部可能的解。那么，此处所提到的解空间树具体指什么呢？

解空间树与回溯法应用

解空间树：
根据待解决的问题特征，将问题的解结构以树状形式进行表达，其中所有可能的解均以叶子节点的形式呈现的一棵树。
回溯法：
回溯法是一种通过深度优先策略对解空间树进行搜索的方法，在搜索过程中会持续判断当前节点是否符合解题条件，若满足则继续向下探索；若不满足，则返回至上一层节点，继续搜索其他子树，这种处理问题的方式即称为回溯法。
解空间树的建立：
其本质是将问题求解过程中涉及的一系列判断与决策步骤以及各类可能的结果，以树形结构加以展示。
实际上，在我们解决问题的过程中，始终伴随着不断进行的判断与决策。每一个判断与决策步骤在解空间树中对应一个分支节点，而不同可能性的结果则对应于该节点下的各个子节点及相应的子树。整个判断与决策过程在解空间树中体现为逐步扩展的过程；而最终所有可能的解决方案，则会全部体现在这棵解空间树的叶子节点之中。

求解N皇后问题的回溯算法