Python实现经典算法八皇后问题

在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问一共有多少种摆法。

分别用递归回溯算法与遗传算法实现,代码如下

递归回溯解八皇后问题

import numpy

def findQueen(column):

    if column > 7:
        global count
        count+=1
        print(matrix)
        return
    else:
        for row in range(8):
            if check(row,column):
                matrix[row][column]=1
                arr[column]=row
                findQueen(column+1)
                matrix[row][column]=0
                arr[column]=0

def check(row,column):
    for k in range(len(arr)):
        if k >= column:
            return True
        if arr[k] == row or abs(arr[k] - row) == abs(k - column):
            return False

if __name__ == '__main__':
    count = 0
    matrix = numpy.zeros((8,8),dtype=int)
    arr = numpy.zeros(8,dtype=int)
    findQueen(0)
    print(count)

遗传算法解八皇后问题

import copy
import random
import math

种群大小
population_size = 8
父种群的编码列表
parent = []
子种群的编码列表
children = []
父种群每个个体的适应度
parent_fitness = []
子种群每个个体的适应度
children_fitness = []

初始化个体
def initial_individual():
    # 个体的编码
    individual = []
    # 8个编码
    for i in range(8):
        a = random.randint(0, 7)
        individual.append(a)
    # 计算生成的个体的适应度
    fit_score = update_fitness_score(individual)
    # 加入到种群中

    parent_fitness.append(fit_score)
    parent.append(individual)
    return

更新适应度函数
def update_fitness_score(individual):
    value = 0
    for i in range(8):
        for j in range(i + 1, 8):
            if individual[i] != individual[j]:
                x = j - i
                y = abs(individual[i] - individual[j])
                if x != y:
                    value += 1
    return value

初始化1个种群,种群大小为population_size
def initial_population():
    for i in range(population_size):
        initial_individual()
    return

选择出一个父本
def select():
    # 所有个体的适应度之和
    total_score = 0
    for fit in parent_fitness:
        total_score += fit

    # 轮盘赌中的数
    num = random.randint(0, total_score)
    # 前面的适应度之和
    front_score = 0
    for i in range(population_size):
        front_score += parent_fitness[i]
        # 如果此时前面的适应度之和大于生成的随机数,那么该数必定落在编号为 i 的个体上
        if front_score >= num:
            return i

变异
def mutation(change_individual):
    # 第pos个基因发生变异
    pos = random.randint(0, 7)
    # 改变的值
    change = random.randint(0, 7)
    change_individual[pos] = change
    return change_individual

交叉产生后代
def hybridization():
    # 选择两个父本
    first = select()
    second = select()
    selected_parents = copy.deepcopy([parent[first], parent[second]])
    # 交换从pos1到pos2的基因
    pos1 = random.randint(0, 6)
    pos2 = random.randint(0, 6)
    # 保证pos1  pos2:
        pos1, pos2 = pos2, pos1
    # 交叉
    tmp = selected_parents[0][pos1:pos2]
    selected_parents[0][pos1:pos2] = selected_parents[1][pos1:pos2]
    selected_parents[1][pos1:pos2] = tmp
    # 一定的概率发生变异,假设概率为0.5
    may = random.random()
    if may > 0.5:
        selected_parents[0] = mutation(selected_parents[0])
    may = random.random()
    if may > 0.5:
        selected_parents[1] = mutation(selected_parents[1])
    # 更新适应度
    first_fit = update_fitness_score(selected_parents[0])
    second_fit = update_fitness_score(selected_parents[1])

    # 加入到子代中
    children.append(selected_parents[0])
    children.append(selected_parents[1])
    children_fitness.append(first_fit)
    children_fitness.append(second_fit)
    return

