四皇后问题
在一个4×4的国际象棋棋盘上，一次一个地摆放4枚皇后棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。
回溯策略
- 是否是目标状态，是返回1
- 循环规则集
- 调用规则作用于当前状态，生成新状态
- 判断当前状态是否合法
- 合法则递归调用
- 不合法取新的规则
代码
#include<stdio.h>
/**
*@function 检测状态是否合法
*
*/
int Validate(int a[4][4], int i, int j) {
int x, y;
// 左上对角线是否存在皇后
for(x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--) {
if(a[x][y] == 1) {
return 0;
}
}
// 右上对角线是否存在皇后
for(x = i - 1,y = j + 1; x >= 0 && y < 4; x--,y++) {
if(a[x][y] == 1) {
return 0;
}
}
// 所在列是否存在皇后
for(x = i - 1; x >= 0; x--) {
if(a[x][j] == 1) {
return 0;
}
}
return 1;
}
/*
*@function 回溯
*
*/
int Resolve(int a[4][4], int i) {
int j, k;
// 判断是否为目标状态
if(i == 4) {
for(j = 0; j < 4; j++) {
for(k = 0; k < 4; k++) {
printf("%d ", a[j][k]);
}
printf("\n");
}
return 1;
}
// 循环规则集
for(j = 0; j < 4; j++) {
a[i][j] = 1;
if(Validate(a, i, j)) {
if(Resolve(a, i + 1)){
a[i][j] = 0;
printf("\n");
continue;
}
}
a[i][j] = 0;
}
return 0;
}
/*
*@function 主函数
*
*/
int main(int argc, char *argv[]) {
int a[4][4];
int i, j;
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
a[i][j] = 0;
}
}
Resolve(a, 0);
return 0;
}
