115行代码，手把手教你做个数独解析器！

知行编程网 2022-06-26 20:00 知行编程网 | 隐藏边栏 | 抢沙发 | 5 0

文章评分 0 次，平均分 0.0 ：

来源 | medium 出品 | 大数据文摘

编译 | 牛婉杨

你也是数独爱好者吗？

Aakash Jhawar和许多人一样，乐于挑战新的难题。上学的时候，他每天早上都要玩数独。长大后，随着科技的进步，我们可以让计算机来帮我们解数独了！只需要点击数独的图片，它就会为你填满全部九宫格。

叮~ 这里有一份数独解析教程，等待你查收~ 喜欢收藏硬核干货的小伙伴看过来~

我们都知道，数独由9×9的格子组成，每行、列、宫各自都要填上1-9的数字，要做到每行、列、宫里的数字都不重复。

可以将解析数独的整个过程分成3步：

第一步：从图像中提取数独

第二步：提取图像中出现的每个数字

第三步：用算法计算数独的解

第一步：从图像中提取数独

首先需要进行图像处理。

1、对图像进行预处理

首先，我们应用高斯模糊的内核大小(高度，宽度)为9的图像。注意，内核大小必须是正的和奇数的，并且内核必须是平方的。然后使用11个最近邻像素自适应阈值。

为了使网格线具有非零像素值，我们颠倒颜色。此外，把图像放大，以增加网格线的大小。

阈值化后的数独图像

2、找出最大多边形的角

下一步是寻找图像中最大轮廓的4个角。所以需要找到所有的轮廓线，按面积降序排序，然后选择面积最大的那个。

使用的操作符。带有max和min的itemgetter允许我们获得该点的索引。每个点都是有1个坐标的数组，然后[0]和[1]分别用于获取x和y。

右下角点具有最大的(x + y)值；左上角有点最小(x + y)值；左下角则具有最小的(x - y)值；右上角则具有最大的(x - y)值。

现在我们有了4个点的坐标，然后需要使用索引返回4个点的数组。每个点都在自己的一个坐标数组中。

最大多边形的四个角

3、裁剪和变形图像

有了数独的4个坐标后，我们需要剪裁和弯曲一个矩形部分，从一个图像变成一个类似大小的正方形。由左上、右上、右下和左下点描述的矩形。

注意：将数据类型显式设置为float32或‘getPerspectiveTransform’会引发错误。

用计算长度的边来描述一个正方形，这是要转向的新视角。然后要做的是通过比较之前和之后的4个点来得到用于倾斜图像的变换矩阵。最后，再对原始图像进行变换。

裁剪和变形后的数独图像

4、从正方形图像中推断网格

从正方形图像推断出81个单元格。我们在这里交换 j 和 i ，这样矩形就被存储在从左到右读取的列表中，而不是自上而下。

5、得到每一位数字

下一步是从其单元格中提取数字并构建一个数组。

extract_digit 是从一个数独方块中提取一个数字(如果有的话)的函数。它从整个方框中得到数字框，使用填充特征查找来获得框中间的最大特征，以期在边缘找到一个属于该数字的像素，用于定义中间的区域。接下来，需要缩放并填充数字，让适合用于机器学习的数字大小的平方。同时，我们必须忽略任何小的边框。

最后的数独的形象

现在，我们有了最终的数独预处理图像，下一个任务是提取图像中的每一位数字，并将其存储在一个矩阵中，然后通过某种算法计算出数独的解。

第二步：提取图像中出现的每个数字

对于数字识别，我们将在MNIST数据集上训练神经网络，该数据集包含60000张0到9的数字图像。从导入所有库开始。

需要修复随机种子以确保可重复性。

然后将图像重塑为样本*像素*宽度*高度，并输入从0-255规范化为0-1。在此之后，对输出进行热编码。

接下来，我们将创建一个模型来预测手写数字。

模型总结

在创建模型之后，需要进行编译，使其适合数据集并对其进行评估。

现在，可以测试上面创建的模型了。

手写体数字分类模型的预测数字

神经网络的精度为98.314%！最后，保存序列模型，这样就不必在需要使用它的时候反复训练了。

