首页 > 代码库 > 飘逸的python - 八皇后问题简洁解法
飘逸的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(推导式).
孰好孰坏呢?
飘逸的python - 八皇后问题简洁解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。