【Acm】八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。

其解决办法和我以前发过的【算法之美—Fire Net：www.cnblogs.com/lcw/p/3159414.html】类似

题目：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

 #include <stdio.h>

 int count = ;    //全局变量，统计所有解法

 int notDanger( int row, int j, int (*chess)[] )    //判断是否存在危险

 {

     int i, k, flag1=, flag2=, flag3=, flag4=, flag5=;

     // 判断列方向

     for( i=; i < ; i++ )

     {

         if( *(*(chess+i)+j) !=  )

         {

             flag1 = ;

             break;

         }

     }

     // 判断左上方

     for( i=row, k=j; i>= && k>=; i--, k-- )

     {

         if( *(*(chess+i)+k) !=  )

         {

             flag2 = ;

             break;

         }

     }

     // 判断右下方

     for( i=row, k=j; i< && k<; i++, k++ )

     {

         if( *(*(chess+i)+k) !=  )

         {

             flag3 = ;

             break;

         }

     }

     // 判断左下方

     for( i=row, k=j; i>= && k<; i--, k++ )

     {

         if( *(*(chess+i)+k) !=  )

         {

             flag4 = ;

             break;

         }

     }

     // 判断右上方

     for( i=row, k=j; i< && k>=; i++, k-- )

     {

         if( *(*(chess+i)+k) !=  )

         {

             flag5 = ;

             break;

         }

     }

     if( flag1 || flag2 || flag3 || flag4 || flag5 )

     {

         return ;

     }

     else

     {

         return ;

     }

 }

 // 参数 row：表示起始行

 // 参数 n：表示列数

 // 参数 (*chess)[8]: 表示指向棋盘每一行的指针

 void EightQueen( int row, int n, int (*chess)[] )

 {

     int chess2[][], i, j;

     for( i=; i < ; i++ )

     {

         for( j=; j < ; j++ )

         {

             chess2[i][j] = chess[i][j];

         }

     }

     if(  == row )    //本次解法完毕

     {

         printf("第 %d 种 \n", count+);

         for( i=; i < ; i++ )

         {

             for( j=; j < ; j++ )

             {

                 printf("%d ", *(*(chess2+i)+j));

             }

             printf("\n");

         }

         printf("\n");

         count++;

     }

     else

     {

         for( j=; j < n; j++ )

         {

             if( notDanger( row, j, chess ) ) // 判断这个位置是否存在危险

             {

                 for( i=; i < ; i++ )

                 {

                     *(*(chess2+row)+i) = ;

                 }

                 *(*(chess2+row)+j) = ;

                 EightQueen( row+, n, chess2 );    //没有危险，继续往下

             }

         }

     }

 }

 int main()

 {

     freopen( "output.txt", "w", stdout );    //将输出结果保存到 output.txt中

     int chess[][], i, j;

     for( i=; i < ; i++ )

     {

         for( j=; j < ; j++ )

         {

             chess[i][j] = ;

         }

     }

     EightQueen( , , chess );

     printf("总共有 %d 种解决方法 \n\n", count);

     fclose(stdout);

     return ;

 }

巴特西

【Acm】八皇后问题

最新文章

热门文章