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

## 递归回溯解八皇后问题

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

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实现经典算法八皇后问题

(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

本文不讲述软件安装过程，记述本人在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