八皇后问题其实很有趣,借助这个问题可以很好检验对一门新的语言的理解程度。
使用生成器,在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
相关推荐
利用yield技术来减少内存使用,代码直接可运行
解决八皇后问题的源码,带有注释,由于数据结构即算法的学习,如有其他需要,请留言
用python实现的八皇后问题求解。刚刚学习python时,用来练手写的代码。分享下~
两个经典小游戏汉诺塔和八皇后问题的python代码实现
八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八...
C语言求解出八皇后所有解,稍作修改可以推至n皇后问题
八皇后的Python连接库,直接在Python里调用就可以了 调用其中的main函数,记得要导包
自己根据拉斯维加斯算法,写的一个用来求解八皇后问题的python程序,其中可以自定义棋盘大小,显示程序的执行时间。
八皇后问题的实现代码,经过测试 可以用
这个文档关于八皇后问题,一共两种代码,输出分别为0和1的矩阵或者直接输出位置序号两种输出结果。代码是C++语言编写。
八皇后问题的源代码,自己用C语言编写的源代码,绝对可以运行。
这个是八皇后问题的一种解法,希望可以给大家参考,有需要的话可以看一下哦!
关于C语言中八皇后的解法,例如穷举法、试探法的非递归和递归实现
用python语言,通过遗传算法,解决八皇后问题,,遗传算法(Genetic algorithm)属于演化计算( evolutionary computing),是随着人工智能领域发展而来的一种智能算法。正如它的名字所示,遗传算法是受达尔文进化论...
该程序主要解决八皇后问题;问题的提出:8*8的棋盘上放置八个皇后,在同一横线、竖线、对角线上会产生冲突,求不产生冲突即8个皇后都安全的放置方法。改变计数即可以求出n皇后的n*n棋盘的放置方法。
算法设计源程序 java代码实现八皇后问题求解
八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题八皇后问题
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
八皇后问题的回溯算法的实现,实现语言为c++
八皇后问题python