在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之在同一行或同一列或同一斜线上的旗子。n后问题等价于在n*n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
有俩种解法,第一种采用解空间为N(4)叉树的解法、第二种是采用解空间为排列数的解法。
每个皇后在一行上有四个可选位置。即每个非叶结点有4个子节点,4叉树如下:
解向量:(x1,x2,x3,......,xn)
显约束:任意俩皇后不同行。
隐约束:(1) 不同列:xi ≠ xj (2) 不处于同一正反对角线:|i - j| ≠ |xi - xj|
核心代码:
// 剪枝函数,排除同列和同一对角线的分支
int place1(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k])
return 0;
return 1;
}
// t > n代表当前解已经求出,将总数+1
// 利用循环遍历节点的n叉,同时判断分叉是否符合条件
// 符合条件的分叉继续遍历下去
void BackTrack1(int t) {
if (t > n)
sum++;
else
for (int i = 1; i <= n; i++) {
x[t] = i;
if (place1(t))
BackTrack1(t + 1);
}
}
核心代码:
// 交换俩行皇后的位置
// 实现切换排列数的分支作用
void swap(int i, int j) {
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
// 剪枝函数,排除在同一对角线上的情况
int place2(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]))
return 0;
return 1;
}
// t > n时表示当前排列符合条件,总数 + 1
// 利用for循环,和swap函数,将节点对应的所有排列遍历一次
// 同时采用剪枝函数,减去错误的分支
// 对正确的分支继续求解下去
// 最后递归求解结束后,再次调用swap函数将状态返回到原本的节点状态
void BackTrack2(int t) {
if (t > n) sum++;
else
for (int i = t; i <= n; i++) {
swap(t, i);
if (place2(t))
BackTrack2(t + 1);
swap(t ,i);
}
}
/**
* 回溯法求解n皇后问题
* 使用x解向量,x1,x2,x3分别表示在1,2,3行上皇后的列号
**/
#include <stdio.h>
#include <stdlib.h>
#define MAX 4
/**
* n 皇后个数
* x 当前解
* sum
**/
int n = MAX;
int x[MAX + 1];
long sum = 0;
// 剪枝函数,排除同列和同一对角线的分支
int place1(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k])
return 0;
return 1;
}
// t > n代表当前解已经求出,将总数+1
// 利用循环遍历节点的n叉,同时判断分叉是否符合条件
// 符合条件的分叉继续遍历下去
void BackTrack1(int t) {
if (t > n)
sum++;
else
for (int i = 1; i <= n; i++) {
x[t] = i;
if (place1(t))
BackTrack1(t + 1);
}
}
// 交换俩行皇后的位置
// 实现切换排列数的分支作用
void swap(int i, int j) {
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
// 剪枝函数,排除在同一对角线上的情况
int place2(int k) {
for (int j = 1; j < k; j++)
if (abs(k - j) == abs(x[j] - x[k]))
return 0;
return 1;
}
// t > n时表示当前排列符合条件,总数 + 1
// 利用for循环,和swap函数,将节点对应的所有排列遍历一次
// 同时采用剪枝函数,减去错误的分支
// 对正确的分支继续求解下去
// 最后递归求解结束后,再次调用swap函数将状态返回到原本的节点状态
void BackTrack2(int t) {
if (t > n) sum++;
else
for (int i = t; i <= n; i++) {
swap(t, i);
if (place2(t))
BackTrack2(t + 1);
swap(t ,i);
}
}
void main() {
for (int i = 0; i <= n; i++)
x[i] = i;
BackTrack1(1);
printf("%d\n", sum);
for (int i = 0; i <= n; i++)
x[i] = i;
sum = 0;
BackTrack2(1);
printf("%d\n", sum);
system("pause");
}
联系客服