N皇后问题及深度优先算法.doc
版权申诉
24 浏览量
2022-05-07
13:17:33
上传
评论
收藏 133KB DOC 举报
常规 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)的点的
排列总数。
二．伪代码：
判断点是否符合要求：
place(k, X)
I=1
While i<k do
If x[i]==x[k] or abs(x[i]-
x[k])==abs(i-k) then
Return false
I=i+1
Return true
求问题的所有解：
Nqueens(n, X)
Sum=0 , X[1]=0 , k=1
While k>0 do
X[k]=X[k]+1
While X[k]<=n and !(place(k,x))
X[k]=X[k]+1
If X[k]<=n then
Sum=Sum+1
Else
K=K+1 ,X[k]=0
Else
K=K-1
Print sum
三．代码实现
#include <iostream>
using namespace std;
#include <math.h>
/*检查可不可以放置一个新的皇后*/
bool place(int k, int *X)
{
int i;
i=1;
while(i<k)
{
if((X[i]==X[k])||(abs(X[i]-
X[k])==abs(i-k)))
return false;
i++;
}
return true;
}
/*求解问题的所有解的总数，X 存放列数*/
void Nqueens(int n,int *X)
{
int k,sum=0;
X[1]=0;
k=1;
while(k>0)
1
资源评论
