飘逸的python - 八皇后问题简洁解法
思路:
- 使用DFS.
- 用一维数组表达坐标,其中下标为行,元素为列.A[i]=j表示将第i行的皇后放在j列上.
- 一行一行依次遍历(从上往下),决定放在哪列(从左往右),这样就不用判断行冲突,只需要判断列冲突和主斜线副斜线冲突.
- (行-列)标识主斜线, (行+列)标识副斜线.
下面上代码.
#coding=utf-8 #风格1 def queen(A, cur=0): if cur==len(A): print A else: for col in range(len(A)): A[cur] = col #表示把第cur行的皇后放在col列上 ok = True for r in range(cur): if A[r]==col or r-A[r]==cur-A[cur] or r+A[r]==cur+A[cur]:#判断是否跟前面的皇后冲突 ok = False break if ok: queen(A, cur+1) #风格2 def queen(A, cur=0): if cur==len(A): print A else: for col in range(len(A)): A[cur] = col #表示把第cur行的皇后放在col列上 for r in range(cur): if A[r]==col or r-A[r]==cur-A[cur] or r+A[r]==cur+A[cur]:#判断是否跟前面的皇后冲突 break else: queen(A, cur+1) #风格3 def queen(A, cur=0): if cur==len(A): print A else: for col in range(len(A)): A[cur] = col #表示把第cur行的皇后放在col列上 if all(A[r]!=A[cur] and r-A[r]!=cur-A[cur] and r+A[r]!=cur+A[cur] for r in range(cur)):#判断是否跟前面的皇后冲突 queen(A, cur+1) queen([None]*8)
这三种风格差别在于"判断是否跟前面的皇后冲突"这里.
分别是ok flag -> for...else... -> all(推导式).
孰好孰坏呢?
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。