ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 2506|回复: 25

[讨论] Microsoft 365:关于函数公式解数独的探讨

[复制链接]

TA的精华主题

TA的得分主题

发表于 2023-9-21 08:55 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:LAMBDA
本帖最后由 shaowu459 于 2023-10-11 12:26 编辑

本帖只是初步解决了出正确结果的问题(有些复杂的解不出来),效率比起编程语言差的多。一楼已更新最新的文件,循环有两个公式,递归有一个公式,对同一个题目来说这三个公式解决速度有很大差异,主要和已知数情况及数据分布有关系。

本帖所称数独是指如下的标准数独(九宫格):
1)数独大小为9×9,共81个格子;
2)数独分九宫,每宫大小均为3×3,各9个格子;
3)每个格子只能填入1~9的数字,并且每行、每列、每一宫(不包括两条主对角线)中1~9的数字都只出现一次。

图片.png
图片.png

Sudoku-循环(优化).rar

57.62 KB, 下载次数: 49

Sudoku-递归(优化).rar

64.79 KB, 下载次数: 42

评分

11

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 09:08 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 shaowu459 于 2023-9-21 09:09 编辑

第一种方法:循环穷举。


初始数据存储在9×9的单元格区域中,后续运算的中间过程相关只能保存在数组中。因为涉及行、列、九宫的判断,因此我们需要在9×9的区域中提取当前数字所在行、列和当前九宫的数据来判断和运算。提取行、列都比较方便,只需要判断当前数据所在的行数或列数,然后用INDEX函数即可提取,但提取当前数据在9×9数组中所在的九宫数据就稍微麻烦一些。为了方便后续处理,我们可以将9×9数据转化为一列来运算。

图片.png

首先,使用TOCOL函数将数独区域转化为81行一列的数组。这样,第1~9个数据是第一行,第10~18个数据是第二行,第19~27个数据是第三行,以此类推。
图片.png
有了上面分析的规律,提取第n行就比较方便了。使用下面的公式可以生成9个1、9个2、9个3……的序列,要获取第n行,只需要筛选即可:
FILTER(81行的数组,INT((ROW(1:81)-1)/9)+1=n)
  1. =INT((ROW(1:81)-1)/9)+1
复制代码
图片.png

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 09:14 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
本帖最后由 shaowu459 于 2023-9-21 11:48 编辑

同样的,通过观察,第1、10、19……个数字是第1列,第2、11、20……个数字是第2列。使用以下公式生成1~9的循环,提取第n列的数据筛选即可:
FILTER(81行的数组,MOD(ROW(1:81)-1,9)+1=n)
  1. =MOD(ROW(1:81)-1,9)+1
复制代码
图片.png

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 09:17 | 显示全部楼层
本帖最后由 shaowu459 于 2023-9-21 11:47 编辑

同样思路,使用下面的公式生成一个有规律的序列,使用筛选的方法可以获得第n个九宫的数据:
FILTER(81行的数组,下面公式生成的数组=n)
  1. =INT(MOD(ROW(1:81)-1,9)/3)+1+3*INT((ROW(1:81)-1)/27)
复制代码
图片.png


TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 09:30 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 shaowu459 于 2023-11-3 15:37 编辑

因为要判断当前要填数字(也就是0所在的位置)所在的行、列和九宫中已有数字是否重复,所以,首先要获得当前行、列和九宫的数字。以C2单元格为例,C2所在的行、列和九宫数据可以使用以下公式获得(可以不适用UNIQUE函数,使用该函数主要是为了保证截图能截全):
  1. =UNIQUE(VSTACK(C2:C10,TOCOL(B2:J2),TOCOL(B2:D4)))      VSTACK函数第一参数截图中笔误为B2:B10
复制代码
图片.png
上图中的N2:N8单元格区域数据就是C2所在行、列和九宫中的已有数据。公式中的各部分提取方法在前面楼层已有介绍,不再赘述。

