《N皇后问题实验报告.docx》由会员分享，可在线阅读，更多相关《N皇后问题实验报告.docx（5页珍藏版）》请在金锄头文库上搜索。
1、N皇后问题实验报告一、实验内容在nn格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，求解可以放置的方法种数。二、问题分析n后问题等于于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后，不会造成列上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。三、算法设计1.解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i
2、为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2.算法设计因为n皇后问题，从n大于11开始求解过程耗时就很长，所以定义x 数组的最大值MAXNUM=30；即最大可解决30皇后问题。1)判断当前位置是否可放置皇后皇后k在第k行第xk列时，xi=xk 时，两皇后在同一列上;abs(xi-xk)=abs(i-k)时，两皇后在同一斜线上;两种情况两皇后都可相互攻击，返
3、回false表示不符合条件。bool Place(int k)int i;i=1;while(iif(xi=xk|abs(xi-xk)=abs(i-k)return false;i=i+1;return true;2)输出当前解void Print(int x,int n)num+;printf(第%dt种解法:(,num);for(int i=1;iprintf(%d,xi);if(i%n=0)printf();n);3)回溯法搜索解空间void NQueens(int n)int k=1;x1=0;while(k0)xk+=1;while(xkxk+=1;if(xkif(k=n)Print
4、(x,n);elsek=k+1;xk=0;/回溯至上一行；elsek-;3.实验结果及分析n皇后问题解的情况4.实验程序实验#include #include#define N 4 /* 定义棋盘大小*/static int sum; /* 当前已找到解的个数*/static int xN;int place(int k)int j;for (j = 0; j if (xj = xk | abs(j - k) = abs(xj - xk)return 0;return 1;/* 打印棋局*/void chessboard()int i,j;int siteN;printf(第%d种解法:n, + sum);for (i = 0; i = 0) xk += 1; /* 向右移一列*/* 向右移至出最右列或可以放置皇后的列*/while (xk