初始化种群
initial_population()
计算迭代次数
count = 0
not a number
find = float('nan')
while True:
    count += 1
    if count % 1000 == 0:
        print('第%d' % count + '次迭代')
    # 杂交population_size/2次产生population_size个后代
    for k in range(population_size // 2):
        hybridization()
    # 如果某个个体适应度达到28,说明此时找到了一个解
    for k in range(population_size):
        if children_fitness[k] == 28:
            # 记录解的位置
            find = k
            break
    if not math.isnan(find):
        break
    # 将子代种群放入父代中作为新的父代,子代清空
    parent[0:population_size] = children[0:population_size]
    parent_fitness[0:population_size] = children_fitness[0:population_size]
    children = []
    children_fitness = []

此时找到满足要求的子代个体
res = children[find]
print(res)

构造棋盘
res_queen = [[0 for i in range(8)] for j in range(8)]
for t in range(8):
    res_queen[res[t]][t] = 1
将棋盘打印
print("找到结果:")
for t in range(8):
    print(res_queen[t])

Original: https://www.cnblogs.com/left23333/p/16347767.html
Author: Left23333
Title: Python实现经典算法八皇后问题

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/582412/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • 高通MSM8998 ABL的调试

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年10月19日
    0245
  • 【Java】关于Maven仓库地址

    Maven仓库地址 仓库 如果你没有配置阿里云仓库镜像源,可以到这里来找 https://mvnrepository.com/ 如果你配置了阿里云仓库镜像源,可以来这里找 http…

    Linux 2023年6月14日
    070
  • 对脱壳脚本的一些改进–识别出目标DEX

    一、前言 通常对于加壳的程序,第一步的操作通常是脱壳,而现在脱壳一般都选择利用 frida 来进行 hook 进行脱壳,不谈其他脱壳方式,利用 frida 脱壳原理大致分为两种: …

    Linux 2023年6月8日
    076
  • cobbler部署

    cobbler cobbler 一、cobbler简介 二、cobbler对应关系 三、cobbler工作原理 cobbler部署 进行测试 web界面自动安装 一、cobbler…

    Linux 2023年6月6日
    072
  • Debian中CodeIgniter+nginx+MariaDB+phpMyAdmin配置

    本文不讲述软件安装过程,记述本人在Debia 中配置CodeIgniter 时遇到的问题及解决方法,希望能够为有需要的人提供帮助。 一、Debian版本及所需的软件 Debian …

    Linux 2023年6月13日
    069
  • GitHub使用教程for Eclipse

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月30日
    0257
  • Spring常见异常说明

    文章要点 Spring bean 的声明方式 Spring bean 的注入规则 Spring bean 的依赖查找规则 Spring bean 的名称定义方式和默认名称规则 XX…

    Linux 2023年6月6日
    056
  • PHP 获取数组长度

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年10月15日
    0241
  • 实验一 密码引擎-3-电子钥匙功能测试

    任务详情 1 解压”龙脉密码钥匙驱动实例工具等”压缩包2 在Ubuntu中运行 “龙脉密码钥匙驱动实例工具等\mToken-GM3000\skf…

    Linux 2023年6月8日
    069
  • C语言—>指针

    当两个指针 p1, p2相减时, p2-p1就是从 p1到 p2,不包含 p2的元素个数,结果的类型是 ptrdiff_t #include int main() { int a[…

    Linux 2023年6月8日
    064
  • 【Example】C++ 标准库多线程同步及数据共享 (std::future 与 std::promise)

    否则你会像听天书一样懵。(…) ==================================== 在任何语言的多线程编程当中,必然涉及线程的同步及数据的共享,方…

    Linux 2023年6月13日
    073
  • 在Linux下配置RealVNC和TigerVNC

    作者:alittlemc | 更新中 | 原创文章,可能有技术理解错误,欢迎指正,请与我联系,谢谢! 命令和快速总结 realvnc创建# :会话id -name 取名字 -dep…

    Linux 2023年6月6日
    068
  • HCNP Routing&Switching之VRRP基础

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0239
  • ubuntu 16.04 编译安装 amule (开启GUI)

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0258
  • Oracle学习笔记(2)–Centos 7 下11gR2部署

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0273
  • redis重点是 dir 的默认配置一定要改

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年9月14日
    0204
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球