在这种情况下,C2单元格的备选数据就是1~9扣除N2:N8之间已出现过的数据。例如可以使用MATCH、TOCOL(实际应用时直接使用TOROW函数)等函数获得:
  1. =TOCOL(ROW(1:9)/ISNA(MATCH(ROW(1:9),N2#,)),3)
复制代码
图片.png

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 09:43 | 显示全部楼层
上一层使用公式获得了C2单元格的备选数字4、6、8,那么如何将这3个备选数字填入原来的数组呢?

为了方便说明,在L列仅列示数独转成81行一列数组的前9个元素,也就是B2:J2这第一行的数据,其中棕色单元格代表C2单元格,0代表当前单个没有数据。为了插入备选数据,把上一步获得的4、6、8备选数据使用TOROW函数转成列:
图片.png

因为第一列里有若干个0,所以先使用MATCH函数确定第一个0,也就是C2单元格在数组中的位置:
图片.png

然后使用IF函数将4、6、8替代数组中位置2的0:
  1. =IF(ROW(1:9)=MATCH(0,L2:L10,),N3:P3,L2:L10)
复制代码
图片.png

上面公式中的ROW(1:9)在实际公式中是ROW(1:81),N3:P3的备选数字是上个步骤生成的一行数组,L2:L10是当前数独的状态,下一步需要将第1个0(也就是第一个未填入数字)的位置填充上可以填入的备选数。

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 09:53 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
有了上面所有的基础分析,我们可以得到以下通过循环来解数独的一种思路:
1)将数独的数据转化为一列(TOCOL函数转换);
2)循环n次,n=81-数独已有数据个数。每循环一次,将某个位置的备选数字填入对应位置,有几个备选数整个数独的列就会被扩展成几列;
3)每次循环时,从上到下确认第1个0所在的位置(也即第一个未填入数据的位置),提取该位置所在行、列、九宫的数据(前面已介绍公式提取方法);
4)判断1~9是否在当前行、列、九宫中出现,找到未出现的,生成备选数数组;
5)使用IF函数将备选数填入数独列的第一个0的位置并扩充数独列,每一列是一种可能。
6)再次循环,将已生成的多种可能得数独列每列按照上述方式循环,填充下一个0的位置。
7)循环完毕后,可能生成多组符合条件的结果,使用公式提取第一列结果,然后使用WRAPROWS函数按9个一行折叠,返回结果数组。

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 10:09 | 显示全部楼层
本帖最后由 shaowu459 于 2023-9-21 13:11 编辑

上述思路下完整的参考公式如下,大家有更高效率的循环方法也请不吝赐教(公式已更新):
  1. =LET(行,LAMBDA(x,INT((x-1)/9)+1),列,LAMBDA(x,MOD(x-1,9)+1),九宫,LAMBDA(x,INT(MOD(x-1,9)/3)+1+3*INT((x-1)/27)),结果,REDUCE(TOCOL(--B2:J10),SEQUENCE(81-COUNT(B2:J10)),LAMBDA(x,y,DROP(REDUCE(0,SEQUENCE(COLUMNS(x)),LAMBDA(m,n,LET(每一列,INDEX(x,,n),筛,LAMBDA(x,y,FILTER(每一列,x=y)),位置,MATCH(0,每一列,),行判,筛(行(ROW(1:81)),行(位置)),列判,筛(列(ROW(1:81)),列(位置)),九宫判,筛(九宫(ROW(1:81)),九宫(位置)),备选,TOROW(ROW(1:9)/ISNA(MATCH(ROW(1:9),VSTACK(行判,列判,九宫判),)),3),IF(COUNT(备选)=0,m,HSTACK(m,IF(ISNA(位置),每一列,IF(ROW(1:81)=位置,备选,每一列))))))),,1))),WRAPROWS(TAKE(FILTER(结果,BYCOL(结果,LAMBDA(x,NOT(OR(x=0))))),,1),9))
复制代码

图片.jpg

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 10:13 | 显示全部楼层
本帖最后由 shaowu459 于 2023-9-21 10:14 编辑

由于字符数量超过限制,只能发截图:
]2H5H8L[F}NGMSVH{RYBR0Q.jpg



TA的精华主题

TA的得分主题

 楼主| 发表于 2023-9-21 10:25 | 显示全部楼层
本帖最后由 shaowu459 于 2023-9-22 17:19 编辑

递归公式的方法和循环的公式基本一致,首先定义fx:
  1. =LAMBDA(z,LET(行,LAMBDA(x,INT((x-1)/9)+1),列,LAMBDA(x,MOD(x-1,9)+1),九宫,LAMBDA(x,INT(MOD(x-1,9)/3)+1+3*INT((x-1)/27)),筛,LAMBDA(x,y,FILTER(z,x=y)),位置,MATCH(0,z,),行判,筛(行(ROW(递归!$1:$81)),行(位置)),列判,筛(列(ROW(递归!$1:$81)),列(位置)),九宫判,筛(九宫(ROW(递归!$1:$81)),九宫(位置)),备选,TOCOL(ROW(递归!$1:$9)/ISNA(MATCH(ROW(递归!$1:$9),VSTACK(行判,列判,九宫判),)),3),IF(ISNA(位置)+(COUNT(备选)=0),z,DROP(REDUCE(0,备选,LAMBDA(m,n,HSTACK(m,fx(IF(ROW(递归!$1:$81)=位置,n,z))))),,1))))
复制代码
然后在空单元格中输入以下公式:
  1. =LET(s,fx(TOCOL(--B2:J10)),WRAPROWS(TAKE(FILTER(s,BYCOL(s,LAMBDA(x,NOT(OR(x=0))))),,1),9))
复制代码
图片.jpg

公式核心思路是:
在当前位置循环备选数,将每个备选数填入数独列第一个0的位置,生成新的数独列后在此进入fx循环判断。由于递归在Excel中使用的限制,只能解决20个空的问题,仅供参考。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-6-19 08:25 , Processed in 0.049000 second(s), 12 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表