八皇后问题独立解Python代码
程序员文章站
2022-05-12 18:32:14
...
八皇后问题其实很有趣,借助这个问题可以很好检验对一门新的语言的理解程度。
使用生成器,在8皇后的时候,以下非独立解决代码的计算次数为46752次:
# !/usr/bin/python # coding:utf-8 # __author__=watson 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 def queens(num=1, state=()): for pos in range(num): if not conflict(state, pos): if len(state) == num-1: yield (pos,) else: for result in queens(num, state + (pos,)): yield (pos,) + result if __name__ == "__main__": print list(queens(8))
使用记忆算法,在8皇后的时候,以下非独立解决代码的计算次数为15720次:
# !/usr/bin/python # coding:utf-8 # __author__=watson column = rup = lup = [] def conflict(line, col, num): if column[col] == 0 and rup[line+col] == 0 and lup[line-col+num] == 0: return False return True def queens(num=1, line=1): for col in range(1, num + 1): if not conflict(line, col, num): if line == num: yield (col,) else: column[col] = rup[line+col] = lup[line-col+num] = 1 for result in queens(num, line + 1): yield (col,) + result column[col] = rup[line+col] = lup[line-col+num] = 0 if __name__ == "__main__": number = 8 column = [0] * (number + 1) rup = [0] * (2*number + 1) lup = [0] * (2*number + 1) print list(queens(number))
使用记忆算法,不使用生成器:
# !/usr/bin/python # coding:utf-8 # __author__=watson number = 0 result = [0] column = [0] rup = [0] lup = [0] no = 0 def backtrack(line): if line > number: show_result() else: for col in range(1, number+1): if column[col] == 0 and rup[line+col] == 0 and lup[line-col+number] == 0: result[line] = col column[col] = rup[line+col] = lup[line-col+number] = 1 backtrack(line + 1) column[col] = rup[line+col] = lup[line-col+number] = 0 def show_result(): global no no += 1 print "result no %r:" % no for i in range(1, number + 1): for j in range(1, number + 1): if result[i] == j: print " Q ", else: print " . ", print "\n" if __name__ == "__main__": number = 8 result = [0] * (number + 1) column = [0] * (number + 1) rup = [0] * (2*number + 1) lup = [0] * (2*number + 1) # print column[number] backtrack(1)
上述算法都是递归算法,在皇后数多的都比较消耗内存。
独立解参考《八皇后问题独立解JAVA代码》:
http://kingxss.iteye.com/blog/2290026