四皇后問(wèn)題
在一個(gè)4×4的國(guó)際象棋棋盤(pán)上痹换，一次一個(gè)地?cái)[放4枚皇后棋子泻帮，擺好后滿足每行精置、每列和對(duì)角線上只允許出現(xiàn)一枚棋子，即棋子間不許相互俘獲锣杂。
回溯策略
- 是否是目標(biāo)狀態(tài)脂倦，是返回1
- 循環(huán)規(guī)則集
- 調(diào)用規(guī)則作用于當(dāng)前狀態(tài)，生成新?tīng)顟B(tài)
- 判斷當(dāng)前狀態(tài)是否合法
- 合法則遞歸調(diào)用
- 不合法取新的規(guī)則
代碼
#include<stdio.h>
/**
*@function 檢測(cè)狀態(tài)是否合法
*
*/
int Validate(int a[4][4], int i, int j) {
int x, y;
// 左上對(duì)角線是否存在皇后
for(x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--) {
if(a[x][y] == 1) {
return 0;
}
}
// 右上對(duì)角線是否存在皇后
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;
// 判斷是否為目標(biāo)狀態(tài)
if(i == 4) {
for(j = 0; j < 4; j++) {
for(k = 0; k < 4; k++) {
printf("%d ", a[j][k]);
}
printf("\n");
}
return 1;
}
// 循環(huán)規(guī)則集
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 主函數(shù)
*
*/
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;
}
