八皇后问题，是19世纪著名的数学家高斯在1850年提出的：在8×8格的国际象棋盘上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上，试问有多少种摆法？高斯先生给出的答案是“76”种，实际是76种吗？
八皇后问题是回溯算法的典型应用，但是本文提供递归的求法。
递归的核心思想可以总结成：把一个复杂的问题无限缩小，每个小问题的解法都是一样的，最终归结于求解每个小问题的原型。递归编程的思路可以假设所有的问题都已解决，来到结束条件，这是非常简单的，然后再调用自身求解整个问题。虽然递归的效率比较低，但是可以大大降低思考的程度。
八皇后问题的递归思路为：先放置第一个皇后；把第一个皇后所能攻击到的区域排除，放置第二个皇后；把第二个皇后所能攻击到的区域排除，放置第三个皇后......直至放置第八个皇后，第八个皇后所能放置的区域只有一个格子。
1 //八皇后问题，递归法实现 2 #include3 4 int count = 0; 5 6 //判断第row行j列是否安全，判断列、左上、右上、左下、右下 7 int Safe( int row, int j, int (*chess)[8]) 8 { 9 int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0; 10 11 //判断列方向是否安全 12 for( i=0; i<8; i++) 13 { 14 if(*(*(chess+i)+j) !=0) 15 { 16 flag1 = 1; //不安全 17 break; 18 } 19 } 20 21 //判断左上方是否安全 22 for( i=row, k=j; i>=0 && k>=0; i--,k--) 23 { 24 if(*(*(chess+i)+k) !=0) 25 { 26 flag2 = 1; //不安全 27 break; 28 } 29 } 30 31 //判断右下方是否安全 32 for( i=row, k=j; i<8 && k<8; i++,k++) 33 { 34 if(*(*(chess+i)+k) !=0) 35 { 36 flag3 = 1; //不安全 37 break; 38 } 39 } 40 41 //判断右上方是否安全 42 for( i=row, k=j; i>=0 && k<8; i--,k++) 43 { 44 if(*(*(chess+i)+k) !=0) 45 { 46 flag4 = 1; //不安全 47 break; 48 } 49 } 50 51 //判断左下方是否安全 52 for( i=row, k=j; i<8 && k>=0; i++,k--) 53 { 54 if(*(*(chess+i)+k) !=0) 55 { 56 flag5 = 1; //不安全 57 break; 58 } 59 } 60 61 if( flag1 || flag2 || flag3 || flag4 || flag5) 62 return 0; 63 else 64 return 1; 65 } 66 67 // row :起始行 68 // n :列数 69 // (*chess)[8] :指向棋盘每一行的指针 70 void EightQueen( int row, int n, int (*chess)[8]) 71 { 72 int i, j, chessTemp[8][8]; //用于存放当前形式的棋盘 73 74 for( i=0; i<8; i++) 75 { 76 for( j=0; j<8; j++) 77 { 78 chessTemp[i][j] = chess[i][j]; 79 } 80 } 81 82 if( 8==row ) //递归终止条件，即假设已经找到一种棋盘分布，将它打印 83 { 84 printf("第 %d 种棋盘：\n",count+1); 85 for( i=0; i<8; i++) 86 { 87 for( j=0; j<8; j++) 88 { 89 printf("%d ",*(*(chessTemp+i)+j)); 90 } 91 printf("\n"); 92 } 93 printf("\n"); 94 count++; 95 } 96 else //进入递归 97 { 98 for( j=0; j