看sicp看到8皇后谜题, 突然兴致来了,尝试独立解决(scheme代码的好处在于,即使你瞟了眼答案, 也不会有任何收获, 除了知道那儿有一坨神秘的括号和英文字符外但Python代码就不同了),成功了,而且还是N皇后算法(把N个皇后放到N*N正方形方格中有多少种方法, N为自然数).
最简单的情况是, 给你一个1*N的矩形, 需要把1个皇后放进去, 有多少种放法? 显然, 有N种放法. 这就是递归的终点. 那么如何把N*N的正方形转化为这种最简单的情况呢?
把N*N正方格分为两个矩形, 一个是1*N矩形A1, 另一个是(N-1)*N矩形B1. 则矩形B1里面必定有且仅有N-1个皇后, 现在只需要考虑如何把最后一个皇后F放到矩形A1里面就可以了.
矩形A1的皇后F的坐标(x, y), 它不能和矩形B1里面的任何一个皇后的坐标(px, px) 在同一水平(x==px), 或在同一垂直(y==py), 或在同一斜线(py-y==px-x 或 py-y==x-px), 符合条件的(x,y)加上矩形B里面的N-1个皇后的坐标组, 就构成了一个解.
上面解决了一般情形,接下来,需要把问题向最简单的情况分解:
考虑矩形B1, 它可以类似地分为一个1*N矩形和(N-2)*N矩形B2, 矩形B2里面有N-2个皇后;
考虑矩形B2, 它可以类似地分为一个1*N矩形和(N-3)*N矩形B3, 矩形B3里面有N-3个皇后;
....
考虑矩形B(N-2), 它可以类似地分为一个1*N矩形和1*N矩形B(N-1), 矩形B(N-1)里面有1个皇后;
这样, 矩形B(N-1)就是我们要的最简单的情况了.
把N*N正方形方格抽象为一个平面直角坐标系, 且0<= x, y <=N-1.
把问题输入抽象为一个整数N, 输出抽象为一组坐标组. 例如当N=4时,有2个坐标组能满足条件,分别是(0, 1), (1, 3), (2, 0), (3, 2)和(0, 2), (1, 0), (2, 3), (3, 1).
def nqueen(n):
def recur(x):
if x==0:
for y in range(n):
yield ((0, y),)
else:
for sln in recur(x-1):
for y in range(n):
if all((y!=py and py-y!=px-x and py-y!=x-px) for px, py in sln):
yield sln + ((x, y),)
return recur(n-1) def visual(n, sln):
for y in range(n-1,-1,-1):
for x in range(n):
if (x, y) in sln:
print('* ',end='')
else:
print('0 ',end='')
print()
print() if __name__=='__main__':
n = 4
for sln in nqueen(n):
print(sln)
visual(n,sln)
结果:
>>>
((0, 1), (1, 3), (2, 0), (3, 2))
0 * 0 0
0 0 0 *
* 0 0 0
0 0 * 0 ((0, 2), (1, 0), (2, 3), (3, 1))
0 0 * 0
* 0 0 0
0 0 0 *
0 * 0 0
问题解出的那一刻, 心里还是有些小激动, 因为这说明自己运用递归解决看似复杂问题的能力在增强. 放到以前, 我肯定在各种分类讨论中迷失, 或者想着想着就因为诸如"这太难了,头脑已想爆"的感慨而放弃.
不过, 更奇特的是, 我尝试着把nqueen的基本情况再往前推一步(纯粹是基于一种感觉):
def nqueen(n):
def recur(x):
if x== -1:
yield ()
else:
for sln in recur(x-1):
for y in range(n):
if all((y!=py and py-y!=px-x and py-y!=x-px) for px, py in sln):
yield sln + ((x, y),)
return recur(n-1)
竟然完完全全没有问题!!
这一刻我对递归的神奇佩服的五体投地...