1.非递归方法
#define N 4 int q[N + 1]; //检查当前皇后与前i个有没有冲突 int check(int j) { int i; for (i = 1; i < j; i++) { //不在一个行 不在一个斜线上 至于不在一行，for循环条局的i<j已经有的判断 if (q[i]==q[j] || abs(i-j) == abs(q[i]-q[j])) { return 0; } } return 1; } void queen() { int i; //初始 for (i = 1; i <= N; i++) { q[i] = 0; } //方案数 int answer = 0, j = 1; while (j >= 1) { q[j] = q[j] + 1;//踏入第一行第一个各自，上道，从1开始 while (q[j] <= N && !check(j))//不越绝+检查有问题 { //则代表当前q[j] = q[j] + 1的上道有问题，则继续+1 q[j] = q[j] + 1; } //出来代表当前皇后与前面的N皇是不冲突的,但是越界需要判断一下 if (q[j] <= N) { if (j == N)//代表当前走到最后一行，即有一种方案了 { answer = answer + 1; printf("方案%d\n", answer); for (i = 1; i <= N; i++) { printf("%d ", q[i]); } printf("\n"); } else { j = j + 1;//如果不是j == N，代表下面还有行需要走，这里的j不是代指列，是当前走到的行 } } else { q[j] = 0;//回溯回去，当前行的j皇走的失败路线要重置 j = j - 1;//回溯上去第j-1个皇后 } } } int main() { queen(); return 0; }
![]()
2.递归求解方法
void queen(int j)//当前行的的摆放皇后 { int i; for (i = 1; i <= N; i++) { q[j] = i; if (check(j)) { if (j == N) { answer = answer + 1; printf("方案%d\n", answer); for (i = 1; i <= N; i++) { printf("%d ", q[i]); } printf("\n"); } else { queen(j + 1); } } } }
