OpenCV玩九宫格数独(三):九宫格生成与数独求解

前言

在此之前,OpenCV玩九宫格数独(一)OpenCV玩九宫格数独(二)分别介绍了如何从九宫格图片中提取出已知数字和如何用knn训练数字识别模型。在这些前期工作都已经完成的基础上,接下来我们需要做什么呢?

我们要做的有三部分:

1.生成九宫格,也就是生成一个9x9的矩阵,把已知的数字按照图片中的位置填到矩阵中的相应位置,其他位置全部置0。

2.编写数独求解算法,对九宫格矩阵进行求解。

3.把填完的九宫格重新填充到图片中去。

我们仍然是一步一步来说。

生成九宫格

这里就需要用到我们之前两篇的内容了,生成九宫格的步骤如下:

1.从九宫格图片中提取数字(第一篇内容)

2.用训练的数字识别模型对上一步的数字进行识别。

这里需要注意的是,提取之后的数字,要按照训练模型之前的数据处理方式进行处理,然后输入knn模型识别。识别效果如下图所示。就像上一篇结尾说的一样,本文用不到一百个样本训练出来的模型仅仅能保证在本文的示例图片上取得完美效果。其他情况下不作保证。如果想要得到更完美的数字识别模型,请优化数据预处理方式和加大数据量。

3.按照位置顺序把数字填入相应的矩阵位置中。

矩阵初始化为零阵

soduko = np.zeros((9, 9),np.int32)

然后按照位置求解数字在矩阵中所处的位置

## 求在矩阵中的位置    
soduko[int(y/box_h)][int(x/box_w)] = number

得到的矩阵如下所示:

跟上面的图片比较一下,是不是位置一样呢?

编写算法求解九宫格矩阵

数独的求解算法有很多种,热爱数独的且热爱数学的人对此进行了深入研究,提出了各种各样的算法。这里用的是传说中的回溯法。回溯法具体内容感兴趣的可以自行搜索,我这里只是用,没有深究。

至于为什么用这个算法?。。。因为我在stackoverflow上找到了可用的代码(捂脸逃...)

代码里标注了出处:

## 数独求解算法,回溯法。来源见下面链接,有细微改动。

## http://stackoverflow.com/questions/1697334/algorithm-for-solving-sudoku
def findNextCellToFill(grid, i, j):
    for x in range(i,9):
        for y in range(j,9):
            if grid[x][y] == 0:
                return x,y
    for x in range(0,9):
        for y in range(0,9):
            if grid[x][y] == 0:
                return x,y
    return -1,-1

def isValid(grid, i, j, e):
    rowOk = all([e != grid[i][x] for x in range(9)])
    if rowOk:
        columnOk = all([e != grid[x][j] for x in range(9)])
        if columnOk:
            # finding the top left x,y co-ordinates of the section containing the i,j cell
            secTopX, secTopY = 3 *int(i/3), 3 *int(j/3)
            for x in range(secTopX, secTopX+3):
                for y in range(secTopY, secTopY+3):
                    if grid[x][y] == e:
                        return False
                return True
    return False

def solveSudoku(grid, i=0, j=0):
    i,j = findNextCellToFill(grid, i, j)
    if i == -1:
        return True
    for e in range(1,10):
        if isValid(grid,i,j,e):
            grid[i][j] = e
            if solveSudoku(grid, i, j):
                return True
            # Undo the current cell for backtracking
            grid[i][j] = 0
    return False

然后我们根据算法对前面生成的数独求解。只需要这么一句就行:

solveSudoku(soduko)

这里为了便于观察,分别原始数独求解后的数独,为了验算,输出结果数独的每行每列的和,如果求解正确,每行每列和都应该等于1+2+...+9=45

print("\n生成的数独\n")
print(soduko)
print("\n求解后的数独\n")

## 数独求解
solveSudoku(soduko)

print(soduko)
print("\n验算:求每行每列的和\n")
row_sum = map(sum,soduko)
col_sum = map(sum,zip(*soduko))
print(list(row_sum))
print(list(col_sum))

输出的结果如下:

最后两行可以看到各行各列的和确实都是45。数独求解成功。

在黑窗口里看最后的数独可能不那么友好,接下来我们就把生成的九宫格填充到图片里来看。

填充图片九宫格

我们只需要在图片中九宫格中相应的位置写相应的数字就可以了,这一部分乏善可陈。还是直接看代码和效果图吧。

