0%

Eight Queens Problem

Posted on Edited on In Disqus:
Symbols count in article: 10k Reading time ≈ 9 mins.

八皇后问题

回溯算法 Backtracking

  • 在递归迭代的过程中
    它不像普通的递归迭代，单向的向深处迭代（每次迭代，N逐渐变小），然后单向返回，比如之前说的“阶乘”和“Fibonacci数列”
  • 在迭代的过程中
    有进有退，它在前向迭代的过程中，如果遇到“死胡同”，比如在第n次迭代时（棋盘的第n行），无论这个皇后放在0-7中的任何一格，都会与之前的那些皇后中的一个产生冲突，那么，算法会退回到前一次迭代（n-1行），并选择其他格。
  • 同样的，如果遍历了n-1行，也不行，算法还会继续回退。

书上的python实现

  • 添加了一部分打印输出的代码，可以方便的看到递归的深度。
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
import random
space = "+ ------------------------- "
def conflict(state, nextX):
    nextY = len(state)
    for i in range(nextY):

        if abs(state[i]-nextX) in (0, nextY-i):
            return True
    return False

# 根据当前棋局（state）找出下一行可以放置皇后的位置(pos)
def queens(num=8, state=()):
    # 在当前所有的棋局（state）里，逐一尝试在下一行的0-8个位置可否放置皇后
    for pos in range(num):
        print(f"{space*len(state)}在棋局为{state}的情况下检查：({pos},{len(state)})")
        if not conflict(state, pos):
            # 该位置（pos）没有冲突
            print("{}({}, {}): sucessed".format(space*len(state), pos, len(state)))
            if len(state) == num-1:
                # 这是棋盘的最后一行
                print(f"试了半天终于凑出一盘棋了，yield最后一行皇后在位置：{pos}")
                yield (pos,)
            else:
                # 不是最后一行
                for result in queens(num, state + (pos,)):
                    # 将新的棋局（state=state+(pos,)) 作为参数，寻找下一行可以放置皇后的位置
                    print(f"yield本行的位置在：{pos} + 之前找到的位置: {result}")
                    yield (pos,) + result
                    print("在状态为", state, "的情况下找到了", (pos,) + result, "，继续往下找")
        else:
            print("{}({}, {}): failed".format(space*len(state), pos, len(state)))


def prettyprint(solution):
    def line(pos, length=len(solution)):
        return '. ' * (pos) + 'X ' + '. ' * (length - pos - 1)

    for pos in solution:
        print(line(pos))


# print(list(queens(4)))
for i in queens(4):
    print(f"找到一个盘可行的摆棋：{i}")
    prettyprint(i)
    print(f"\n\n继续查找下一盘棋 ：__next__()....")

