Microsoft 365：关于函数公式解数独的探讨

shaowu459

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

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

shaowu459

第一种方法：循环穷举。


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



首先，使用TOCOL函数将数独区域转化为81行一列的数组。这样，第1~9个数据是第一行，第10~18个数据是第二行，第19~27个数据是第三行，以此类推。

有了上面分析的规律，提取第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

复制代码

shaowu459

同样的，通过观察，第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

复制代码

shaowu459

同样思路，使用下面的公式生成一个有规律的序列，使用筛选的方法可以获得第n个九宫的数据：
FILTER(81行的数组,下面公式生成的数组=n)

1. =INT(MOD(ROW(1:81)-1,9)/3)+1+3*INT((ROW(1:81)-1)/27)

复制代码

shaowu459

因为要判断当前要填数字（也就是0所在的位置）所在的行、列和九宫中已有数字是否重复，所以，首先要获得当前行、列和九宫的数字。以C2单元格为例，C2所在的行、列和九宫数据可以使用以下公式获得（可以不适用UNIQUE函数，使用该函数主要是为了保证截图能截全）：

1. =UNIQUE(VSTACK(C2:C10,TOCOL(B2:J2),TOCOL(B2:D4)))      VSTACK函数第一参数截图中笔误为B2:B10
   

复制代码

上图中的N2:N8单元格区域数据就是C2所在行、列和九宫中的已有数据。公式中的各部分提取方法在前面楼层已有介绍，不再赘述。

在这种情况下，C2单元格的备选数据就是1~9扣除N2:N8之间已出现过的数据。例如可以使用MATCH、TOCOL（实际应用时直接使用TOROW函数）等函数获得：

1. =TOCOL(ROW(1:9)/ISNA(MATCH(ROW(1:9),N2#,)),3)

复制代码

shaowu459

上一层使用公式获得了C2单元格的备选数字4、6、8，那么如何将这3个备选数字填入原来的数组呢？

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


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


然后使用IF函数将4、6、8替代数组中位置2的0：

1. =IF(ROW(1:9)=MATCH(0,L2:L10,),N3:P3,L2:L10)

复制代码

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

shaowu459

有了上面所有的基础分析，我们可以得到以下通过循环来解数独的一种思路：
1）将数独的数据转化为一列（TOCOL函数转换）；
2）循环n次，n=81-数独已有数据个数。每循环一次，将某个位置的备选数字填入对应位置，有几个备选数整个数独的列就会被扩展成几列；
3）每次循环时，从上到下确认第1个0所在的位置（也即第一个未填入数据的位置），提取该位置所在行、列、九宫的数据（前面已介绍公式提取方法）；
4）判断1~9是否在当前行、列、九宫中出现，找到未出现的，生成备选数数组；
5）使用IF函数将备选数填入数独列的第一个0的位置并扩充数独列，每一列是一种可能。
6）再次循环，将已生成的多种可能得数独列每列按照上述方式循环，填充下一个0的位置。
7）循环完毕后，可能生成多组符合条件的结果，使用公式提取第一列结果，然后使用WRAPROWS函数按9个一行折叠，返回结果数组。

shaowu459

上述思路下完整的参考公式如下，大家有更高效率的循环方法也请不吝赐教（公式已更新）：

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))

复制代码

shaowu459

由于字符数量超过限制，只能发截图：

shaowu459

递归公式的方法和循环的公式基本一致，首先定义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))

复制代码

公式核心思路是：
在当前位置循环备选数，将每个备选数填入数独列第一个0的位置，生成新的数独列后在此进入fx循环判断。由于递归在Excel中使用的限制，只能解决20个空的问题，仅供参考。