写个程序玩数独

2024-06-23 20:08
文章标签 程序 玩数 写个

本文主要是介绍写个程序玩数独,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

由于不可抗力的因素,导致今年(2020)的假期格外的长,毕竟还只能蜗居度过。在家里消磨时光有很多方法,比如说看剧,看书,玩游戏等。

说到玩游戏,我就想到了我初中时候看杂志时,里面会有一类题目,叫做数独。

2013053-b3c1c45feabeaf61.png
数独游戏

数独游戏的目标是用数字填充9x9的宫格,让每一列,每一行和每个3x3小九宫部分都包含1到9之间的数字。在游戏开始时,9x9的宫格中会有一些方格已填上数字。你要做的是运用逻辑来填上缺失的数字并完成宫格。不要忘记,如果出现以下情况,表示填法不正确

  • 任意一行中,有多个相同的1到9中的数字
  • 任意一列中,有多个相同的1到9中的数字
  • 任意一个3x3小宫格中,有多个相同的1到9中的数

那个时候,拿着铅笔和橡皮擦玩,一个谜题能把一个晚自修给干掉。

最近在家学习算法,学到了回溯算法这一部分,里面就提到了回溯算法的使用范围为,在一组可能的解中,搜索满足期望的解。课程介绍了回溯算法处理八皇后问题,把数独问题留作了练习题。我就用C语言写了相应的代码。

代码的核心是写一个递归函数,用于分步求解当前值是否满足要求,如果满足需求就进入下一阶段,如果下一个阶段在前一阶段基础上无解,就会回到上一阶段,换另一个值进行尝试。

按照这个思想我写了第一版代码

 void
