8皇后问题的三种解法
#define RUN#ifdef RUN#include<stdio.h>//C[x]=y 表示x行的皇后处于y列int C[50], tot = 0, n = 8, nc = 0;void search(int cur) { int i, j; nc++; //检查每个可能，看是否会冲突 if(cur == n) { for(i = 0; i < n; i++) for(j = i+1; j < n; j++) if(C[i] == C[j] || i-C[i] == j-C[j] || i+C[i] == j+C[j]) return;//找到一个没冲突的可能 tot++; } //遍历生成所有的可能 else for(i = 0; i < n; i++) { C[cur] = i; search(cur+1); }}int main() { search(0); printf("%d\n", tot); printf("%d\n", nc); return 0;}#endif

?

?

?

2 回溯法

?

//#define RUN#ifdef RUN#include<stdio.h>//C[x]=y 表示x行的皇后处于y列int C[50], tot = 0, n = 8, nc = 0;void search(int cur) {  int i, j;  nc++;  //递归边界，只要走到这里，所有的皇后必然不冲突  if(cur == n) {    tot++;  }   else {  //对于当前第cur行，逐个测试i从0到n-1，看适合放在哪一列  for(i = 0; i < n; i++) {  int ok = 1;  //假设放在第i列  C[cur] = i;  //测试在前面的行的皇后是否会和当前位置冲突  for(j = 0; j < cur; j++){  //列冲突，主对角线冲突，副对角线冲突  if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j]) {  ok = 0;  break;  }  }  //进行下一行的搜索  if(ok) search(cur+1);  }  }  }int main() {  search(0);  printf("%d\n", tot);  printf("%d\n", nc);  return 0;}#endif

?

?

3 有全局变量的回溯法(最常用)

?

//#define RUN#ifdef RUN#include<stdio.h>#include <string.h>//C[x]=y 表示x行的皇后处于y列int C[50], vis[3][50], tot = 0, n = 8, nc = 0;void search(int cur) {  int i, j;  nc++;  if(cur == n) {    tot++;  }   else{  //测试每一列  for(i = 0; i < n; i++) {  //检测列冲突，副对角线，正对角线冲突  if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]) {  C[cur] = i;  vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;  search(cur+1);  vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;  }  }  }}int main() {  memset(vis, 0, sizeof(vis));  search(0);  printf("%d\n", tot);  printf("%d\n", nc);  return 0;}#endif

?

?

注意：如果在回溯法中使用了辅助的全局变量，则一定要及时把它们恢复原状。例如，若函数有多个出口，则需在每个出口处恢复被修改的值。