皇后问题回溯算法解决Queen

#include<stdio.h> int x[100]; int abs(int m) //返回绝对值 { if(m < 0) return -m; return m; } bool place(int k) //判断皇后k是否发生冲突 { int i; for(i = 1; i < k; i++) { if(x[k] == x[i] || abs(k - i) == abs(x[k] - x[i])) return false; } return true; } void queen(int n) { int i,k; for(i = 1;i <= n; i++) x[i] = 0; k = 1; while(k >= 1) { x[k] = x[k] + 1; //在下一列放置第k个皇后 while(x[k] <= n && !place(k)) x[k] = x[k] + 1;//搜索下一列 if(x[k] <= n && k == n)//得到一个解 { for(i = 1;i <= n;i++) printf("%d ", x[i]); printf("\n"); //若return则只求出其中一种解 //若不return则可以继续回溯，求出全部的可能的解 } else if(x[k] <= n && k<n) k++; //准备放置下一个皇后 else { x[k] = 0; //不合适，重置x[k],回溯 k--; } } } int main() { int n; printf("输入皇后个数n:"); scanf("%d", &n); queen(n); return 0; }