Python算法题集_N 皇后

Python算法题集_N 皇后

  • 题51：N 皇后
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【规则遍历合理性+回溯】
    • 2) 改进版一【线状态检测合理性+回溯】
    • 3) 改进版二【单行矩阵+回溯】
  • 4. 最优算法
  • 5. 相关资源

本文为Python算法题集之一的代码示例

题51：N 皇后

1. 示例说明

  • 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

    给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    示例 1：

    img

    输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

    示例 2：

    输入：n = 1
输出：[["Q"]]

    提示：

    • 1 <= n <= 9

2. 题目解析

- 题意分解

  1. 本题是在矩阵内摆放Q皇后，并且不违反规则的问题
  2. 矩阵大小为nn，要放n个Q皇后，代表每行、每列最多有一个Q皇后；额外的规则是斜线，左斜线有(2n-1)条，右斜线有(2*n-1)条【类似2.5d地图】
  3. 核心计算有两层，一是回溯遍历，二是当前位置Q是否合乎规则判断
  4. 回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

- 优化思路

  1. 通常优化：减少循环层次

  2. 通常优化：增加分支，减少计算集

  3. 通常优化：采用内置算法来提升计算速度

  4. 分析题目特点，分析最优解

    1. 可以进行规则遍历进行合理性函数检测

    2. 可以保存列、左斜线、右斜线是否被占据的状态，通过线状态检测判定是否合理

    3. 因每行仅有一个Q皇后，因此整个矩阵可以用一维列表保存，位置代表行，值代表此行的Q皇后列下标

- 测量工具

  • 本地化测试说明：LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】，因此需要本地化测试解决数据波动问题
  • CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成，详见章节【最优算法】，代码文件包含在【相关资源】中

3. 代码展开

1) 标准求解【规则遍历合理性+回溯】

通过规则遍历的合理性函数，实现回溯求解

页面功能测试，凄凄惨惨，超过28%

import CheckFuncPerf as cfp

class Solution:
 def solveNQueens_base(self, n):
     def isValid(board, row, col):
         ilen = len(board)
         for irow in range(row):
             if board[irow][col] == 'Q':
                 return False
         for irow, icol in zip(range(row - 1, -1, -1), range(col + 1, ilen, 1)):
             if board[irow][icol] == 'Q':
                 return False
         for irow, icol in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
             if board[irow][icol] == 'Q':
                 return False
         return True
     board = [['.'] * n for x in range(n)]
     result, isize = [], n
     def backtrack(irow):
         if irow == isize:
             tmpmap = [''.join(x) for x in board]
             result.append(tmpmap)
             return
         for icol in range(isize):
             if not isValid(board, irow, icol):
                 continue
             board[irow][icol] = 'Q'
             backtrack(irow + 1)
             board[irow][icol] = '.'
     backtrack(0)
     return result

aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.solveNQueens_base, ilen)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
 
# 运行结果
函数 solveNQueens_base 的运行时间为 61887.03 ms；内存使用量为 75908.00 KB 执行结果 = 73712

2) 改进版一【线状态检测合理性+回溯】

通过线状态检测位置合理性，实现回溯求解，此检测方法实际上将二维平面的遍历转化为了一维的循环，减少了一层循环

页面功能测试，性能一般，超过76%

import CheckFuncPerf as cfp

class Solution:
 def solveNQueens_ext1(self, n):
     from copy import deepcopy
     def backtrack(irow, cols, dgs, adgs, currmap, result):
         ilen = len(cols)
         if irow == ilen:
             result.append(deepcopy(currmap))
             return result
         for icol in range(ilen):
             if cols[icol] or dgs[irow + icol] or adgs[irow - icol + ilen - 1]:
                 continue
             currmap[irow][icol] = "Q"
             cols[icol] = True
             dgs[irow + icol] = True
             adgs[irow - icol + ilen - 1] = True
             backtrack(irow + 1, cols, dgs, adgs, currmap, result)
             adgs[irow - icol + ilen - 1] = False
             dgs[irow + icol] = False
             cols[icol] = False
             currmap[irow][icol] = "."
     statecols = [False for x in range(n)]
     statedgs = [False for x in range(2 * n - 1)]
     stateadgs = [False for x in range(2 * n - 1)]
     currmap = [["." for x in range(n)] for y in range(n)]
     result = []
     backtrack(0, statecols, statedgs, stateadgs, currmap, result)
     for statemap in result:
         for irow in range(len(statemap)):
             statemap[irow] = "".join(statemap[irow])
     return result

aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.solveNQueens_ext1, ilen)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
 
# 运行结果
函数 solveNQueens_ext1 的运行时间为 13925.13 ms；内存使用量为 199784.00 KB 执行结果 = 73712

3) 改进版二【单行矩阵+回溯】

使用单行列表存储矩阵，通过计算判断合理性，实现回溯算法

页面功能测试，马马虎虎，超过53%

import CheckFuncPerf as cfp

class Solution:
 def solveNQueens_ext2(self, n):
     result = []
     def nqbacktrack(currmap):
         if len(currmap) == n:
             result.append(["." * (x-1) +"Q" +"." * (n-x) for x in currmap])
         rows = [x for x in range(1, n+1)]
         for irow in rows:
             if irow in currmap:
                 continue
             tmpFlag = False
             for icol, val in enumerate(currmap):
                 if abs(val-irow) == len(currmap)-icol:
                     tmpFlag = True
             if tmpFlag:
                 continue
             currmap.append(irow)
             nqbacktrack(currmap)
             currmap.pop()
     nqbacktrack([])
     return result

aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.solveNQueens_ext2, ilen)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
 
# 运行结果
函数 solveNQueens_ext2 的运行时间为 31577.39 ms；内存使用量为 66228.00 KB 执行结果 = 73712

4. 最优算法

根据本地日志分析，最优算法为第2种方式【线状态检测合理性+回溯】solveNQueens_ext1

本题测试数据，似乎能推出以下结论：

  1. 布尔计算性能优于数值计算
  2. 减少循环层次可以明显提升性能
ilen = 13
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.solveNQueens_base, ilen)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.solveNQueens_ext1, ilen)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.solveNQueens_ext2, ilen)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 算法本地速度实测比较
函数 solveNQueens_base 的运行时间为 61887.03 ms；内存使用量为 75908.00 KB 执行结果 = 73712
函数 solveNQueens_ext1 的运行时间为 13925.13 ms；内存使用量为 199784.00 KB 执行结果 = 73712
函数 solveNQueens_ext2 的运行时间为 31577.39 ms；内存使用量为 66228.00 KB 执行结果 = 73712

5. 相关资源

本文代码已上传到CSDN，地址：Python算法题源代码_LeetCode(力扣)_N皇后

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/436662.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

文生视频Sora模型发布，是否引爆AI芯片热潮

文生视频Sora模型发布，是否引爆AI芯片热潮

文生视频Sora模型发布&#xff0c;是否引爆AI芯片热潮 1. 引言 在人工智能的历史长河中&#xff0c;每一次技术的飞跃都伴随着社会生产力的巨大变革。自2015年以来&#xff0c;深度学习技术的突破性进展&#xff0c;尤其是在自然语言处理、图像识别和机器学习等领域的成功应…
阅读更多...
检测螺栓扭矩的方法有哪些——SunTorque智能扭矩系统

检测螺栓扭矩的方法有哪些——SunTorque智能扭矩系统

螺栓扭矩的检测是确保螺栓连接紧固程度和安全性的重要环节。正确的扭矩检测能够预防螺栓松动、断裂等潜在风险&#xff0c;从而保障设备和结构的稳定运行。SunTorque智能扭矩系统接下来将详细介绍螺栓扭矩的检测方法。 螺栓扭矩的检测是确保螺栓连接紧固程度和安全性的重要环节…
阅读更多...
刷题笔记day27-回溯算法3

刷题笔记day27-回溯算法3

