8queens.cpp

8皇后问题最好的算法,请登陆本站才能下载哦!这是最优的解法哦!

  #include<stdio.h> 
  #include<conio.h>    //conio.h 是 Console (键盘和屏幕) 输出输入函数的头文件,con -- Console, 
                       //io -- input,output, 
  #include<stdlib.h>   //stdlib.h里面定义了五种类型、一些宏和通用工具函数。
                       // 类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；
                       // 宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX和MB_CUR_MAX等等；
                       //常用的函数如malloc()、calloc()、realloc()、free()、system()、
                       //atoi()、atol()、rand()、srand()、exit()等等。
  #define QUEENS 8 
  int iCount = 0; 
  int Site[QUEENS]; 
  void Queen(int n); 
  void Output(); 
  int IsValid(int n); 
                       //Main:主函数
  void main() 
  { 
    Queen(0); 
    getch();           //getch()是一个函数，是从键盘获取一个字符; 
  }                    //一般C语言里用getch()来是程序运行停下来，等待从键盘输入字符，然后继续。
  	                   //练习的小程序getch()放在程序最后的话一般都是用来看程序运行结果的，
	                   //没有getch()的话程序运行就一闪而过
	                   //getchar()读入一个字符会在屏幕上加显该字符，getch()则不会回显示．
	                   //可以用getch()来做密码的输入 

                       //Queen:递归放置皇后
  void Queen(int n)    //从第一列开始，一列一列的放置，每一种情况输出结果从第一列开始，输出为所在行数
  {                    //行数是从1到8 ，开始时候，有一情况是：顺利放置了5个皇后，1，3，5，2，4。
	  	  		       //但第6个皇后不能放入
    int i; 
    if(n == QUEENS) 
	{ 
       Output(); 
       return;         //该句不能少！ 表示返回 null 
	} 

    for(i = 1 ; i <= QUEENS ; i++)                                                                                          
	{ 
       Site[n] = i;    
       if(IsValid(n)) 
         Queen(n+1); 
	} 
  } 

                        //IsValid:判断皇后放上去之后，是否无冲突 
  int IsValid(int n) 
  { 
    int j; 
    for(j = 0 ; j < n ; j++) //后来放的与前面放的每一个皇后逐一比较
	{ 
       if(Site[j] == Site[n]) //判断后来的皇后位置是否与前面皇后位置重复
         return 0; 
       if(abs(Site[j] - Site[n]) == (n - j)) //判断后来的皇后位置是否与前面的在同一对角线上
         return 0; 
	} 
    return 1; 
  } 

                         //-Output:输出一个解，即一种没有冲突的放置方案
  void Output() 
  { 
    int k; 
    printf( "No.%-5d " , ++iCount); 
    for(k = 0 ; k < QUEENS ; k++ ) 
      printf( "%d " , Site[k]); 
    printf( "\n "); 
  }