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