1 /*  2 ** 八皇后问题  3 */  4   5 #include <stdio.h>  6 #define  TRUE  1  7 #define  FALSE 0  8   9 /* 10 ** 棋盘，8*8的二维矩阵，为全局变量 11 ** 将有皇后的地方设置为TRUE 12 ** FALSE，则没有皇后 13 */ 14 int chessboard[8][8] = { 0 }; 15  16 int conflict( int row, int col ); 17 void print_board(); 18 void place_queen( int row ); 19  20 int main() 21 { 22     place_queen( 0 ); 23     return 0; 24 } 25  26 /* 27 ** 函数功能： 28 **     给定某一行，在该行的每一列上放置皇后，检查是否相互攻击 29 */ 30 void  31 place_queen( int row ) 32 { 33     int col; 34      35     /* 36     ** 尝试在该行的每一列上放置皇后 37     */ 38     for( col = 0; col < 8; ++ col ) 39     { 40         chessboard[ row ][ col ] = TRUE; 41          42         /* 43         ** 检查放上的皇后是否与其他皇后冲突 44         ** 第1行的皇后是第1个放置的，肯定不与其他冲突 45         ** 第1行和第2~7行刚放上的皇后不与其他冲突时，用递归放置下一个皇后 46         ** 第8行放上的皇后不与其他冲突时，打印答案 47         */ 48         if( row == 0 || !conflict( row, col ) ) 49         { 50             if( row < 7 ) 51                 place_queen( row + 1 ); 52             else 53                 print_board(); 54         } 55          56         // 当前位置放上皇后与其他冲突时，将该位置重置为FALSE 57         chessboard[ row ][ col ] = FALSE; 58     } 59 } 60  61 /* 62 ** 函数功能： 63 **     检查在棋盘某个位置放上皇后是否与其他皇后冲突 64 **   说明： 65 **     由于是一行一行从上往下放置皇后的，只需要检查 66 **     当前位置之前的皇后，当前位置之后还没有放置皇后 67 ** 函数返回： 68 **     有冲突，返回TRUE；无冲突，返回FALSE 69 */ 70 int 71 conflict( int row, int col ) 72 { 73     int i; 74     for( i = 1; i < 8; ++ i ) 75     { 76         // 检查当前棋子的上方直线上是否有皇后 77         if( row - i >= 0 && chessboard[ row - i ][ col ] ) 78             return TRUE; 79              80         // 检查当前棋子的左侧直线上是否有皇后 81         if( col - i >= 0 && chessboard[ row ][ col - i ] ) 82             return TRUE; 83              84         // 检查当前棋子的右侧直线上是否有皇后 85         if( col + i < 8 && chessboard[ row ][ col + i ] ) 86             return TRUE; 87              88         // 检查当前棋子左上角对角线上是否有皇后 89         if( row - i >= 0 && col - i >= 0  90             && chessboard[ row - i ][ col - i ] ) 91                 return TRUE; 92                  93         // 检查当前棋子右上角对角线上是否有皇后 94         if( row - i >= 0 && col + i < 8  95             && chessboard[ row - i ][ col + i ] ) 96                 return TRUE;         97     } 98      99     // 执行到这里说明没有冲突，返回FALSE100     return FALSE;101 }102 103 /*104 ** 函数功能：105 **     打印棋盘106 */107 void108 print_board()109 {110     int row;111     int col;112     static int solution_count;  // 静态变量，计算第几个答案113     solution_count ++;114     printf( "Solution %d:\n", solution_count );115     116     /*117     ** 遍历棋盘，并打印118     */119     for( row = 0; row < 8; ++ row )120     {121         for( col = 0; col < 8; ++ col )122         {123             if( chessboard[ row ][ col ] )124                 printf( " Q" );125             else126                 printf( " +" );127         }128         putchar( ‘\n‘ );129     }130     putchar( ‘\n‘ );131 }