37. 解数独 - 力扣(LeetCode)

基础知识要求:

Java: 方法、for循环、if else语句、数组

Python: 方法、for循环、if else语句、列表

题目: 

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 '.' 表示。

示例 1:

输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

提示:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

思路解析:

这个解题思路是一个典型的回溯算法在数独求解问题上的应用,它非常直观且易于理解。下面是对这个解题思路的总结:

  1. 初始化
    • 提供一个初始的数独板(在这个例子中是通过一个二维列表表示的)。
    • 如果数独板没有完全填充(即含有.作为占位符),则需要进行求解。
  2. 定义is_valid函数
    • 这是一个辅助函数,用于检查在给定位置(row, col)填入数字num是否有效。
    • 检查包括:当前行、当前列以及所在的3x3宫格内是否已存在该数字。
  3. 定义solve_sudoku函数
    • 这是求解数独的核心函数,它使用回溯法来尝试填充每一个空格。
    • 对于数独板上的每一个空格(即值为.的位置):
      • 尝试填入数字1到9。
      • 如果填入某个数字后,数独仍然有效(通过is_valid函数检查),则继续递归地求解剩余的空格。
      • 如果递归求解成功(即找到了一个解),则返回True。
      • 如果递归求解失败(即当前数字不合适),则回溯,将该空格重新置为.,并尝试下一个数字。
    • 如果尝试完所有数字后仍然没有找到解,则返回False。
    • 如果所有空格都成功填充,则返回True,表示找到了一个解。
  4. 求解与输出
    • 调用solve_sudoku函数来求解数独。
    • 如果求解成功,则打印出解出的数独板;否则,输出“无解”。

Java代码示例:

public class SudokuSolver {  // 检查数字在行、列和3x3宫格内是否有效  public static boolean isValid(char[][] board, int row, int col, char num) {  // 检查行  for (int i = 0; i < 9; i++) {  if (board[row][i] == num) {  return false;  }  }  // 检查列  for (int i = 0; i < 9; i++) {  if (board[i][col] == num) {  return false;  }  }  // 检查3x3宫格  int startRow = 3 * (row / 3);  int startCol = 3 * (col / 3);  for (int i = 0; i < 3; i++) {  for (int j = 0; j < 3; j++) {  if (board[i + startRow][j + startCol] == num) {  return false;  }  }  }  return true;  }  // 递归求解数独  public static boolean solveSudoku(char[][] board) {  for (int i = 0; i < 9; i++) {  for (int j = 0; j < 9; j++) {  if (board[i][j] == '.') {  for (char num = '1'; num <= '9'; num++) {  if (isValid(board, i, j, num)) {  board[i][j] = num;  // 递归尝试下一个空格  if (solveSudoku(board)) {  return true;  }  // 回溯  board[i][j] = '.';  }  }  // 尝试完所有数字都不可行,说明当前空格无解,返回false  return false;  }  }  }  // 所有空格都填满了,说明找到解了  return true;  }  // 主函数,用于测试  public static void main(String[] args) {  char[][] board = {  {'5', '3', '.', '.', '7', '.', '.', '.', '.'},  {'6', '.', '.', '1', '9', '5', '.', '.', '.'},  {'.', '9', '8', '.', '.', '.', '.', '6', '.'},  {'8', '.', '.', '.', '6', '.', '.', '.', '3'},  {'4', '.', '.', '8', '.', '3', '.', '.', '1'},  {'7', '.', '.', '.', '2', '.', '.', '.', '6'},  {'.', '6', '.', '.', '.', '.', '2', '8', '.'},  {'.', '.', '.', '4', '1', '9', '.', '.', '5'},  {'.', '.', '.', '.', '8', '.', '.', '7', '9'}  };  if (solveSudoku(board)) {  // 格式化输出  for (char[] row : board) {  for (char num : row) {  System.out.print(num + " ");  }  System.out.println();  }  } else {  System.out.println("无解");  }  }  
}

Python代码示例:

