八皇后问题（Python）

一.问题简介

八皇后问题： 如何能在 8*8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了到达此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

二.几种思路和方法

1.回溯法+递归思想

 如图所示，圆圈代表皇后所放的位置，这里如果将棋盘转化为二维矩阵进行遍历比较麻烦，考虑到棋盘的每一行不能同时存在一个以上的皇后，所以将棋盘转化为一个具有八个元素的列表，而皇后的位置（i，j）对应的是列表中（元素的索引值，元素的值），因此放置皇后的操作变成了在列表中的每个位置填值操作，很明显的一个条件是列表中不能有相同的值。图中给出的是某一种情形

接下来直接看代码：

首先是定义一个queen函数，作用就是用来放皇后的位置。然后进入到第一个判断条件：如果当前行的位置遍历到“第9行”，即全部遍历完之后，将所有的结果放入到列表list中；然后是进入循环，在每一行的八个列的位置遍历，如果满足check中所有条件，那么直接递归调用，进入下一行遍历。

check函数：【任两个皇后都不能处于同一条横行】这一条件已经在前面保证成立了，这里只需保证剩下的两个条件【同一条纵行】和【同一条斜线】成立即可。注意：当两个皇后的位置坐标的连线斜率的绝对值为1，则这两个皇后在同一直线上。

def check(self, list, row):        for i in range(row):            if list[i] == list[row] or abs(list[row] - list[i]) == abs(row - i):                return False        return Truedef queen(self, list, row, n):  # list为存储的结果；row是当前行；n为棋盘大小        x=[]        if row == n:            x.extend(list)            self.solves.append(x)            return        for i in range(n):  # 这里的i指的是所在列的值            list[row] = i            if self.check(list, row):                self.queen(list, row + 1, n)

下面是完整代码：

导包：

import numpy as np           # 提供维度数组与矩阵运算import copy                  # 从copy模块导入深度拷贝方法from board import Chessboard

棋盘类的初始化

# 初始化8*8八皇后棋盘chessboard = Chessboard()

# 基于棋盘类，设计搜索策略class Game:    def __init__(self, show = True):        """        初始化游戏状态.        """                self.chessBoard = Chessboard(show)        self.solves = []        self.gameInit()            # 重置游戏    def gameInit(self, show = True):        """        重置棋盘.        """                self.Queen_setRow = [-1] * 8        self.chessBoard.boardInit(False)                    def check(self, list, row):        for i in range(row):            if list[i] == list[row] or abs(list[row] - list[i]) == abs(row - i):                return False        return True    def queen(self, list, row, n):  # list为存储的结果；row是当前行；n为棋盘大小        x=[]        if row == n:            x.extend(list)            self.solves.append(x)            return        for i in range(n):  # 这里的i指的是所在列的值            list[row] = i            if self.check(list, row):                self.queen(list, row + 1, n)        def run(self, row=0):        #self.solves.append([0, 6, 4, 7, 1, 3, 5, 2])        n = 8        list = [0 for _ in range(n)]        self.queen(list,row,n)                def showResults(self, result):        """        结果展示.        """                self.chessBoard.boardInit(False)        for i,item in enumerate(result):            if item >= 0:                self.chessBoard.setQueen(i,item,False)                self.chessBoard.printChessboard(False)        def get_results(self):        """        输出结果.        return: 八皇后的序列解的list.        """                self.run()        return self.solves   

验证一下结果：

game = Game()solutions = game.get_results()print('There are {} results.'.format(len(solutions)))game.showResults(solutions[0])

 可以直接输出所有的结果（92种）：

print(solutions)

2.排列组合的思想

在上面的基础上，可以稍微转化一下思路，放置不同的皇后位置就是将不同的八个元素的作排列组合问题，然后只要再保证“不在同一斜线”这个条件就可以了。下面是代码：

list1=[0,1,2,3,4,5,6,7]result=[]final_result=[]from itertools import  permutations  #permutations函数：可以对集合或字符串进行排序或排列的所有可能的组合for i in permutations(list1,8):          result.append(i)               #转化为排列组合问题，result存储部分可能的结果      #下面只需要从result中找出满足‘任一两个皇后不在同一斜线上’的结果for i in result:    n=0                  #n用以标记那些满足条件的结果；    for j in enumerate(i):        for m in enumerate(i):            if  m!=j and abs(m[0]-j[0])==abs(m[1]-j[1]):  #m！=j是避免对同一个坐标位置进行判断                n+=1           #只要有两个坐标的连线斜率为1，n就不为0    if n==0:        final_result.append(i)                    print(len(final_result))print(final_result)

3.遗传算法

基本原理和步骤   

        遗传算法将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

其计算步骤如下：

（1） 编码：将问题空间转换为遗传空间；

（2）创建初始种群：随机生成P 个染色体作为初始种群；

（3）适应度计算：染色体评价，计算各个染色体的适应度；

（4）选择操作：根据染色体适应度，按选择算子进行染色体的选择；

（5）交叉操作：按交叉概率进行交叉操作；

（6）变异操作：按变异概率进行变异操作；

（7）返回（4）形成新的种群，继续迭代，直到满足终止条件。

 

具体实现代码部分还在写，以后有机会在续上吧。

觉得不错的话，大家给个关注给个赞吧！

来源地址：https://blog.csdn.net/m0_46366547/article/details/127292090