calcSudoku( int (*arr)[9], int (*arr2)[9], int pos, int value ){if ( pos == 81){printSudoku(arr);return ;}int row = pos / 9;int col = pos % 9;int val;for ( val = 1; val < 10; val++){// 如果为0, 说明此处可以进行修改if ( arr2[row][col] == 0 ){if ( isValidStep(arr, row, col, val ) ){arr[row][col] = val;calcSudoku( arr, arr2, pos + 1, val );}} else{// 当前记录如果不为0, 说明此处是已填写区域// 跳过这个地方calcSudoku( arr, arr2, pos + 1, val );}}
}   for ( val = 1; val < 10; val++){// 如果为0, 说明此处可以进行修改if ( arr2[row][col] == 0 ){if ( isValidStep(arr, row, col, val ) ){arr[row][col] = val;calcSudoku( arr, arr2, pos + 1, val );printSudoku(arr);}} else{// 当前记录如果不为0, 说明此处是已填写区域// 跳过这个地方calcSudoku( arr, arr2, pos + 1, val );}}

结果代码会陷入一个死循环。我在代码中各种加printf来想办法找到可能的问题,然后还和之前的八皇后问题进行了比较,最终和别人的java代码做了比较之后,才发现代码的问题

  1. 原本是提供arr2作为原来数组的拷贝,用于记录哪里为0,想避免修改原来为不为0的地方, 但对于正确的回溯代码,递归记录了路径,因此在回溯的过程中,可以重设原来的状态。
  2. 判断当前值是否为0,应该是在for循环之外,可以避免不必要的计算
  3. 缺少重设原来状态的代码,导致回退之后,还是之前的状态。

经过我的修改,下面的代码才是真正能用的

void
calcSudoku( int (*metrics)[9],  int pos, int value ){if ( pos == 81 ){printSudoku(metrics);return ;}int row = pos / 9;int col = pos % 9;int val;// 如果为0, 说明此处可以进行修改if ( metrics[row][col] == 0 ){for ( val = 1; val < 10; val++){if ( isValidStep(metrics, row, col, val ) ){ // 如果能够设置当前值metrics[row][col] = val;calcSudoku( metrics, pos + 1, val ); // 前进到下一步}//从下一状态回退到当前值时,则重设当前值metrics[row][col] = 0; }} else{// 当前记录如果不为0, 说明此处是已填写区域// 跳过这个地方calcSudoku( metrics, pos + 1, val );}
}

最终版代码在GitHub上, https://github.com/xuzhougeng/learn-algo/blob/master/sudoku.c

使用方法,把之前的问题输入到一个文本中,以空格作为分隔符

0 0 9 4 2 0 0 6 0
0 7 0 9 0 5 3 0 2
5 0 0 0 0 3 0 9 0
0 0 0 8 0 1 0 2 0
2 6 0 0 0 0 0 5 1
0 1 8 2 0 0 4 0 0
3 8 0 0 0 4 0 1 9
0 9 4 0 3 0 6 8 5
0 2 1 0 0 8 0 3 0

然后运行代码,就会得到答案。

$ ./sudoku q.txt
0 0 9 4 2 0 0 6 0
0 7 0 9 0 5 3 0 2
5 0 0 0 0 3 0 9 0
0 0 0 8 0 1 0 2 0
2 6 0 0 0 0 0 5 1
0 1 8 2 0 0 4 0 0
3 8 0 0 0 4 0 1 9
0 9 4 0 3 0 6 8 5
0 2 1 0 0 8 0 3 01 3 9 4 2 7 5 6 8
8 7 6 9 1 5 3 4 2
5 4 2 6 8 3 1 9 7
4 5 3 8 7 1 9 2 6
2 6 7 3 4 9 8 5 1
9 1 8 2 5 6 4 7 3
3 8 5 7 6 4 2 1 9
7 9 4 1 3 2 6 8 5
6 2 1 5 9 8 7 3 4

这篇关于写个程序玩数独的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1088147

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

EMLOG程序单页友链和标签增加美化

单页友联效果图: 标签页面效果图: 源码介绍 EMLOG单页友情链接和TAG标签,友链单页文件代码main{width: 58%;是设置宽度 自己把设置成与您的网站宽度一样,如果自适应就填写100%,TAG文件不用修改 安装方法:把Links.php和tag.php上传到网站根目录即可,访问 域名/Links.php、域名/tag.php 所有模板适用,代码就不粘贴出来,已经打

跨系统环境下LabVIEW程序稳定运行

在LabVIEW开发中,不同电脑的配置和操作系统(如Win11与Win7)可能对程序的稳定运行产生影响。为了确保程序在不同平台上都能正常且稳定运行,需要从兼容性、驱动、以及性能优化等多个方面入手。本文将详细介绍如何在不同系统环境下,使LabVIEW开发的程序保持稳定运行的有效策略。 LabVIEW版本兼容性 LabVIEW各版本对不同操作系统的支持存在差异。因此,在开发程序时,尽量使用

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

这些心智程序你安装了吗?

原文题目:《为什么聪明人也会做蠢事(四)》 心智程序 大脑有两个特征导致人类不够理性,一个是处理信息方面的缺陷,一个是心智程序出了问题。前者可以称为“认知吝啬鬼”,前几篇文章已经讨论了。本期主要讲心智程序这个方面。 心智程序这一概念由哈佛大学认知科学家大卫•帕金斯提出,指个体可以从记忆中提取出的规则、知识、程序和策略,以辅助我们决策判断和解决问题。如果把人脑比喻成计算机,那心智程序就是人脑的

uniapp设置微信小程序的交互反馈

链接:uni.showToast(OBJECT) | uni-app官网 (dcloud.net.cn) 设置操作成功的弹窗: title是我们弹窗提示的文字 showToast是我们在加载的时候进入就会弹出的提示。 2.设置失败的提示窗口和标签 icon:'error'是设置我们失败的logo 设置的文字上限是7个文字,如果需要设置的提示文字过长就需要设置icon并给

基于SpringBoot的宠物服务系统+uniapp小程序+LW参考示例

系列文章目录 1.基于SSM的洗衣房管理系统+原生微信小程序+LW参考示例 2.基于SpringBoot的宠物摄影网站管理系统+LW参考示例 3.基于SpringBoot+Vue的企业人事管理系统+LW参考示例 4.基于SSM的高校实验室管理系统+LW参考示例 5.基于SpringBoot的二手数码回收系统+原生微信小程序+LW参考示例 6.基于SSM的民宿预订管理系统+LW参考示例 7.基于

Spring Roo 实站( 一 )部署安装 第一个示例程序

转自:http://blog.csdn.net/jun55xiu/article/details/9380213 一:安装 注:可以参与官网spring-roo: static.springsource.org/spring-roo/reference/html/intro.html#intro-exploring-sampleROO_OPTS http://stati

未来工作趋势:零工小程序在共享经济中的作用

经济在不断发展的同时,科技也在飞速发展。零工经济作为一种新兴的工作模式,正在全球范围内迅速崛起。特别是在中国,随着数字经济的蓬勃发展和共享经济模式的深入推广,零工小程序在促进就业、提升资源利用效率方面显示出了巨大的潜力和价值。 一、零工经济的定义及现状 零工经济是指通过临时性、自由职业或项目制的工作形式,利用互联网平台快速匹配供需双方的新型经济模式。这种模式打破了传统全职工作的界限,为劳动

Java程序到CPU上执行 的步骤

相信很多的小伙伴在最初学习编程的时候会容易产生一个疑惑❓,那就是编写的Java代码究竟是怎么一步一步到CPU上去执行的呢?CPU又是如何执行的呢?今天跟随小编的脚步去化解开这个疑惑❓。 在学习这个过程之前,我们需要先讲解一些与本内容相关的知识点 指令 指令是指导CPU运行的命令,主要由操作码+被操作数组成。 其中操作码用来表示要做什么动作,被操作数是本条指令要操作的数据,可能是内存地址,也