def is_valid(board, row, col, num):  # 检查行中是否已存在该数字  for i in range(9):  if board[row][i] == num:  return False  # 检查列中是否已存在该数字  for i in range(9):  if board[i][col] == num:  return False  # 检查3x3宫格中是否已存在该数字  start_row = 3 * (row // 3)  start_col = 3 * (col // 3)  for i in range(3):  for j in range(3):  if board[i + start_row][j + start_col] == num:  return False  return Truedef solve_sudoku(board):  for i in range(9):  for j in range(9):  if board[i][j] == '.':  for num in ['1', '2', '3', '4', '5', '6', '7', '8', '9']:  if is_valid(board, i, j, num):  board[i][j] = num  if solve_sudoku(board):  return True  # 如果当前数字不合法,回溯  board[i][j] = '.'  # 尝试完所有数字都不可行,说明无解  return False  # 所有空格都填满了,说明找到解了  return True  # 示例输入  
board = [["5","3",".",".","7",".",".",".","."],  ["6",".",".","1","9","5",".",".","."],  [".","9","8",".",".",".",".","6","."],  ["8",".",".",".","6",".",".",".","3"],  ["4",".",".","8",".","3",".",".","1"],  ["7",".",".",".","2",".",".",".","6"],  [".","6",".",".",".",".","2","8","."],  [".",".",".","4","1","9",".",".","5"],  [".",".",".",".","8",".",".","7","9"]]  # 转换为二维列表  
board = [list(map(str, row)) for row in board]  # 求解数独  
if solve_sudoku(board):  # 格式化输出  for row in board:  print(row)  
else:  print("无解")

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vs无法打开或包括文件”QTxxx“

vs创建项目时默认引入core、gui、和widgets等模块&#xff0c;在需要网络通讯或者图表等开发时需要添加相应模块。 点击扩展 -> QT VS Tools -> QT Project Setting->Qt Modules&#xff0c;添加相应模块即可

南加州大学字节提出MagicPose,提供逼真的人类视频生成,实现生动的运动和面部表情传输,以及不需要任何微调的一致的野外零镜头生成。

MagicPose可以精确地生成外观一致的结果&#xff0c;而原始的文本到图像模型(如Stable Diffusion和ControlNet)很难准确地保持主体身份信息。 此外&#xff0c;MagicPose模块可以被视为原始文本到图像模型的扩展/插件&#xff0c;而无需修改其预训练的权重。 相关链接 论文链…

【BSP开发经验】简易文件系统digicapfs实现方式

文章目录 背景Linux vfs框架介绍数据结构系统调用openwriteread 总体框架 Linux 磁盘高速缓存机制标准文件访问同步文件访问异步文件访问buffer_head 如何实现一个简单的文件系统blkdevfs注册文件系统产生一个文件让文件变得可读可写 背景 在新的分区升级启动方案中需要分别实…

详解ArcGIS 水文分析模型构建

目录 前言 项目环境、条件 Dem 数据预览 ArcGIS模型构建器 模型搭建 填洼 流向 流量 河流长度 栅格计算器 河流链接 河网分级 栅格河网矢量化 绘制倾泻点 栅格流域提取 集水区 盆域分析 栅格转面 模型应用 导出 py 文件 完善脚本 最终效果 结束语 前言 …

使用python实现socket进行消息传输-demo

Socket 是什么 Socket 是一种在计算机网络中用于实现进程间通信的一种机制。它是网络编程中的重要概念&#xff0c;通过它可以在不同的计算机之间进行数据传输和通信。Socket 可以用于实现各种网络应用&#xff0c;包括客户端-服务器模型、P2P 应用等。基本上&#xff0c;Sock…

Java面向对象-常用类 (包装类)

常用类 – 包装类 基本数据类型的包装类 理解&#xff1a;包装类是8种基本数据类型对应的类 出现原因&#xff1a;Java是一种纯面向对象语言&#xff0c;但是java中有8种基本数据类型&#xff0c;破坏了java为纯面向对象的特征。为了承诺在java中一切皆对象&#xff0c;java…

16. Elasticsearch面试题汇总

Java全栈面试题汇总目录-CSDN博客 1. 什么是Elasticsearch? Elasticsearch是一个基于Lucene的搜索引擎。它提供了具有HTTP Web界面和无架构JSON文档的分布式&#xff0c;多租户能力的全文搜索引擎。 Elasticsearch是用Java开发的&#xff0c;根据Apache许可条款作为开源发布…

安全生产月答题pk小程序怎么做

在当今信息化时代&#xff0c;小程序已成为人们日常生活和工作中不可或缺的一部分。特别是在安全生产领域&#xff0c;通过小程序进行答题PK活动&#xff0c;不仅可以提高员工的安全意识&#xff0c;还能促进团队间的协作与交流。本文将详细介绍如何制作一款安全生产月答题PK小…

物体检测算法-R-CNN,SSD,YOLO

物体检测算法-R-CNN&#xff0c;SSD&#xff0c;YOLO 1 R-CNN2 SSD3 Yolo总结 1 R-CNN R-CNN&#xff08;Region-based Convolutional Neural Network&#xff09;是一种基于区域的卷积神经网络&#xff0c;是第一个成功将深度学习应用到目标检测上的算法。它主要由三个步骤组…

