文件名称：回溯算法n皇后问题
文件大小：63KB
文件格式：DOCX
更新时间：2015-01-23 06:22:07
算法实验设计 回溯算法 n皇后问题
运用回溯法解题通常包含以下三个步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 通过上述的基本思路，我们可以将问题描述为：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。 也就是对于N×N的棋盘，选择出N个符合i!=r∧j!=s∧|i-r|!=|j-s|∨(i+r)!=(j+s)的点的排列总数。