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

作者：冰不语

来源：「CVPy」公众号

前言

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

我们要做的有三部分：

1.生成九宫格，也就是生成一个9×9的矩阵，把已知的数字按照图片中的位置填到矩阵中的相应位置，其他位置全部置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