数独的识别与求解

发表于 分类于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

前言

🤐 疫情在家宅太久了，闷得慌，2020 年 2 月 26 日，微软数独正式上架苹果 App Store，就下载玩了起来，游戏本身制作非常精良，只是内置了广告，付费去广告的价格有点高，15 元/月或 73 元/年，买不起，还是将就一下吧。玩得久了后，又觉得有点无聊和费劲了，索性来写个程序解数独吧。

Tip：数独求解用的是DFS，图像识别用的是OpenCvSharp，数字识别用的是Tesseract OCR。

😅 话说好久不练算法了，还得去百度查一下才敢说自己写的是 DFS。

数独求解

从最简单的部分讲起吧，是的，求解才是最简单的部分。首先用 WPF 写个简单的数独游戏界面出来，数独的格子就用 Button 吧，点击再弹出一个数字选择的窗体，当然也支持点击后直接用按键输入。

随便输入一些数字，会以黑色展示，然后点击 Solve 按钮，就可以求解，当然，你可以连续点击 Solve，获取随机答案。

求解的算法倒是很好写，很久没碰算法了，也是一遍写过，不需要调试。

求解方法Solve的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private static readonly Random random = new Random();
private static readonly int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

public static bool Solve(int[,] data, int i = 0, int j = 0)
{
    i += j / 9;
    j %= 9;
    if (i == 9)
    {
        return true;
    }
    else if (data[i, j] == 0)
    {
        var r = random.Next(100);
        for (int v = 0; v < nums.Length; v++)
        {
            data[i, j] = nums[(r + v) % nums.Length];
            if (CheckValue(data, i, j) && Solve(data, i, j + 1))
            {
                return true;
            }
        }
        data[i, j] = 0;
        return false;
    }
    else
    {
        return Solve(data, i, j + 1);
    }
}

核心求解方法 Solve，数独的数据通过二维数组int[,] data保存，0 代表没有填充数字。算法简单的应该不需要讲解了，CheckValue方法就是判断填入的数字是否满足数独的规则。

数独识别

最麻烦的部分来了，求解半小时，识别一整天，一开始没意识到这么麻烦，计算机视觉(Computer Vision)之前也只是简单了解，从没有实际应用过，这次也算是实战了一回。

为什么要做识别呢？理由很简单，数独游戏可能是来自手机 APP、网页或程序等等，获取这些数据，最通用的方式，还是先截图，然后再从图片中识别。

既然是截图，索性就直接全屏截图，然后识别截图中的数独，识别部分的思路是按照 OpenCV 的惯用思路去处理，首先获取 MAT，然后依次调用CvtColor、GaussianBlur、Canny方法进行灰化、降噪、边缘检测处理。

之后的思路便是自由发挥了，我先假定屏幕上只有一个数独：

  1. 通过 FindContours 方法提取图像的所有轮廓；
  2. 然后遍历轮廓，记录这些轮廓作为其他轮廓的 Parent 的出现次数；
  3. 找到出现次数不小于 9 次（图示里用红色矩形标记）且高度（宽度或面积也行）最大的一个轮廓，应该就是数独的轮廓；
  1. 截取数独轮廓，从全屏截图中剔除数独以外的图像内容；
  1. 再次通过 FindContours 方法提取数独图像的所有轮廓；
  2. 遍历轮廓，通过 BoundingRect 方法定位矩形边界，这是为了找到数独图像中的数字；
  3. 判断矩形边界的高度（毕竟数字的字符宽度不确定，但高度至少是一致的），高度在整个数独轮廓的 1/18 和 1/12 之间的，基本可以判断是数字；
  1. 计算矩形的所在坐标，并调用 Tesseract 进行数字识别。

setNumber 的三个参数，分别是行、列、值，用于将识别出来的数据进行输出，识别部分的代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static async Task OCR(Action<int, int, int> setNumber, string fileName = tempFilename) => await Task.Run(() =>
{
    var src = new Mat(fileName);
    var tmp = src.Clone();
    Cv2.CvtColor(src, tmp, ColorConversionCodes.RGB2GRAY);
    Cv2.GaussianBlur(tmp, tmp, new Size(3, 3), 0, 0);
    Cv2.Canny(tmp, tmp, 10, 255);
    Cv2.FindContours(tmp, out Point[][] contours, out HierarchyIndex[] hierarchy, RetrievalModes.Tree, ContourApproximationModes.ApproxSimple);
    var rect = new Rect();
    var contourCount = new Dictionary<int, int>();
    for (int i = 0; i < contours.GetLength(0); i++)
    {
        var p = hierarchy[i].Parent;
        if (p >= 0)
        {
            if (contourCount.ContainsKey(p))
            {
                contourCount[p]++;
                if (contourCount[p] >= 9)
                {
                    var r = Cv2.BoundingRect(contours[p]);
                    if (r.Height > rect.Height)
                    {
                        rect = r;
                    }
                }
            }
            else
            {
                contourCount.Add(p, 1);
            }
        }
    }
    tmp = new Mat(tmp, rect);
    src = new Mat(src, rect);
    Cv2.FindContours(tmp, out contours, out hierarchy, RetrievalModes.Tree, ContourApproximationModes.ApproxSimple);
    for (int i = 0; i < contours.GetLength(0); i++)
    {
        var r = Cv2.BoundingRect(contours[i]);
        if (r.Height < (rect.Height / 12.0) && r.Height > (rect.Height / 18.0))
        {
            if (new Mat(src, r).ImWrite(fileName))
            {
                var m = (int)((r.Top + r.Height / 2.0) / (rect.Height / 9.0));
                var n = (int)((r.Left + r.Width / 2.0) / (rect.Width / 9.0));
                var text = OCRSingleNumber(fileName);
                setNumber(m, n, text);
            }
        }
    }
});

数独识别部分的完整代码在SudokuCV.cs文件里。

识别效果

对于主色调是黑白灰之类的，识别效果尚可，像 iOS 版的微软数独，但是对于颜色丰富点的图像，识别效果就相当差了，调这个有点麻烦，还是把这个坑留着吧。

后记

本项目的完整源码已存到 Github 上，HT.Sudoku

至于数独答案怎么自动输入，留坑，看以后啥时候又闲得慌就来填坑。

另外，😏 对数独求解有兴趣的 gamer，去瞧瞧下面这篇文章吧。

Solving Every Sudoku Puzzle