## 把结果按照位置填入图片中  
for i in range(9):
    for j in range(9):
        x = int((i+0.25)*box_w)
        y = int((j+0.5)*box_h)
        cv2.putText(img,str(soduko[j][i]),(x,y), 3, 2.5, (0, 0, 255), 2, cv2.LINE_AA)
#print(number_boxes)
cv2.namedWindow("img", cv2.WINDOW_NORMAL);
cv2.imshow("img", img)
cv2.waitKey(0)

最后的效果你应该在预告篇就看到过了。为了便于对比,保留了上一步数字识别的结果。

尾声

到此,整个opencv玩数独项目告一段落。容我感慨几句。

玩数独项目最早可以追溯到一年前,那时候就开始尝试用C++来对数独图片进行处理,但是最终受限于当时的水平和心态,只完成了一小半。为什么说心态呢?因为那时候很多东西不会的也不敢去尝试,如果当时敢于尝试,畏难心理没有那么重的话,也许这个项目会提前很久完成。

其实我本来最擅长的是C++的,然而最近用python越来越顺手了。这个项目坐下来受益最大的显然是我自己。分享出来,感兴趣的人也许会有很多,但是真正会去做一遍的应该没有几个。会完整做下来的应该更是寥寥无几。

这个小项目都对高手来说也许不算什么,但是对于初学Python和opencv的人来说应该是一个不错的锻炼。希望有人能做一遍,能做下来的相信会做的更好。欢迎感兴趣的人来一起交流学习。

代码

github:https://github.com/LiuXiaolong19920720/opencv-soduko

相关推荐

OpenCV 玩九宫格数独:预告篇

OpenCV 玩九宫格数独(一):九宫格图片中提取数字

OpenCV 玩九宫格数独(二):knn 数字识别

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

计算机如何理解我们的语言?NLP is fun!

【导读】我们从日常每天都会用到的推荐系统到现在研究火热的开放性聊天、对话机器人,越来越多的产品与应用的背后都需要自然语言处理(NLP)和知识图谱的技术。也有越来...

793
来自专栏专知

【干货】Python大数据处理库PySpark实战——使用PySpark处理文本多分类问题

【导读】近日,多伦多数据科学家Susan Li发表一篇博文,讲解利用PySpark处理文本多分类问题的详情。我们知道,Apache Spark在处理实时数据方面...

1.9K7
来自专栏大数据文摘

如何优雅地测量一只猫的体积

1897
来自专栏BestSDK

【干货教程】可视化大数据最易犯的10个错误:排序混乱,扭曲数据...

  从传播学的角度,这意味着以图片为载体的视觉叙事更加引人注意,更容易获得人们的好感。   通过可视化信息,我们的大脑可以更有效地合成和保留信息内容,增强对信息...

3326
来自专栏机器之心

入门 | 自然语言处理是如何工作的?一步步教你构建 NLP 流水线

计算机非常擅长使用结构化数据,例如电子表格和数据库表。但是我们人类通常用文字交流,而不是使用电子表格来交流。这对计算机来说不是一件好事。

653
来自专栏新智元

从“London”出发,8步搞定自然语言处理(Python代码)

【新智元导读】自然语言处理是AI的一个子领域,从人们日常沟通所用的非结构化文本信息中提取结构化数据,以便计算机理解。本文用通俗易懂的语言深入浅出的介绍了自然语言...

532
来自专栏机器学习算法原理与实践

用scikit-learn学习LDA主题模型

    在LDA模型原理篇我们总结了LDA主题模型的原理,这里我们就从应用的角度来使用scikit-learn来学习LDA主题模型。除了scikit-learn...

913
来自专栏大数据挖掘DT机器学习

PageRank算法(2):PageRank原理剖析

一、PageRank算法的简单举例 Google PageRank算法的思想精华在于:将一个网页级别/重要性的排序问题转化成了一个公共参与、以群体民主投票的方式...

3586
来自专栏人工智能

基于TensorFlow的循环神经网络生成矢量格式的伪造汉字

注意:对于中文汉字和日文汉字我根据具体情况交替使用它们。

6658
来自专栏深度学习自然语言处理

【python】Tkinter可视化窗口(三)

我们的最终效果就是移动scale里面的bar,使得上面的黄色label显示该值并保留两位小数。

833

扫码关注云+社区