「Python破解九宫格数独」：九宫格生成与数独求解

  • A+
所属分类：编程语言

「Python破解九宫格数独」：九宫格生成与数独求解

作者：冰不语

来源：「CVPy」公众号

前言

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

我们要做的有三部分：

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

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

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

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

生成九宫格

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

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

「Python破解九宫格数独」：九宫格生成与数独求解

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

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

「Python破解九宫格数独」：九宫格生成与数独求解

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

矩阵初始化为零阵

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

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

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

得到的矩阵如下所示：

「Python破解九宫格数独」：九宫格生成与数独求解

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

编写算法求解九宫格矩阵

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

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

代码里标注了出处：

  1. ## 数独求解算法，回溯法。来源见下面链接，有细微改动。
  2. ## http://stackoverflow.com/questions/1697334/algorithm-for-solving-sudoku
  3. def findNextCellToFill(grid, i, j):
  4. for x in range(i,9):
  5. for y in range(j,9):
  6. if grid[x][y] == 0:
  7. return x,y
  8. for x in range(0,9):
  9. for y in range(0,9):
  10. if grid[x][y] == 0:
  11. return x,y
  12. return -1,-1
  13. def isValid(grid, i, j, e):
  14. rowOk = all([e != grid[i][x] for x in range(9)])
  15. if rowOk:
  16. columnOk = all([e != grid[x][j] for x in range(9)])
  17. if columnOk:
  18. # finding the top left x,y co-ordinates of the section containing the i,j cell
  19. secTopX, secTopY = 3 *int(i/3), 3 *int(j/3)
  20. for x in range(secTopX, secTopX+3):
  21. for y in range(secTopY, secTopY+3):
  22. if grid[x][y] == e:
  23. return False
  24. return True
  25. return False
  26. def solveSudoku(grid, i=0, j=0):
  27. i,j = findNextCellToFill(grid, i, j)
  28. if i == -1:
  29. return True
  30. for e in range(1,10):
  31. if isValid(grid,i,j,e):
  32. grid[i][j] = e
  33. if solveSudoku(grid, i, j):
  34. return True
  35. # Undo the current cell for backtracking
  36. grid[i][j] = 0
  37. return False

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

solveSudoku(soduko)

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

  1. print("
生成的数独
")
  2. print(soduko)
  3. print("
求解后的数独
")
  4. ## 数独求解
  5. solveSudoku(soduko)
  6. print(soduko)
  7. print("
验算：求每行每列的和
")
  8. row_sum = map(sum,soduko)
  9. col_sum = map(sum,zip(*soduko))
  10. print(list(row_sum))
  11. print(list(col_sum))

输出的结果如下：

「Python破解九宫格数独」：九宫格生成与数独求解

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

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

填充图片九宫格

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

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

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

「Python破解九宫格数独」：九宫格生成与数独求解

尾声

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

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

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

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

代码

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

题图：pexels，CC0 授权。

直播推荐：

「Python破解九宫格数独」：九宫格生成与数独求解

weinxin
我的微信公众号
爱真理，得永生！　　　　　　　　　　爱在灵灵久博客，网罗天下，福利大家！

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: