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 条评论
登录 后参与评论

相关文章

来自专栏专知

【论文推荐】最新八篇推荐系统相关论文—可解释推荐、上下文感知推荐系统、异构知识库嵌入、深度强化学习、移动推荐系统

【导读】专知内容组既昨天推出八篇推荐系统相关论文之后,今天为大家又推出八篇推荐系统(Recommendation System)相关论文,欢迎查看!

3723
来自专栏DHUtoBUAA

正六边形网格化(Hexagonal Grids)原理与实现

 在路径规划、游戏设计栅格法应用中,正六边形网格不如矩形网格直接和常见,但是正六边形具有自身的应用特点,更适用于一些特殊场景中,比如旷阔的海洋、区域或者太空。...

4075
来自专栏专知

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

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

7.5K8
来自专栏专知

【论文推荐】最新十篇推荐系统相关论文—内容感知、图卷积神经网络、博弈论、个性化排序、元学习、xDeepFM

【导读】专知内容组既前两天推出十六篇推荐系统相关论文之后,今天为大家又推出十篇推荐系统(Recommendation System)相关论文,欢迎查看!

2453
来自专栏专知

【论文推荐】最新六篇行人再识别相关论文—特定视角、多目标、双注意匹配网络、联合属性-身份、迁移学习、多通道金字塔型

【导读】专知内容组整理了最近六篇行人再识别(Person Re-Identification)相关文章,为大家进行介绍,欢迎查看! 1. Learning Vi...

7715
来自专栏专知

【论文推荐】最新七篇图像检索相关论文—草图、Tie-Aware、场景图解析、叠加跨注意力机制、深度哈希、人群估计

2333
来自专栏机器学习算法工程师

OpenCV从零基础---检测及分割图像的目标区域

作者:王抒伟 编辑:王抒伟 算了 爱看多久看多久 零 参考目录: 1.获取图片 2.转换灰度并去噪声 3.提取图像的梯度 4.我们继续去噪声 5.图像形态学...

2.6K10
来自专栏专知

【论文推荐】最新5篇知识图谱相关论文—强化学习、习知识图谱的表示、词义消除歧义、并行翻译嵌入、图数据库

【导读】专知内容组整理了最近五篇知识图谱(Knowledge Graph)相关文章,为大家进行介绍,欢迎查看! 1. DeepPath: A Reinforce...

4114
来自专栏数据结构与算法

HDU4576 Robot(概率)

抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

851
来自专栏专知

【论文推荐】最新5篇语音识别(ASR)相关论文—音频对抗样本、对抗性语音识别系统、声学模型、序列到序列、口语可理解性矫正

【导读】专知内容组整理了最近五篇语音识别(Automatic Speech Recognition, ASR)相关文章,为大家进行介绍,欢迎查看! 1. Aud...

4784

扫码关注云+社区