39. 组合总和 var path []int var tmp []int var result [][]int// 还是需要去重复&#xff0c;题目中要求的是至少一个数字备选的数量不同。 // 所以需要剪枝操作&#xff0c;右边的要比左边的> func combinationSum(candidates []int, target int) [][]int {// 组合问题pa…
阅读更多...
Ubuntu环境配置-LinuxQQ篇

Ubuntu环境配置-LinuxQQ篇

本教程下载Linux QQ的版本是linuxqq_3.0.0-571_amd64.deb 一、下载LinuxQQ 直接使用wget命令下载链接&#xff0c;下载文件 wget https://dldir1.qq.com/qqfile/qq/QQNT/c005c911/linuxqq_3.0.0-571_amd64.deb 二、安装LinuxQQ 当下载完成后&#xff0c;运行命令&#xff1a;…
阅读更多...
数据结构界的终极幻神----树

数据结构界的终极幻神----树

目录 一.数的概念和分类 种类 二.重点概念 哈希树: 二叉树的线索化 什么是线索化 为什么要线索化 特殊的查找树 完全二叉树 三.手撕完全二叉树(堆) 重点讲解 向上搜索算法 向下搜索算法 一.数的概念和分类 树&#xff08;tree&#xff09;是包含 n(n≥0) [2] 个节…
阅读更多...
4万+条LDZ数据上线啦！快来体验专属于你的设计数据包

4万+条LDZ数据上线啦！快来体验专属于你的设计数据包

利驰电天下资源集市LDZ库正式上线后&#xff0c;物料数据已更新至44151条&#xff01;你在做自动化设计时找不到元件物料&#xff1f;物料过时&#xff1f;物料信息有误&#xff1f;花高价买的物料信息重复&#xff1f;利驰官方的LDZ库可以帮助你解决这些问题。 LDZ库为电气设…
阅读更多...
解决 Pandas 导出文件出现 dtype: object 字样

解决 Pandas 导出文件出现 dtype: object 字样

文章目录 1. 问题2. 解决方法 1. 问题 python 用 pandas 输出 excel 文件时&#xff0c;发现有些列的单元格出现 “dtype: object” 的字样&#xff0c;如下图&#xff1a; 这是 pandas 没有处理好导致的 2. 解决方法 结果用 .values 进行输出&#xff0c;这样就转成字符串…
阅读更多...
请说明Vue中的Error Boundaries

请说明Vue中的Error Boundaries

当我们开发基于Vue框架的应用时&#xff0c;我们经常会遇到各种错误处理的情况。Vue提供了一种非常强大且简单的方式来处理这些错误&#xff0c;那就是Error Boundaries&#xff08;错误边界&#xff09;。本文将从概念、用法和示例代码三个方面来详细介绍Vue中的Error Boundar…
阅读更多...
多媒体信息处理-重点知识-3. Feature Indexing and Retrieval

多媒体信息处理-重点知识-3. Feature Indexing and Retrieval

Chap 3. Feature Indexing and Retrieval 什么是索引&#xff1f; 为了提高数据集的检索效率而生成的结构化信息 基于特征的相似度匹配是多媒体数据检索方法的基础 从多媒体对象中提取重要特征&#xff0c;将其转化成高维特征向量存储在数据库中 相似性度量&#xff1a; 两种…
阅读更多...
springboot245科研项目验收管理系统

springboot245科研项目验收管理系统

科研项目验收管理系统 摘 要 使用旧方法对科研项目信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在科研项目信息的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次…
阅读更多...
Tomcat性能调优

Tomcat性能调优

1‍.应用场景/常见内容溢出问题‍ 常见问题为内存溢出&#xff0c;分为堆内存溢出、非堆内存溢出&#xff0c;比较常见的为堆内存溢出&#xff0c;后2类属于非堆内存溢出。 堆溢出&#xff1a; java.lang.OutOfMemoryError:Java heap spcace 原因:项目运行阶段,new的对象过多…
阅读更多...
Linux CentOS系统安装Spug并结合内网穿透实现远程访问本地运维平台

