型网站建设,沈阳营商环境建设局网站,北京做网站哪家公司最好,企业自己如何做网站推广本文为大家分享了python八皇后问题的解决方法#xff0c;供大家参考#xff0c;具体内容如下题目#xff1a;给定一个 N*N 正方形棋盘#xff0c;在上面放置 N个棋子#xff0c;又叫皇后#xff0c;使每两个棋子都不在同一条横线上、竖线上、斜线上。一般我们都讨论8皇后…本文为大家分享了python八皇后问题的解决方法供大家参考具体内容如下题目给定一个 N*N 正方形棋盘在上面放置 N个棋子又叫皇后使每两个棋子都不在同一条横线上、竖线上、斜线上。一般我们都讨论8皇后但是只要N 4都会存在解的。分析方法1根据定义来处理即每往棋盘中放置皇后的时候都要判断哪些位置可以放新加入的皇后而哪些地方如果放置皇后的话会造成冲突。我下面写的这个代码就是基于此。方法2、我看了下别人的优化主要是采用位运算来实现计算复杂度降低的我没有用Python 实现这个所以在这里挖一个坑。代码代码里的注释有详细的说明设定N值即可返回一个符合要求的解。但是这个问题还有一个进阶那就是讨论究竟会有多少个解这就需要数论的知识了而且我对这块数学没研究过所以也没有代码实现。大家将就使用一下代码就好了。class EightQueensPuzzle(object):八皇后问题求解代码使用方法eight_q EightQueensPuzzle(4, 5)print EIGHT QUEEDS PUZZLE:result eight_q.eight_queens_puzzle()for i in result:print idef __init__(self, n, char):self.n n # 棋盘维度self.char char # 皇后标记字符def init_chess_board(self, n):初始化一个棋盘棋盘规格可以按参数 n 随意选定,一般都讨论八皇后就选择 8:return: 返回棋盘是一个 8*8 矩阵chess_board []for i in xrange(0, n):line []for j in xrange(0, n):line.append(0)chess_board.append(line)return chess_boarddef update_conflict_board(self, conflict_board, position):for k in xrange(0, self.n): # 为行添加 1conflict_board[position[0]][k] 1for id in xrange(position[0]1, self.n):conflict_board[id][position[1]] 1 # 为列添加 1if position[0] position[1] - id 0: # 为左斜添加 1conflict_board[id][position[0] position[1] - id] 1if position[1] - position[0] id self.n: # 为右斜添加 1conflict_board[id][position[1] - position[0] id] 1def queens_conflict(self, conflict_board, position):当前棋盘的状态是 conflict_board, 判定如果在 position 位置给一个皇后的话会不会出现问题。如果有问题则返回 False如果没有问题返回 Trueif conflict_board[position[0]][position[1]] ! 0:return Falseelse:return Truedef eight_queens_puzzle(self):给出一个八皇后的求解答案。:return:返回一个结果并打印.import randomwhile True: # 不停寻找符合条件的八皇后排列chess_board self.init_chess_board(self.n)conflict_board self.init_chess_board(self.n)for i in xrange(0, self.n):flag 0for cnt in conflict_board[i]:if cnt ! 0:flag 1if flag self.n: # 如果已经1被填满了说明这个答案错误breakwhile True:pos [i, random.randint(0, self.n-1)] # 元组构成皇后的位置if self.queens_conflict(conflict_board, pos): # 如果没有冲突chess_board[i][pos[1]] self.charself.update_conflict_board(conflict_board, pos)breakif self.char in chess_board[self.n-1]:return chess_board以上就是本文的全部内容希望对大家的学习有所帮助也希望大家多多支持脚本之家。
