算法分析与设计实验报告第 六 次实验姓名学号班级时间12.12上午地点工训楼309 实验名称回溯法实验(n皇后问题)实验目的1. 掌握回溯法求解问题的思想2. 学会利用其原理求解相关问题实验原理用n元组x1:n表示n后问题的解。其中，xi表示皇后i放在棋盘的第i行的第xi列。由于不允许将2个皇后放在同一列上，所以解向量中的xi互不相同。2个皇后不能放在同一斜线上是问题的隐形约束。用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束Place剪出不满足行、列和斜线约束的子树。递归函数Backtrack(1)实现对整个解空间的回溯搜索。 Backtrack(i)搜索解空间中第i层子树。类Queen的数据成员记录解空间中结点信息，以减少传给Backtrack的参数。Sum记录当前已找到的可行方案数。实验步骤数组法：（1）根据n皇后问题，可以把其设想为一个数组；（2）根据n皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都不能相同，由此可以得到判断条件；