Linux CentOS系统安装Spug并结合内网穿透实现远程访问本地运维平台

目录 前言 1. Docker安装Spug 2 . 本地访问测试 3. Linux 安装cpolar 4. 配置Spug公网访问地址 5. 公网远程访问Spug管理界面 6. 固定Spug公网地址 结语 作者简介&#xff1a; 懒大王敲代码&#xff0c;计算机专业应届生 今天给大家聊聊Linux CentOS系统安装Spug并结合…
阅读更多...
Leetcode刷题（三十八）

Leetcode刷题（三十八）

旋转矩阵&#xff08;Medium&#xff09; 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。示例 1&#xff1a;输入&#xff1a;mat…
阅读更多...
Blazor系统教程(.net8)

Blazor系统教程(.net8)

Blazor系统教程 1.认识 Blazor 简单来讲&#xff0c;Blazor旨在使用C#来替代JavaScript的Web应用程序的UI框架。其主要优势有&#xff1a; 使用C#编写代码&#xff0c;这可提高应用开发和维护的效率利用现有的NET库生态系统受益于NET的性能、可靠性和安全性与新式托管平台(如…
阅读更多...
MYSQL使用mysqldump备份、复原数据库

MYSQL使用mysqldump备份、复原数据库

参考 添加链接描述 1. 备份数据库 C:\Windows\system32>mysqldump -uroot -p test student>C:\student.sql Enter password: ****2. 备份多个数据库 mysqldump -u root -p --databases test mysql>C:\testandmysql.sql3. 备份所有数据库 mysqldump -u root -p -…
阅读更多...
二维码样式修改如何在线处理？在电脑上改二维码图案的方法

二维码样式修改如何在线处理？在电脑上改二维码图案的方法

随着网络的不断发展&#xff0c;二维码的应用场景不断增多&#xff0c;很多人都会将内容放到二维码中&#xff0c;通过扫码的方式将储存在云端的数据调取显示。而面对不同的用途时&#xff0c;对二维码的样式也会有单独的要求&#xff0c;比如需要改变颜色、加入文字、logo、尺…
阅读更多...
加油！你也可以成为学生口中的“好老师”

加油！你也可以成为学生口中的“好老师”

在教育的道路上&#xff0c;每一位教师都承载着塑造未来的重要使命。而成为学生口中的“好老师”&#xff0c;无疑是每位教育工作者的追求和荣耀。那么&#xff0c;如何才能成为这样的“好老师”呢&#xff1f; 一、热爱教育&#xff0c;关爱学生 成为“好老师”的首要条件是对…
阅读更多...
神经网络（neural network)

神经网络（neural network)

在这一章中我们将进入深度学习算法&#xff0c;学习一些神经网络相关的知识&#xff0c;这些是有更加强大的作用&#xff0c;更加广泛的用途。 神经元和大脑(neurons and the brain): 我们对于我们的编程的进步主要来自我们对于大脑的研究&#xff0c;根据我们对于大脑的研究…
阅读更多...
Vue系列-环境快速搭建

Vue系列-环境快速搭建

vue环境快速搭建 演示视频 快速搭建Vue开发环境pnpm和yarn 1. 基本信息 作者: GMCY系列: Vue仓库: GitHub | Gitee话题(GitHub): tools \ vue创建时间: 2024/03/02 2. 介绍 功能 批处理文件vue 环境的快速搭建nodejs, npm, pnpm, yarn 自动 下载安装npm, pnpm, yarn 自动 …
阅读更多...
网络空间资产安全解决方案

网络空间资产安全解决方案

长期以来&#xff0c;我们一直强调要做好网络安全建设&#xff0c;而其中的第一步就是要做好对自身资产的发现和清点&#xff0c;正如大家经常所说的那句话——“你无法保护你看不见的东西”。的确&#xff0c;如果不知道自己拥有什么资产&#xff0c;那么如何去了解与它们相关…
阅读更多...
最新文章

Copyright @ 2022~2023