相信"迷宫"是许多人儿时的回忆，大家小时候一定都玩过迷宫游戏。我们从不用别人教导，都知道走迷宫的策略是：

  其实，这就是回溯法——一个基于深度优先搜索和约束函数的问题求解方法。

  众所周知，回溯法的时间复杂度主要取决于如下几点：

  当问题和算法一旦确定下来，就只剩下第5点的实际产生的节点数目是根据问题的具体实例而动态生成，不可预知的。   对于一个具体的问题实例，很难预测出回溯法的行为（先选哪一条岔路，这条岔路是否能很快得到最优解），这时应该怎么办呢？

  此时，可以使用蒙特卡罗方法估计回溯法产生的节点数目。   所谓蒙特卡罗方法，其实就是一种以概率统计理论为指导的，使用随机数（或伪随机数）来解决计算问题的方法，通过对大量随机试验求平均，以求得相近的值。   蒙特卡罗方法的基本思想是：当求解的问题是某种随机事件出现的概率或数学期望时，通过大量“实验”的方法，以频率估计概率或者得到某些数字特征，将其近似看作问题的解。   1777年，法国数学家布丰(Buffon)提出使用投针试验的方法求解圆周率π，这被认为是蒙特卡罗方法的起源（扯远了）。

  我们需要估计的是回溯法实际产生的节点数目，以此计算回溯法的时间复杂度。   其主要思想是，在解空间树（状态空间树）上动态、随机的产生一条路径，然后沿此路径来估算解空间树中所有满足约束条件的节点总数（这里计算的是最差时间复杂度，假设要走遍所有满足约束条件的节点）。   多次进行上述实验，对结果求平均值，即可得到回溯法中实际生成的节点数目的估计值。

  问题背景：8皇后问题是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。N皇后问题由此推广而来。   问题描述：在N×N格的国际象棋上摆放N个皇后，使其不能互相攻击，即不能处于同一列或同一行，也不能处在同一斜线上，请问有多少种摆法？

  N皇后问题也是回溯算法的典型案例，这里，我们可以使用递归和循环迭代两种不同的回溯方式编写代码：