【数独 2】候选数法解数独谜题 - 挖掘更深的信息 -C++ 实现
🍘前言
前面已经介绍了用候选数法来解数独谜题。还没看的朋友点这里哦：【数独 1】不回溯，试试候选数法1ms高效解数独谜题-C++实现
接下来在前一节算法的基础上进行一些==改进==，使模型可解更多的数独谜题。
本解的方法利用==区块摒除法==和==数对法==的思路实现，下面会先介绍这两种数独谜题的解法。
🍘区块摒除法过程
区块摒除法是人玩数独游戏时常用的一种解法。
如果在一个小九宫中，某个数字剩下的候选数都在同行（列），则可以摒除该行（列）其它位置该数字出现的可能性。
如果在一行（列）中，某个数字剩下的候选数豆子同一小九宫中，则可以摒除该小九宫其它位置该数字出现的可能性。
例子：
对==下图==情况，可以首先数字 6 对第五宫摒除，得到第五宫的 6 在 R4C5 或 R6C5，不论是在 R4C5 还是 R6C5，此时==C5 这一列的其他单元格都不能再有数字 6==。结合第一宫和第三宫的数字 6 对第二宫的摒除，我们可以确定，第二宫的数字 6 在 R1C4。
🍘数对法过程
数对法的使用条件比区块摒除法更苛刻
如果在一（行 / 列 / 小九宫）中，两个不同的数字剩余的候选数恰好都在同样的两个格子中，则可以排除这两个格子中的其它候选数。
例子：
如==下图==所示，通过数字 2 和 7 对第一宫的摒除，我们发现出现了这样的情况：在第一宫中，==2 和 7 两个数字的候选位置占用了相同的两个单元格==。于是可以肯定，这两个单元格中只能是 2 和 7，从而==摒除了其他数字出现在这两个单元格中的可能==。
在下图的例子中，我们再利用 8 对 C1 列的摒除，就可以确定第一宫中的数字 8 位于 R1C3。
刚刚我们介绍了两种解数独的方法，但是要怎么把它们==实现==到我们的程序中来呢？继续往下面看吧！
🍘程序的实现
首先我们考虑==数据的表示==，我们使用两个全局变量，其中一个二维数组 s 来存储我们的数独盘面，另一个三维数组 p 来存储我们的候选数。
其中我们存储候选数的三维数组 p 在==逻辑上==可以理解成像下图的样子，
p[3][4][2]=1表示数独第 3 行第 4 列的数字 2 处于候选状态。相反，如果值为p值为 0 则表示相应的候选数已经被排除了。
接下来我们看具体的算法实现。
1. 区块摒除
区块摒除法在程序中将被实现成一个扫描
p数组的过程，扫描寻找的==情况可以分为两种==：
1）在扫描某个数字对应的矩阵时，发现矩阵的一行或一列，==恰有 2 到 3 个为 1 的值，而这些 1 值都位于同一个小九宫中==。则在对应的数字矩阵中，就可以排除小九宫中其它的 1 值。
2）在扫描某个数字对应的矩阵时，发现矩阵的一个小九宫中==恰有 2 到 3 个为 1 的值，而这些 1 值都位于同一行或同一列中==。同样的，我们在对应的数字矩阵中，就可以排除同行或同列中其它的 1 值。
源代码：
2. 数对
数对法的实现也是一个扫描
p的过程。
可以在一行、一列、或一小九宫中寻找数对
在一小九宫中寻找数对的步骤：1）对于每个数字对于的矩阵，首先，我们逐个小九宫地扫描，如果发现==一个小九宫中只有两个 1 值==，则说明我们发现了一个存在数对的潜在可能性，于是进行下一步。2）接下来用我们发现的这个小九宫，来和其它数字对应的矩阵来的相同宫位进行匹配。如果找到了一个完全匹配的（1 值的数量和位置都相同）小九宫，则我们就找到了一个数对。3）找到数对之后，我们就可以排除 1 到 9 所有数字对应矩阵的数对所在位置的 1 值。
源代码：
在实现了上面两个方法后，只需要在原来的主函数中
change_p();的位置加上这两个函数的调用就可以啦！
主函数源代码：
测试数据：0 0 0 0 0 7 3 0 82 0 0 0 0 0 0 0 70 9 7 8 0 5 6 0 00 7 0 1 0 0 9 0 60 0 5 9 0 3 7 0 09 0 1 0 0 8 0 3 00 0 2 3 0 4 5 6 08 0 0 0 0 0 0 0 15 0 4 2 0 0 0 0 0
这是上一节不能解决的一个数独谜题，现在已经可以填出全部的数字啦！
运行截图
🍘总结
相比上次，现在的程序已经强大很多啦！可以解出更多的数独谜题（依旧不是全部，仍然有待努力），满满的成就感。数独题库：尤怪之家数独挑战馆出题菜单有兴趣的朋友们可以尝试用这个网站中的数独来测试程序。
🍘都已经白嫖到这里了，不给博主来个==点赞关注加收藏==再走？🍘🍘你们的支持就是博主不断写作的动力！🍘
版权声明: 本文为 InfoQ 作者【阿锋】的原创文章。
原文链接:【http://xie.infoq.cn/article/682dffc2a8bdf3a77ae593ae1】。文章转载请联系作者。
还未添加个人签名 2022.08.09 加入
还未添加个人简介
评论