回溯法-N皇后

1.非递归方法#define N 4 int q[N 1]; //检查当前皇后与前i个有没有冲突 int check(int j) { int i; for (i 1; i j; i) { //不在一个行 不在一个斜线上 至于不在一行for循环条局的ij已经有的判断 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); } } } }