N皇后问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
及深度优先算法
常规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)的点的排列总数。
二(伪代码: X[k]=X[k]+1 判断点是否符合要求: If X[k]<=n then
place(k, X) Sum=Sum+1
I=1 Else
While i
求问题的所有解: using namespace std; Nqueens(n, X) #include Sum=0 , X[1]=0 , k=1
While k>0 do /*检查可不可以放置一个新的皇后*/
X[k]=X[k]+1 bool place(int k, int *X)
While X[k]<=n and !(place(k,x)) {
1
int i; for(int i=1;i<=n;i++)
i=1; cout<0) int main()
{ {
X[k]=X[k]+1; int n;
int *X;
cout<<"请输入皇后的个数:"; while((X[k]<=n)&&(!place(k, X))) cin>>n;
X[k]=X[k]+1; X=new int[n];
if(X[k]<=n) cout<<"问题的解如下:"< upperlimit&~(row|ld|rd); using namespace std; while(pos!=0) #include { int sum = 0; int p=pos&-pos; int upperlimit = 1; pos-=p; void compare(int row,int ld,int rd) compare(row+p,(ld+p)<<1,{ (rd+p)>>1);
if(row!=upperlimit) }
4
} cin>>n;
else{
sum++; upperlimit = (upperlimit<adjvex=j;
return 1; p->adj=w;
} p->nextarc=ga.vexs[i].firstarc; void DestroyQueue(Queue &Q){ ga.vexs[i].firstarc=p;
delete []Q.elem; }
Q.front = Q.rear = 0; }
} void DFS(Net ga,char *name,int *visited)
{
void EnterQueue(Queue &Q, int e) int v,w;
{ ArcNode *p;
if((Q.rear + 1)%MAX_QUEUE_NUMBER != v=LocateVex(ga,name); Q.front) visited[v]=1;
Q.elem[Q.rear ] = e; printf("%s ",ga.vexs[v].szName);
else p=ga.vexs[v].firstarc;
printf("队列满!\n"); while(p!=NULL)
Q.rear = (Q.rear + {
1)%MAX_QUEUE_NUMBER; w=p->adjvex;
} if(visited[w]==0)
void LeaveQueue(Queue &Q, int &e) DFS(ga,ga.vexs[w].szName,visited); { p=p->nextarc;
if(Q.rear != Q.front) }
e = Q.elem[Q.front]; }
else void DFSTravel(Net ga,char *name)
printf("队列空!\n"); {
Q.front = int v,k=0;
(Q.front+1)%MAX_QUEUE_NUMBER; int visited[20];
} for(v=0;v
本文档为【N皇后问题及深度优先算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483