# prettyprint(random.choice(list(queens(4))))
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
在棋局为()的情况下检查：(0,0)
(0, 0): sucessed
+ ------------------------- 在棋局为(0,)的情况下检查：(0,1)
+ ------------------------- (0, 1): failed
+ ------------------------- 在棋局为(0,)的情况下检查：(1,1)
+ ------------------------- (1, 1): failed
+ ------------------------- 在棋局为(0,)的情况下检查：(2,1)
+ ------------------------- (2, 1): sucessed
+ ------------------------- + ------------------------- 在棋局为(0, 2)的情况下检查：(0,2)
+ ------------------------- + ------------------------- (0, 2): failed
+ ------------------------- + ------------------------- 在棋局为(0, 2)的情况下检查：(1,2)
+ ------------------------- + ------------------------- (1, 2): failed
+ ------------------------- + ------------------------- 在棋局为(0, 2)的情况下检查：(2,2)
+ ------------------------- + ------------------------- (2, 2): failed
+ ------------------------- + ------------------------- 在棋局为(0, 2)的情况下检查：(3,2)
+ ------------------------- + ------------------------- (3, 2): failed
+ ------------------------- 在棋局为(0,)的情况下检查：(3,1)
+ ------------------------- (3, 1): sucessed
+ ------------------------- + ------------------------- 在棋局为(0, 3)的情况下检查：(0,2)
+ ------------------------- + ------------------------- (0, 2): failed
+ ------------------------- + ------------------------- 在棋局为(0, 3)的情况下检查：(1,2)
+ ------------------------- + ------------------------- (1, 2): sucessed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(0, 3, 1)的情况下检查：(0,3)
+ ------------------------- + ------------------------- + ------------------------- (0, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(0, 3, 1)的情况下检查：(1,3)
+ ------------------------- + ------------------------- + ------------------------- (1, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(0, 3, 1)的情况下检查：(2,3)
+ ------------------------- + ------------------------- + ------------------------- (2, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(0, 3, 1)的情况下检查：(3,3)
+ ------------------------- + ------------------------- + ------------------------- (3, 3): failed
+ ------------------------- + ------------------------- 在棋局为(0, 3)的情况下检查：(2,2)
+ ------------------------- + ------------------------- (2, 2): failed
+ ------------------------- + ------------------------- 在棋局为(0, 3)的情况下检查：(3,2)
+ ------------------------- + ------------------------- (3, 2): failed
在棋局为()的情况下检查：(1,0)
(1, 0): sucessed
+ ------------------------- 在棋局为(1,)的情况下检查：(0,1)
+ ------------------------- (0, 1): failed
+ ------------------------- 在棋局为(1,)的情况下检查：(1,1)
+ ------------------------- (1, 1): failed
+ ------------------------- 在棋局为(1,)的情况下检查：(2,1)
+ ------------------------- (2, 1): failed
+ ------------------------- 在棋局为(1,)的情况下检查：(3,1)
+ ------------------------- (3, 1): sucessed
+ ------------------------- + ------------------------- 在棋局为(1, 3)的情况下检查：(0,2)
+ ------------------------- + ------------------------- (0, 2): sucessed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(1, 3, 0)的情况下检查：(0,3)
+ ------------------------- + ------------------------- + ------------------------- (0, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(1, 3, 0)的情况下检查：(1,3)
+ ------------------------- + ------------------------- + ------------------------- (1, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(1, 3, 0)的情况下检查：(2,3)
+ ------------------------- + ------------------------- + ------------------------- (2, 3): sucessed
试了半天终于凑出一盘棋了，yield最后一行皇后在位置：2
yield本行的位置在：0 + 之前找到的位置: (2,)
yield本行的位置在：3 + 之前找到的位置: (0, 2)
yield本行的位置在：1 + 之前找到的位置: (3, 0, 2)
找到一个盘可行的摆棋：(1, 3, 0, 2)
. X . .
. . . X
X . . .
. . X .


继续查找下一盘棋 ：__next__()....
在状态为 () 的情况下找到了 (1, 3, 0, 2) ，继续往下找
在状态为 (1,) 的情况下找到了 (3, 0, 2) ，继续往下找
在状态为 (1, 3) 的情况下找到了 (0, 2) ，继续往下找
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(1, 3, 0)的情况下检查：(3,3)
+ ------------------------- + ------------------------- + ------------------------- (3, 3): failed
+ ------------------------- + ------------------------- 在棋局为(1, 3)的情况下检查：(1,2)
+ ------------------------- + ------------------------- (1, 2): failed
+ ------------------------- + ------------------------- 在棋局为(1, 3)的情况下检查：(2,2)
+ ------------------------- + ------------------------- (2, 2): failed
+ ------------------------- + ------------------------- 在棋局为(1, 3)的情况下检查：(3,2)
+ ------------------------- + ------------------------- (3, 2): failed
在棋局为()的情况下检查：(2,0)
(2, 0): sucessed
+ ------------------------- 在棋局为(2,)的情况下检查：(0,1)
+ ------------------------- (0, 1): sucessed
+ ------------------------- + ------------------------- 在棋局为(2, 0)的情况下检查：(0,2)
+ ------------------------- + ------------------------- (0, 2): failed
+ ------------------------- + ------------------------- 在棋局为(2, 0)的情况下检查：(1,2)
+ ------------------------- + ------------------------- (1, 2): failed
+ ------------------------- + ------------------------- 在棋局为(2, 0)的情况下检查：(2,2)
+ ------------------------- + ------------------------- (2, 2): failed
+ ------------------------- + ------------------------- 在棋局为(2, 0)的情况下检查：(3,2)
+ ------------------------- + ------------------------- (3, 2): sucessed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(2, 0, 3)的情况下检查：(0,3)
+ ------------------------- + ------------------------- + ------------------------- (0, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(2, 0, 3)的情况下检查：(1,3)
+ ------------------------- + ------------------------- + ------------------------- (1, 3): sucessed
试了半天终于凑出一盘棋了，yield最后一行皇后在位置：1
yield本行的位置在：3 + 之前找到的位置: (1,)
yield本行的位置在：0 + 之前找到的位置: (3, 1)
yield本行的位置在：2 + 之前找到的位置: (0, 3, 1)
找到一个盘可行的摆棋：(2, 0, 3, 1)
. . X .
X . . .
. . . X
. X . .


继续查找下一盘棋 ：__next__()....
在状态为 () 的情况下找到了 (2, 0, 3, 1) ，继续往下找
在状态为 (2,) 的情况下找到了 (0, 3, 1) ，继续往下找
在状态为 (2, 0) 的情况下找到了 (3, 1) ，继续往下找
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(2, 0, 3)的情况下检查：(2,3)
+ ------------------------- + ------------------------- + ------------------------- (2, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(2, 0, 3)的情况下检查：(3,3)
+ ------------------------- + ------------------------- + ------------------------- (3, 3): failed
+ ------------------------- 在棋局为(2,)的情况下检查：(1,1)
+ ------------------------- (1, 1): failed
+ ------------------------- 在棋局为(2,)的情况下检查：(2,1)
+ ------------------------- (2, 1): failed
+ ------------------------- 在棋局为(2,)的情况下检查：(3,1)
+ ------------------------- (3, 1): failed
在棋局为()的情况下检查：(3,0)
(3, 0): sucessed
+ ------------------------- 在棋局为(3,)的情况下检查：(0,1)
+ ------------------------- (0, 1): sucessed
+ ------------------------- + ------------------------- 在棋局为(3, 0)的情况下检查：(0,2)
+ ------------------------- + ------------------------- (0, 2): failed
+ ------------------------- + ------------------------- 在棋局为(3, 0)的情况下检查：(1,2)
+ ------------------------- + ------------------------- (1, 2): failed
+ ------------------------- + ------------------------- 在棋局为(3, 0)的情况下检查：(2,2)
+ ------------------------- + ------------------------- (2, 2): sucessed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(3, 0, 2)的情况下检查：(0,3)
+ ------------------------- + ------------------------- + ------------------------- (0, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(3, 0, 2)的情况下检查：(1,3)
+ ------------------------- + ------------------------- + ------------------------- (1, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(3, 0, 2)的情况下检查：(2,3)
+ ------------------------- + ------------------------- + ------------------------- (2, 3): failed
+ ------------------------- + ------------------------- + ------------------------- 在棋局为(3, 0, 2)的情况下检查：(3,3)
+ ------------------------- + ------------------------- + ------------------------- (3, 3): failed
+ ------------------------- + ------------------------- 在棋局为(3, 0)的情况下检查：(3,2)
+ ------------------------- + ------------------------- (3, 2): failed
+ ------------------------- 在棋局为(3,)的情况下检查：(1,1)
+ ------------------------- (1, 1): sucessed
+ ------------------------- + ------------------------- 在棋局为(3, 1)的情况下检查：(0,2)
+ ------------------------- + ------------------------- (0, 2): failed
+ ------------------------- + ------------------------- 在棋局为(3, 1)的情况下检查：(1,2)
+ ------------------------- + ------------------------- (1, 2): failed
+ ------------------------- + ------------------------- 在棋局为(3, 1)的情况下检查：(2,2)
+ ------------------------- + ------------------------- (2, 2): failed
+ ------------------------- + ------------------------- 在棋局为(3, 1)的情况下检查：(3,2)
+ ------------------------- + ------------------------- (3, 2): failed
+ ------------------------- 在棋局为(3,)的情况下检查：(2,1)
+ ------------------------- (2, 1): failed
+ ------------------------- 在棋局为(3,)的情况下检查：(3,1)
+ ------------------------- (3, 1): failed

Process finished with exit code 0