更多关于手写数字识别的信息：

https://github.com/aakashjhawar/Handwritten-Digit-Recognition

下一步是加载预先训练好的模型。

调整图像大小，并将图像分割成9x9的小图像。每个小图像的数字都是从1-9。

identify_number 函数拍摄数字图像并预测图像中的数字。

完成以上步骤后，数独网格看起来是这样的：

提取的数独

第三步：用回溯算法计算数独的解

我们将使用回溯算法来计算数独的解。

在网格中搜索仍未分配的条目。如果找到引用参数行，col 将被设置为未分配的位置，而 true 将被返回。如果没有未分配的条目保留，则返回false。“l” 是 solve_sudoku 函数传递的列表变量，用于跟踪行和列的递增。

返回一个boolean，指示指定行的任何赋值项是否与给定数字匹配。

返回一个boolean，指示指定列中的任何赋值项是否与给定数字匹配。

返回一个boolean，指示指定的3x3框内的任何赋值项是否与给定的数字匹配。

检查将num分配给给定的(row, col)是否合法。检查“ num”是否尚未放置在当前行，当前列和当前3x3框中。

采用部分填入的网格，并尝试为所有未分配的位置分配值，以满足数独解决方案的要求(跨行、列和框的非重复)。“l” 是一个列表变量，在 find_empty_location 函数中保存行和列的记录。将我们从上面的函数中得到的行和列赋值给列表值。

最后一件事是print the grid。

最后，把所有的函数整合在主函数中。

这个函数的输出将是最终解出的数独。

最终的解决方案

当然，这个解决方案绝不是万无一失的，处理图像时仍然会出现一些问题，要么无法解析，要么解析错误导致无法处理。不过，我们的目标是探索新技术，从这个角度来看，这个项目还是有价值的。

相关报道：

https://medium.com/@aakashjhawar/sudoku-solver-using-opencv-and-dl-part-1-490f08701179

https://medium.com/@aakashjhawar/sudoku-solver-using-opencv-and-dl-part-2-bbe0e6ac87c5

<section style="white-space: normal;line-height: 1.75em;text-align: center;"><strong style="color: rgb(0, 0, 0);font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;letter-spacing: 0.544px;widows: 1;background-color: rgb(255, 255, 255);max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong>完<strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;font-size: 14px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;font-size: 16px;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;letter-spacing: 0.5px;box-sizing: border-box !important;overflow-wrap: break-word !important;">—</span></strong></span></strong></span></strong></section><pre><pre style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;white-space: normal;font-family: -apple-system-font, system-ui, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;widows: 1;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="max-width: 100%;letter-spacing: 0.544px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section powered-by="xiumi.us" style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 15px;margin-bottom: 25px;max-width: 100%;opacity: 0.8;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section><section style="margin-bottom: 15px;padding-right: 0em;padding-left: 0em;max-width: 100%;color: rgb(127, 127, 127);font-size: 12px;font-family: sans-serif;line-height: 25.5938px;letter-spacing: 3px;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;"><strong style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;font-size: 16px;font-family: 微软雅黑;caret-color: red;box-sizing: border-box !important;overflow-wrap: break-word !important;">为您推荐</span></strong></span></section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;">吴恩达推荐笔记：22 张图总结深度学习全部知识</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;">图灵奖得主Yann LeCun《深度学习》春季课程</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;">你一定从未看过如此通俗易懂的YOLO系列解读 (下)</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;color: rgb(0, 0, 0);box-sizing: border-box !important;overflow-wrap: break-word !important;">22课时、19大主题，CS 231n进阶版课程视频上线</section><section style="margin-top: 5px;margin-bottom: 5px;padding-right: 0em;padding-left: 0em;max-width: 100%;min-height: 1em;font-family: sans-serif;letter-spacing: 0px;opacity: 0.8;line-height: normal;text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="color: rgb(87, 107, 149);font-size: 14px;">震惊！这个街道办招8人，全是清华北大博士硕士！</span><br  /></section></section></section></section></section></section></section></section></section>

本篇文章来源于: 深度学习这件小事

本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！

知行编程网关注：1 粉丝：1

这个人很懒，什么都没写