N皇后问题c语言解法

我就是我 2022-08-27 14:44 136阅读 0赞

#include <stdio.h>
    #include <stdlib.h>  //stdlib.h里面定义了五种类型、一些宏和通用工具函数,在这里我用它是因为我在后面要用到abs（）这个函数，
                        //具体这个函数的作用后面解释
    int q[100];        //在这里单独定义一个数组，用来存放皇后所在的列数
    int cont = 0;  //cont当然是用来统计解得个数 
    int x=1;
    void lay(int k,int n) ;
    FILE *fp;//定义文件类型的指针
    
    
    void main()  
    {  
        int n;  
        printf("请输入皇后的个数,n=");  
        scanf("%d",&n);  
        printf("%d皇后问题求解如下\n",n);  
    fp=fopen("queen.txt","w");//使用该函数打开或者新建一个文件
    if(fp==NULL)
    {
        printf("\n打开文件失败！\n");
        exit(0);
    }
    lay(1,n);        //调用放置函数
    fclose(fp);
    printf("\n");  
    
        
         
    } 
    void printout(int n,FILE *fp)
    //该函数的目的是输出其中的一种情况
    {   
        int i;  
        cont++;  //每一次调用该函数，cont都要加一
    
        printf("第%d个解：\n",cont);
        fputs("第",fp);
    
    
        fputc((char)(cont+48),fp);
        fputs("个解：",fp);
        for(i=1;i<=n;i++)  
         {   printf("(%d,%d) ",i,q[i]);  //在这里i代表行数，q数组代表列数\
             
            fputc('(',fp);
            fputc((char)(i+48),fp);
            fputc(',',fp);
            fputc((char)(q[i]+48),fp);
            fputc(')',fp);  
        }
           printf("\n");  
    
    }  
    
    
    int checkout(int i,int m)   
    //检验i行m列上是否可以放置皇后，可以放置返回true，否则返回false
    {  
        int j=1;  
        while(j<i)  //j=1~i-1是已经放置了皇后的行  
        {  
                  
            if(q[j]==m || abs(j-i)==abs(q[j]-m))    //这行代码的作用是阻止皇后在同一列并且阻止皇后在同一斜线上  ,
                //abs函数的作用是求整数的绝对值\
                return false;  
                j++;  
        }  
        return true;  
    }  
      
    void lay(int k,int n)    
    // 放置皇后到棋盘上,使用的递归方法,这个函数的核心作用是在每一行中找出可以放置皇后的列数
    {  
         
       
        if(k>n)  // 一开始传给k的数值是一，直到k>n时，试探完成
            printout(n,fp);  
        else  
        {  
            for(int j=1;j<=n;j++)   //试探第k行的每一个列 ，在这里J代表的是列数 
            {  
                if(checkout(k,j)) //这句话的作用是为了，将可以放置皇后的列数，赋值给q数组 
                {  
                    q[k] = j;  
                    lay(k+1,n);  //递归总是在成功完成了上次的任务的时候才做下一个任务  
                }  
    
            }  
        } 
    }