芬兰数学家因卡拉花费 3 个月时间设计出的一道数独题,网传是迄今世界上最难的数独题,但据专业机构评估,该题的难度系数实际上只排世界第三。
曾经有个农村老大爷宣称用三天时间解出来了,但说题目需要改一个数字,有点搞笑!重庆有个老教授攻克这道难题,花了 15 天时间。
事实上,数独题的求解讲究方法和步骤,需要经过专业系统的培训,不能单凭兴趣爱好。凭个人兴趣爱好一辈子蒙不出答案的难题,对于受过系统培训的专家,也就数小时的事。本人借助 EXCEL 电子表格工具,解出此题只用了不足两个半小时。
当然,两个半小时出结果,有运气的成份。类似这类需要假设多个已知数反推的世界性数独难题,解题时间具有很大的随机性。运气好时碰巧一次性全部已知数假设都蒙对,分析完第一个表格十几分钟就出结果;运气不好时可能需要逐个分析 2 的 N 次方多个表格,直到分析完最后一个表格才出结果,用时数小时甚至数天。
按最初设计的解题方案,本题总共需要逐个分析 4 组已知数假设系列的 2 的 N 次方多个表格,但在做完第 1 组已知数假设系列最后一级假设 8 个表格中的第 6 个后,就出现正确结果。
解题过程
第 1 步:直接推算。采用数独各种常规推算方法直接推算,结果如下图 1 上中表:只得出 6 对二单元格居一的候选数和一个只能出现在特定宫特定行的候选数。二单元格居一的候选数包括:上中宫和中右宫各一对“5”;上左宫一对 “9”;中左宫一对 “7” 和一对 “8”;下中宫一对“1”。只能出现在特定宫特定行的候选数只有下中宫的三个“8”。对于世界级数独难题而言,这种情况再正常不过。
第 2 步:各单元格候选数列举和分析整理。结果如下图 1 上右表。除了新出现下右宫一对二单元格居一的候选数“9”,其他仍一无所获。
第 3 步:假设已知数反推。选题中出现次数最多,且二单元格居一出现次数最多的数字“5”。先选中右宫的一对“5”,依次假定 G6=5 和 I6=5,分两次反推。结果过程严重受阻,即反推不出矛盾结果,也反推不出最终结果。具体如下图 1 下左、下中、下右三表。
图 1
第 4 步:增设已知数反推和分组。在第 3 步两个反推结果表格的基础上,增选上中宫 E1 和 E2 两个二者居一的候选数 “5”进一步反推,结果还是严重受阻。具体如下图 2 上中、上右、下中、下右四表。
因继续增加假定已知数反推,表格数量将继续呈 2 的 N次方指数级增加,为免因表格数量太多出现解题过程混乱,把 4 个表格分成 A, B, C , D 4 个组。
图 2
第 5 步:A 组增加假定已知数继续反推。选上左宫初始的两个二者居一的“9”,先后假定 A2,C1 两个单元格为“9”,分别反推一次。结果如下图 3 中、右二表。
图 3
第 6 步:A 组再增加假定已知数反推。在第 5 步两个反推结果表格的基础上,增加右下宫经过候选数列举和整理出二者居的一对“9”为假定已知数,先后假定右下宫 G7, G8 两个单元格为“9”,分别反推一次,结果如下图 4 中上、右上、中下、右下四表。
图 4
第 7 步:继续增加假定已知数反推。在第 6 步 4 个表格的基础上,增加左中宫的一对“8”为已知数,每个表格先后假定 B5, B6 为“8”相继反推一次,结果如下图 5 中上、右上、中下、右下四表和下图 6 中上、右上、中下、右下四表。
图 5
图 6
在以上 8 个表格中,图 6 右上表已经出现正确结果,整个解题过程完成。其他表格要么仍不出现最后结果,要么已经出现矛盾结果。但因为数独结果具有唯一性,仍未出现最后结果者无须再解。
分析与讨论
(1)本次解题过程借用了 EXCEL 电子表格辅助,但不是利用 EXCEL 设计复杂的计算机程序运算,只是利用了 EXCEL 电子表的复制、粘贴和键盘输入等简单功能,利用复制、粘贴代替人工的反复誊抄操作,利用键盘输入和删除功能代替铅笔完成反复涂抹操作,其他解题过程和利用铅笔和纸一样,都是靠人脑一步步演算。
(2)为减少图片数量,文中所有插图统一按每张 A4 纸 6 个表格的大小设置,直接在文中查看表格中的候选数字比较困难,有需要认真研究的读者可以利用图片查看器放大后细看,字迹很清晰。
(3)关于解题时间。本题需要假定 5 个已知数才能得出最后结果。以作者平时的解题经验,在利用 EXCEL 电子表格辅助的情况下,自始至终每完整分析完一个包含 5 个假定已知数的表格,平均用时约 15 分钟左右。5 个假定已知数的组合顺序,共有 32 种( 2^5 ),运气特别差时如果要分析到最后一个表格才出现正确结果,用时可能需要 480 分钟(8 小时)。但因解出最终结果具有随机性,不可能所有人都需要分析完最后一个表格才出现正确结果,按中位数计算,平均解题用时约在 4 小时左右。加上复制粘操作,平均解题时间应不致到超过 6 小时。
网传重庆某教授解题用时 15 天,感觉有点夸张。就算使用最原始的铅笔和纸,每解完一张表格重新手工誊抄一次,每誊抄一次用时 1 小时,总解题时间最多也就 32 小时另加 6 小时。因为分析表格用铅笔和键盘,用时实际上是相差不多的。何况就算不懂 EXCEL 电子表格,还可以使用复印机,最不济还可以利用复写纸,再怎么的也不会有人落后到每分析完一张表格都需要手工誊抄一次的地步了!