n后问题

﹏ヽ暗。殇╰゛Y 2022-12-20 05:40 71阅读 0赞

## n后问题 ##

**一、 问题描述**

*  在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子，请输出皇后的位置以及对应皇后的解法个数。

**分析：**

1.  理解皇后不被攻击的条件：n后问题等价于在n\*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。
2.  算法模块简要分析。  
    用数组存储皇后的位置，将i设置为0。  
    Int  place(\*x,n) :数组x\[\] 用来表示列数，n为皇后个数，用来判断皇后 否被攻击，判断的条件是（x\[i\]-x\[n\]==i-n||x\[i\]-x\[n\]==n-i||x\[i\]==x\[n\]）即用来判断“同一行或同一列或同一斜线上”。  
    用数组存储皇后的位置，将i设置为0。  
    Int  iniprint(\*x,n):初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为“1”，不放皇后的位置记为“0”  
    Int  Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。Int i=0,如果x\[i\]>=n的时候即进行下一行，i++；当i=n时，sum++；输出该组可行解的个数和位置的矩阵。并且i–，回溯到上一层继续搜索可行解。

**二、 程序实现**

#include<stdio.h>
    static int n,sum=0;//可行解个数
    static int locate[20];
    int place(int k) 
    {
        //判断是否在一条线上并返回0,1
           for(int i=1;i<k;i++){
        
    	       if(locate[i] == locate[k] || (i+locate[i])==(locate[k]+k)||(locate[i]-i)==(locate[k]-k))
    		              return 0;
    				}
    				return 1;
    			}
    			void Back(int m){
        
    				if(m>n){
        
    					sum++;
    					for(int i=1;i<=n;i++){
        
    						for(int a=1;a<=n;a++){
        
    							if(a<locate[i]||a>locate[i])
    							printf(" * ");
    							else
    							printf(" # ");
    //如果已经安排完毕则输出棋盘和记录 
    						}
    						printf("\n"); 
    					}
    					printf("第%d种解决办法如上图所示：",sum);
    					for(int i=1;i<=n;i++)
    					printf("%d ",locate[i]);
    					printf("\n\n\n");
    				}
    				else
    				{
        
    				//如果没有安排完则地柜继续下一个安排，无解则返回上一个 
    					for(int i=1;i<=n;i++)
    					{
        
    						locate[m]=i;
    						if(place(m))
    						Back(m+1); 
    					}
    				}
    	 
    			}
    			int main()
    			{
        
    				printf("请输入皇后的数量：");
    				scanf("%d",&n);
    				printf("\n(#表示皇后，*表示棋盘)\n\n\n");
    				Back(1);
    				printf("%d个皇后共有以上%d种解法\n\n\n",n,sum);
    			}

**三、 实验结果与分析**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70_pic_center 1]

**结果分析：**

*  通过本次实验，我对回溯法有了深刻的理解,并且对递归得到了巩固。在编写N皇后算法的过程中,遇到了一些问题,当以普通的方式回溯时,当n>=11时,程序运行时间变得很长,说明该算法的时间复杂度比较大。
 *  回溯法有“通用解题法”之称,用它可以搜索问题的所有解。它是一个既带  
    有系统性又带有跳跃性的搜索算法,是按照深度优先策略,从根节点出发搜索解空间树。
 *  算法搜索至某一节点时,利用判断函数先判断该节点内是否包含问题的解,如果不包含则直接跳过,节省时间,相关的判断函数裉据实际问题来编写。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7b1b2f6cebe14a05982a95b239548a7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/3d5dd4df2d2d412ca7464b6e2cc50d0d.png