8操作系统定义、分类及功能+设备管理+作业管理 软设刷题 软考+

操作系统定义、分类及功能设备管理作业管理 知识点1-55-1010-1515-2020-2525-3030-35 刷题操作系统定义、分类及功能1-55-1010-15作业管理1-5设备管理1-55-10 知识点 1-5 1 嵌入式操作系统的特点&#xff1a; 1.微型化&#xff0c;从性能和成本角度考虑&#xff0c;希望占用的…

盲人社区生活支持体系:织就一张温暖的网

在当今社会&#xff0c;构建一个全面、包容的盲人社区生活支持体系成为了推动社会进步、保障残障人士权益的重要议题。随着科技的不断革新&#xff0c;一款名为“蝙蝠避障”的辅助软件走进了盲人的日常生活&#xff0c;它如同一位无形的向导&#xff0c;通过实时避障与拍照识别…

关于基础的流量分析(1)

1.对于流量分析基本认识 1&#xff09;简介&#xff1a;网络流量分析是指捕捉网络中流动的数据包&#xff0c;并通过查看包内部数据以及进行相关的协议、流量分析、统计等来发现网络运行过程中出现的问题。 2&#xff09;在我们平时的考核和CTF比赛中&#xff0c;基本每次都有…

线程的概念和控制

文章目录 线程概念线程的优点线程的缺点线程异常线程用途理解虚拟地址 线程控制线程的创建线程终止线程等待线程分离封装线程库 线程概念 什么是线程&#xff1f; 在一个程序里的一个执行路线就叫做线程&#xff08;thread&#xff09;。更准确的定义是&#xff1a;线程是“一…

VMware虚拟机安装Windows server 2022超详细教程

文章目录 ISO下载安装步骤总结 ISO下载 链接&#xff1a;https://pan.baidu.com/s/19Z2q9KFKZq0pLisPZLn7_g 提取码&#xff1a;3pgn 安装步骤 安装完打开虚拟机后发现引导程序无法正常执行 解决方法见我的上一篇文章&#xff1a;http://t.csdnimg.cn/PzfOz 问题解决完后正常…

计算机毕业设计 | node.js(Express)+vue影院售票商城 电影放映购物系统(附源码+论文)

1&#xff0c;绪论 1.1 项目背景 最近几年&#xff0c;我国影院企业发展迅猛&#xff0c;各大电影院不断建设新的院线&#xff0c;每年新投入使用的荧幕数目逐年显著上升。这离不开人们的观影需求及对观影的过程要求的不断进步。广大观影消费者需要知道自己的空闲时间&#x…

P1【知识点】【数据结构】【链表LinkedList】C++版

链表是一种逻辑上连续&#xff0c;内存上分散的线性表数据结构&#xff0c;是用一组任意的空间&#xff08;可以连续&#xff0c;也可以不连续&#xff09;来存放数据元素。每个数据元素成为一个”结点“&#xff0c;每个结点由数据域和指针域组成。 访问元素&#xff08;Acce…

保护共享资源的方法(互斥锁)

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…

工厂模式(简单工厂模式+工厂模式)

工厂模式的目的就是将对象的创建过程隐藏起来&#xff0c;从而达到很高的灵活性&#xff0c;工厂模式分为三类&#xff1a; 简单工厂模式工厂方法模式抽象工厂模式 在没有工厂模式的时候就是&#xff0c;客户需要一辆马车&#xff0c;需要客户亲自去创建一辆马车&#xff0c;…

向上调整建堆与向下调整建堆的时间复杂度 AND TopK问题

目录 前言建堆的时间复杂度TOPK问题总结 前言 本篇旨在介绍使用向上调整建堆与向下调整建堆的时间复杂度. 以及topk问题 博客主页: 酷酷学!!! 感谢关注~ 建堆的时间复杂度 堆排序是一种优于冒泡排序的算法, 那么在进行堆排序之前, 我们需要先创建堆, 为什么说堆排序的是优于…

2023年数维杯国际大学生数学建模挑战赛D题洗衣房清洁计算解题全过程论文及程序

2023年数维杯国际大学生数学建模挑战赛 D题 洗衣房清洁计算 原题再现&#xff1a; 洗衣房清洁是人们每天都要做的事情。洗衣粉的去污作用来源于一些表面活性剂。它们可以增加水的渗透性&#xff0c;并利用分子间静电排斥机制去除污垢颗粒。由于表面活性剂分子的存在&#xff…