作者：冰不語
前言
在此之前， 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(" 生成的數獨 ")
print(soduko)
print(" 求解後的數獨 ")
## 數獨求解
solveSudoku(soduko)
print(soduko)
print(" 驗算：求每行每列的和 ")
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
題圖：pexels，CC0 授權。
直播推薦：
最後兩行可以看到各行各列的和確實都是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
題圖：pexels，CC0 授權。
直播推薦：