【职业规划】八皇后问题_在8×8格的棋盘上放置彼此不受攻击的8个皇后。 按照国际象棋的规则,皇后可以攻击

- 八皇后问题

是回溯算法的典型例题。

该问题是十九世纪著名的数学家高斯1850年提出：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击。

    即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
1

正确的结果应该是： 92种。

第1次考虑把皇后放在第1行的某个位置。

第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。

第2次就考虑把皇后放在第2行的某个位置，第3次考虑把皇后放在第3行的某个位置， 这样依次去递归。

每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。

找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。

找到一组可行解即可输出，然后程序回溯去找下一组可靠解。

我们用一个一维数组来表示相应行对应的列，比如：

c[i]=j//表示， 第i行的皇后放在第j列
1

一共有8列，所以我们要让c[r]依次取第0列，第1列，第2列……

一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。

怎样是有冲突呢？同行，同列，对角线。

由于已经不会同行了，所以不用考虑这一点。

同列：

c[r]==c[j];
1

同对角线有两种可能，即主对角线方向和副对角线方向。

主对角线方向满足，行之差等于列之差：

r-j==c[r]-c[j];
1

副对角线方向满足， 行之差等于列之差的相反数：

r-j==c[j]-c[r]；
1

只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。

C语言实现

#include <stdio.h>
#include <stdlib.h>

int count = 0;

int notDanger( int row, int j, int (*chess)[8] )
{
        int i, k, flag1=0, flag2=0, flag3=0, flag4=0, flag5=0;

        // 判断列方向
        for( i=0; i < 8; i++ )
        {
                if( *(*(chess+i)+j) != 0 )
                {
                        flag1 = 1;
                        break;
                }
        }

        // 判断左上方
        for( i=row, k=j; i>=0 && k>=0; i--, k-- )
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag2 = 1;
                        break;
                }
        }

        // 判断右下方
        for( i=row, k=j; i<8 && k<8; i++, k++ )
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag3 = 1;
                        break;
                }
        }

        // 判断右上方
        for( i=row, k=j; i>=0 && k<8; i--, k++ )
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag4 = 1;
                        break;
                }
        }

        // 判断左下方
        for( i=row, k=j; i<8 && k>=0; i++, k-- )
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag5 = 1;
                        break;
                }
        }

        if( flag1 || flag2 || flag3 || flag4 || flag5 )
        {
                return 0;
        }
        else
        {
                return 1;
        }
}

// 参数row: 表示起始行
// 参数n: 表示列数
// 参数(*chess)[8]: 表示指向棋盘每一行的指针
void EightQueen( int row, int n, int (*chess)[8] )
{
        int chess2[8][8], i, j;

        for( i=0; i < 8; i++ )
        {
                for( j=0; j < 8; j++ )
                {
                        chess2[i][j] = chess[i][j];
                }
        }

        if( 8 == row )
        {
                printf("第 %d 种\n", count+1);
                for( i=0; i < 8; i++ )
                {
                        for( j=0; j < 8; j++ )
                        {
                                printf("%d ", *(*(chess2+i)+j));
                        }
                        printf("\n");
                }
                printf("\n");
                count++;
        }
        else
        {
                for( j=0; j < n; j++ )
                {
                        if( notDanger( row, j, chess ) ) // 判断是否危险
                        {
                                for( i=0; i < 8; i++ )
                                {
                                        *(*(chess2+row)+i) = 0;
                                }

                                *(*(chess2+row)+j) = 1;

                                EightQueen( row+1, n, chess2 );
                        }
                }
        }
}

int main()
{
        int chess[8][8], i, j;

        for( i=0; i < 8; i++ )
        {
                for( j=0; j < 8; j++ )
                {
                        chess[i][j] = 0;
                }
        }

        EightQueen( 0, 8, chess );

        printf("总共有 %d 种解决方法!\n\n", count);

        return 0;
}

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

python实现

def lie(x):
    x.sort()
    if x == [i for i in range(8)]:
        return True
    else:
        return False

def duijiao(x):
    for i in range(8):
        for j in range(i+1,8):
            if abs(x[i][0]-x[j][0]) == abs(x[i][1]-x[j][1]):
                return False
    else:
        return True


time = 0
for a1 in range(8):
    for a2 in range(8):
        for a3 in range(8):
            for a4 in range(8):
                for a5 in range(8):
                    for a6 in range(8):
                        for a7 in range(8):
                            for a8 in range(8):
                                list1 = [a1,a2,a3,a4,a5,a6,a7,a8]
                                list2 = list(enumerate(list1))
                                if lie(list1) and duijiao(list2):
                                    qipan = [[0 for i in range(8)] for j in range(8)]
                                    for each in list2:
                                        qipan[each[0]][each[1]]=1
                                    for each in qipan:
                                        print(each)
                                    print('\n')
                                    time += 1
print('共有解 %d 个' % time)
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