当前位置: 首页 > news >正文

回溯算法---数独问题

回溯算法理论基础

回溯和递归密不可分,有回溯就有递归,所谓回溯就是基于一个叉树,可能是二叉树或者是三叉树,从root节点开始深度优先搜索遍历节点,当遍历到一个子节点时,回溯到上一个根节点选择另外一个子节点继续进行遍历,就叫做回溯。
回溯算法的标准解题模板:viod backTracking(参数){
结束条件
处理逻辑
递归
回溯
}

PTA数独游戏

在这里插入图片描述
输入格式:
The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

注意: 本题输入数据量较大,cin, getline可能会超时,建议使用scanf。

输出格式:
For each test case, print a line representing the completed Sudoku puzzle.

输入样例:
在这里给出一组输入。例如:

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例:
在这里给出相应的输出。例如:

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936
#include<bits/stdc++.h>
using namespace std;vector<vector<char>> board(9,vector<char>(9));
bool isValid(int row, int col, char val, vector<vector<char>>& board) {for (int i = 0; i < 9; i++) { // 判断行里是否重复if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判断列里是否重复if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true;
}
bool backtracking(vector<vector<char>>& board) {for (size_t i = 0; i < board.size(); i++) {        // 遍历行for (size_t j = 0; j < board[0].size(); j++) { // 遍历列if (board[i][j] != '.') continue;for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) { board[i][j] = k;                // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] = '.';              // 回溯,撤销k}}return false;                           // 9个数都试完了,都不行,那么就返回false}}return true; // 遍历完没有返回false,说明找到了合适棋盘位置了
}int main(){bool judge=true;while(judge){for(int i=0;i<9;i++){for(int j=0;j<9;j++){char c;scanf("%c",&c);if(c=='e'){judge=false;return 0;}board[i][j]=c;}}if(backtracking(board)){for(int i=0;i<9;i++){for(int j=0;j<9;j++){printf("%c",board[i][j]);}}cout<<'\n';}char c;scanf("%c",&c);}
}

我们使用回溯法来解决这个问题,会有一个十叉树,如果数独表这个地方是空格,会尝试十个数字0~9,如果十个数字都不符合,则返回false,如果有符合的数字,则将board[i][j]改为这个数字,进行递归,如果递归函数的结果是true,则返回true。如果递归函数的结果是false,则回溯,就是将board[i][j]重新置空。

在backTracking函数中,为什么没有开头的结束条件呢。因为我们只需要有一条通路,填满这个九宫格就可以。如果我们需要每个通路的内容,则需要有结束条件来记录每个通路。同时我们的backTracking函数的返回值为bool,这是一个判断条件,在递归时代表

相关文章:

回溯算法---数独问题

回溯算法理论基础 回溯和递归密不可分&#xff0c;有回溯就有递归&#xff0c;所谓回溯就是基于一个叉树&#xff0c;可能是二叉树或者是三叉树&#xff0c;从root节点开始深度优先搜索遍历节点&#xff0c;当遍历到一个子节点时&#xff0c;回溯到上一个根节点选择另外一个子…...

蓝桥杯python基础算法(2-1)——排序

目录 一、排序 二、例题 P3225——宝藏排序Ⅰ 三、各种排序比较 四、例题 P3226——宝藏排序Ⅱ 一、排序 &#xff08;一&#xff09;冒泡排序 基本思想&#xff1a;比较相邻的元素&#xff0c;如果顺序错误就把它们交换过来。 &#xff08;二&#xff09;选择排序 基本思想…...

【课程笔记】信息隐藏与数字水印

文章总览:YuanDaiMa2048博客文章总览 【课程笔记】信息隐藏与数字水印 信号处理基础知识隐写系统隐写算法性能指标音频信号处理基础数字音频概念人类听觉系统与语音质量评价信息隐藏的原理数字指纹与版权保护盲水印与非盲水印私钥水印与公钥水印信息隐藏的研究层次信息隐藏与数…...

Page Assist实现deepseek离线部署的在线搜索功能

前面文章Mac 基于Ollama 本地部署DeepSeek离线模型 实现了deepseek的离线部署&#xff0c;但是部署完成虽然可以进行问答和交互&#xff0c;也有thinking过程&#xff0c;但是没办法像官方一样进行联网搜索。今天我们介绍一款浏览器插件Page Assist来实现联网搜索&#xff0c;完…...

composeUI中Box 和 Surface的区别

在 Jetpack Compose 中&#xff0c;Box 和 Surface 都是常用的布局组件&#xff0c;但它们的用途和功能有所不同。 Box 组件&#xff1a; 功能&#xff1a;Box 是一个用于将子组件堆叠在一起的布局容器&#xff0c;类似于传统 Android 中的 FrameLayout。用途&#xff1a;适用…...

【LeetCode】5. 贪心算法:买卖股票时机

太久没更了&#xff0c;抽空学习下。 看一道简单题。 class Solution:def maxProfit(self, prices: List[int]) -> int:cost -1profit 0for i in prices:if cost -1:cost icontinueprofit_ i - costif profit_ > profit:profit profit_if cost > i:cost iret…...

MySQL表的CURD

目录 一、Create 1.1单行数据全列插入 1.2多行数据指定列插入 1.3插入否则更新 1.4替换 2.Retrieve 2.1 select列 2.1.1全列查询 2.1.2指定列查询 2.1.3查询字段为表达式 2.1.4为查询结果指定别名 2.1.5结果去重 2.2where条件 2.3结果排序 2.4筛选分页结果 三…...

Java 如何覆盖第三方 jar 包中的类

目录 一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理 背景&#xff1a; 在我们日常的开发中&#xff0c;经常需要使用第三方的 jar 包&#xff0c;有时候我们会发现第三方的 jar 包中的某一个类有问题&#xff0c;或者我们需要定制化修改其中的逻辑&#xff0c…...

VSCode中使用EmmyLua插件对Unity的tolua断点调试

一.VSCode中搜索安装EmmyLua插件 二.创建和编辑launch.json文件 初始的launch.json是这样的 手动编辑加上一段内容如下图所示&#xff1a; 三.启动调试模式&#xff0c;并选择附加的进程...

【数据结构】_链表经典算法OJ(力扣/牛客第二弹)

目录 1. 题目1&#xff1a;返回倒数第k个节点 1.1 题目链接及描述 1.2 解题思路 1.3 程序 2. 题目2&#xff1a;链表的回文结构 2.1 题目链接及描述 2.2 解题思路 2.3 程序 1. 题目1&#xff1a;返回倒数第k个节点 1.1 题目链接及描述 题目链接&#xff1a; 面试题 …...

Spring Boot 2 快速教程:WebFlux优缺点及性能分析(四)

WebFlux优缺点 【来源DeepSeek】 Spring WebFlux 是 Spring 框架提供的响应式编程模型&#xff0c;旨在支持非阻塞、异步和高并发的应用场景。其优缺点如下&#xff1a; 优点 高并发与低资源消耗 非阻塞 I/O&#xff1a;基于事件循环模型&#xff08;如 Netty&#xff09;&am…...

自定义多功能输入对话框:基于 Qt 打造灵活交互界面

一、引言 在使用 Qt 进行应用程序开发时&#xff0c;我们经常需要与用户进行交互&#xff0c;获取他们输入的各种信息。QInputDialog 是 Qt 提供的一个便捷工具&#xff0c;可用于简单的输入场景&#xff0c;但当需求变得复杂&#xff0c;需要支持更多类型的输入控件&#xff0…...

基于springboot河南省旅游管理系统

基于Spring Boot的河南省旅游管理系统是一种专为河南省旅游行业设计的信息管理系统&#xff0c;旨在整合和管理河南省的旅游资源信息&#xff0c;为游客提供准确、全面的旅游攻略和服务。以下是对该系统的详细介绍&#xff1a; 一、系统背景与意义 河南省作为中国的中部省份&…...

LabVIEW图像采集与应变场测量系统

开发了一种基于LabVIEW的图像采集与应变场测量系统&#xff0c;提供一种高精度、非接触式的测量技术&#xff0c;用于监测物体的全场位移和应变。系统整合了实时监控、数据记录和自动对焦等功能&#xff0c;适用于工程应用和科学研究。 项目背景 传统的位移和应变测量技术往往…...

CommonAPI学习笔记-2

一. 概述 ​ 这篇文章主要是想整理并且分析CommonAPI代码生成工具根据fidl和fdepl配置文件生成出来的代码的结构和作用。 二. fidl ​ 用户根据业务需求在fidl文件中定义业务服务接口的结构以及自定义数据类型&#xff0c;然后使用core生成工具传入fidl文件生成该fidl的核心…...

ISP代理与住宅代理的区别

代理充当用户和互联网之间的中介&#xff0c;在增强安全性、隐私和可访问性方面提供多种功能。在众多代理类型中&#xff0c;ISP和住宅代理脱颖而出&#xff0c;各自拥有不同的功能和应用程序。 一、ISP代理 ISP代理&#xff0c;俗称Internet服务提供商代理&#xff0c;通过其…...

[25] cuda 应用之 nppi 实现图像色彩调整

[25] cuda 应用之 nppi 实现图像色彩调整 在 NPPI(NVIDIA Performance Primitives)中,图像色彩调整通常包括以下几种操作: 亮度调整:增加或减少图像的亮度。对比度调整:增强或减弱图像的对比度。饱和度调整:增强或减弱图像的颜色饱和度。色调调整:改变图像的色调(通常…...

Java 大视界 -- Java 大数据在智慧文旅中的应用与体验优化(74)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

PyTorch快速入门

Anaconda Anaconda 是一款面向科学计算的开源 Python 发行版本&#xff0c;它集成了众多科学计算所需的库、工具和环境管理系统&#xff0c;旨在简化包管理和部署&#xff0c;提升开发与研究效率。 核心组件&#xff1a; Conda&#xff1a;这是 Anaconda 自带的包和环境管理…...

100.7 AI量化面试题:如何利用新闻文本数据构建交易信号?

目录 0. 承前1. 解题思路1.1 数据处理维度1.2 分析模型维度1.3 信号构建维度 2. 新闻数据获取与预处理2.1 数据获取接口2.2 文本预处理 3. 情感分析与事件抽取3.1 情感分析模型3.2 事件抽取 4. 信号生成与优化4.1 信号构建4.2 信号优化 5. 策略实现与回测5.1 策略实现 6. 回答话…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...