【八皇后问题】
在棋盘上放置8个皇后，使得她们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，要求找出所有解。
【回溯】：当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。递归枚举算法通常被称为回溯法。
1 #include2 3 #define QUEEN_N (8) 4 5 int queen[QUEEN_N][QUEEN_N] = { 6 { 0, 0, 0, 0, 0, 0, 0, 0}, 7 { 0, 0, 0, 0, 0, 0, 0, 0}, 8 { 0, 0, 0, 0, 0, 0, 0, 0}, 9 { 0, 0, 0, 0, 0, 0, 0, 0}, 10 { 0, 0, 0, 0, 0, 0, 0, 0}, 11 { 0, 0, 0, 0, 0, 0, 0, 0}, 12 { 0, 0, 0, 0, 0, 0, 0, 0}, 13 { 0, 0, 0, 0, 0, 0, 0, 0}, 14 }; 15 16 int queen_check(int x, int y) 17 { 18 int i; 19 20 for(i = 0; i < QUEEN_N; i++) 21 { 22 if(queen[i][y] == 1 && i != x) // 检测列 23 return 0; 24 if(queen[x][i] == 1 && i != y) // 检测行 25 return 0; 26 } 27 28 // 检测对角线,x正向方向 29 for(i = x+1; i < QUEEN_N; i++) 30 { 31 if(y + i - x < QUEEN_N) 32 if(queen[i][y+i-x] == 1) 33 return 0; 34 if(y - (i - x) >= 0) 35 if(queen[i][y-i+x] == 1) 36 return 0; 37 } 38 // 检测对角线,x反向方向 39 for(i = x-1; i >=0; i--) 40 { 41 if(y + (x-i) < QUEEN_N) 42 if(queen[i][y+x-i] == 1) 43 return 0; 44 if(y - (x-i) >= 0) 45 if(queen[i][y-x+i] == 1) 46 return 0; 47 } 48 return 1; 49 } 50 51 void queen_print(int queen[QUEEN_N][QUEEN_N]) // 输出棋盘布局 52 { 53 int i, j; 54 55 for(i = 0; i < QUEEN_N; i++) 56 { 57 for(j = 0; j < QUEEN_N; j++) 58 { 59 if(queen[i][j] == 1) 60 { 61 printf("O "); 62 } 63 else 64 { 65 printf("x "); 66 } 67 } 68 printf("\n"); 69 } 70 } 71 72 // 输出所有棋盘 73 void queen_fill(int n) 74 { 75 int i; 76 static int iCount = 0; 77 if(n >= QUEEN_N) // 递归边界。只要走到了这里，所有皇后必然不冲突。 78 { 79 printf("queen_print <%d>\n", iCount++); 80 queen_print(queen); 81 } 82 else 83 { 84 for(i = 0; i < QUEEN_N; i++) // 尝试把第n行的皇后放在第i列 85 { 86 queen[n][i] = 1; 87 if(queen_check(n, i) == 1) 88 { 89 queen_fill(n+1); // 如果合法，则继续递归，放置下一行 90 } 91 queen[n][i] = 0; 92 } 93 } 94 } 95 // 输出第1个棋盘 96 int queen_fill_1(int n) 97 { 98 int i; 99 if(n >= QUEEN_N)100 {101 queen_print(queen);102 return 1;103 }104 else105 {106 for(i = 0; i < QUEEN_N; i++)107 {108 queen[n][i] = 1;109 if(queen_check(n, i) == 1)110 {111 if(queen_fill_1(n+1) == 1)112 return 1;113 }114 queen[n][i] = 0;115 }116 }117 return 0;118 }119 120 // 对于原始棋盘,判断是否能输出满足的棋盘121 int queen_fill_x(int n)122 {123 int i;124 if(n >= QUEEN_N)125 {126 queen_print(queen);127 return 1;128 }129 else130 {131 for(i = 0; i < QUEEN_N; i++)132 {133 if(queen[n][i] == 0)134 {135 queen[n][i] = 1;136 if(queen_check(n, i) == 1)137 {138 if(queen_fill_x(n+1) == 1)139 return 1;140 }141 queen[n][i] = 0;142 }143 else144 {145 if(queen_check(n, i) == 1)146 {147 if(queen_fill_x(n+1) == 1)148 return 1;149 }150 }151 }152 }153 return 0;154 }155 156 int main(void)157 {158 int iRet;159 printf("init queen:\n");160 queen_print(queen);161 162 printf("queen_fill_x:\n");163 iRet = queen_fill_x(0);164 if(iRet != 1)165 {166 printf("xxx err\n");167 }168 169 printf("queen_fill_1:\n");170 queen_fill_1(0);171 172 printf("queen_fill_all:\n");173 queen_fill(0);174 175 return 0;176 }
在编写递归枚举程序之前，需要深入分析问题，对模型精雕细琢。一般还应对解答树的结点数有一个粗略的估计，作为对评价模型的重要依据。
递归解决问题的思想：
if 问题足够简单：
直接解决问题
返回解
else：
将问题分解为与原问题同构的一个或多个更小的问题
逐个解决这些更小的问题
将结果组合为，获得最终的解
返回解