算法 n-皇后问题 (回溯法)

问题描述

n-皇后问题是在 n 行 n 列的棋盘上放置 n 个皇后，使得皇后彼此之间不受攻击，其规则是任意两个皇后不在同一行、同一列和相同的对角线上 (也就算国际象棋的皇后移动范围)

问题分析

拟采用以下思路解决 n-皇后问题：

第 i 个皇后放在第 i 行

从第一个皇后开始，对每个皇后，从其对应行 (第 i 个皇后对应第 i 行) 的第一列开始尝试若可以放置，确定位置，考虑下一个皇后若与之前的皇后冲突，则考虑下一列若超出最后一列，则重新确定上一个皇后的位置

重复该过程，直到找到所有的放置方案

C 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <math.h>

#define N 4 // 皇后个数

// 判断第 k 个皇后目前放置位置是否与前面的皇后冲突
int isplace(int pos[], int k){
        int i;
        for(i=1; i<k; i++){
            if(pos[i]==pos[k] || fabs(i-k) == fabs(pos[i]-pos[k]))
                return 0;
        }
        return 1;
}

int main(){
    int i,j;
    int count = 1;
    int pos[N+1];

    // 初始化位置
    for(i=1;i<=N;i++)
        pos[i]=0;
    
    j = 1;
    while(j>=1){
        pos[j]=pos[j]+1;

        // 尝试摆放第 i 个皇后
        while(pos[j]<=N && !isplace(pos,j)){
            pos[j]=pos[j]+1;
            // 得到一个摆放方案
        }

        if(pos[j]<=N && j==N){
            printf("方案 %d：", count++);
            for(i=1;i<=N;i++)
                printf("%d", pos[i]);
            printf("\n");
        }

        // 考虑下一个皇后
        if(pos[j]<=N && j<N){
            j+=1;
        }else{ // 返回考虑上一个皇后
            pos[j]=0;
            j-=1;
        }
    }
    return 1;
}