First of all, I am so sorry for keeping you waiting.
I've just finished my second semester and came back for a long trip from Viet Nam.
In part 2 of this series (See part 2), we've discussed how to recognize number from each cell in SUDOKU grid. Now, with the help of SVM, we can easily extract the digit number from SUDOKU image. Base on that recognition result, we can solve the SUDOKU grid by using a backtracking method.
But first, let's form the recognition result to the matrix for more easier to solve.
The recognition result of a SUDOKU picture will be formed as a matrix like an example below.
Fig 1. SUDOKU picture
[0 9 7 0 5 0 2 1 0]
[0 0 0 0 8 0 1 0 0]
[0 0 2 0 9 7 0 6 3]
[0 6 0 0 0 0 3 0 9]
[3 0 0 4 1 9 0 0 6]
[7 0 9 0 0 0 0 2 0]
[8 3 0 2 4 0 9 0 0]
[0 0 6 0 3 0 0 0 0]
[0 5 4 0 7 0 6 3 0]
Matrix of result after recognition (0 means the cell is empty)
Now, we have the result of recognition as a matrix. Next step, we will solve SUDOKU problem base on that result.
The easiest solution to solve SUDOKU matrix is using the Backtracking algorithm.
We can solve SUDOKU by one by one assigning numbers to empty cells. Before assigning a number, we check whether it is safe to assign. We basically check that the same number is not present in current row, current column and current 3X3 subgrid. After checking for safety, we assign the number, and recursively check whether this assignment leads to a solution or not. If the assignment doesn’t lead to a solution, then we try next number for current empty cell. And if none of number (1 to 9) lead to solution, we return false.
This post used the idea from page: http://www.geeksforgeeks.org/backtracking-set-7-suduku/ to solve the SUDOKU problem. I don't have time to explain what backtracking is but I wish I could have time to write an article about basic of backtracking.
Here is the code for solving SUDOKU problem
import numpy as np #Finding unsige cell #File name: SUDOKU.py def FindUnsignedLocation(Board, l): for row in range(0,9): for col in range(0,9): if (Board[row][col] == 0): l[0] = row l[1] = col return True return False # Hàm kiểm tra tính an toàn của những ô trong hàng def InRow(Board, row, num): for i in range(0,9): if (Board[row][i] == num): return True return False # Hàm kiểm tra tính an toàn của những ô trong cột def InCol(Board, col, num): for i in range(0,9): if (Board[i][col] == num): return True return False # Hàm kiểm tra tính an toàn của các ô trong một ô lớn 3x3 def InBox(Board, row, col, num): for i in range(0,3): for j in range(0,3): if (Board[i + row][j + col] == num): return True return False # Kiểm tra trạng thái an toàn tại một vị trí def isSafe(Board, row, col, num): return not InCol(Board, col, num) and not InRow(Board, row, num) and not InBox(Board, row - row % 3, col - col % 3, num) def SolveSudoku(Board): l=[0,0] if (not FindUnsignedLocation(Board, l)): return True row = l[0] col = l[1] for num in range(1,10): if (isSafe(Board, row, col, num)): Board[row][col] = num if (SolveSudoku(Board)): print Board break Board[row][col] = 0 return False Board = [[0, 9, 7, 0, 5, 0, 2, 1, 0], [0, 0, 0, 0, 8, 0, 4, 0, 0], [0, 0, 2, 0, 9, 7, 0, 6, 3], [0, 6, 0, 0, 0, 0, 3, 0, 9], [3, 0, 0, 4, 1, 9, 0, 0, 6], [7, 0, 9, 0, 0, 0, 0, 2, 0], [8, 3, 0, 2, 4, 0, 9, 0, 0], [0, 0, 6, 0, 3, 0, 0, 0, 0], [0, 5, 4, 0, 7, 0, 6, 3, 0]] SolveSudoku(Board)
We use the 9x9 matrix as an input of the above code. You can test with your own matrix with the above code to see the code runs properly.
Combine with the code in Part 2 and the code above. We can now solve the SUDOKU and show the result like this.
Combine with the code in Part 2 and the code above. We can now solve the SUDOKU and show the result like this.
Here is the final code
import cv2 import numpy as np import joblib import SUDOKU font = cv2.FONT_HERSHEY_SIMPLEX ratio2 = 3 kernel_size = 3 lowThreshold = 30 count = 1 clf = joblib.load('classifier.pkl') is_print = True cv2.namedWindow("SUDOKU Solver") vc = cv2.VideoCapture(0) if vc.isOpened(): # try to get the first frame rval, frame = vc.read() else: rval = False while rval: sudoku1 = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY) sudoku1 = cv2.blur(sudoku1, (1,1)) edges = cv2.Canny(sudoku1, lowThreshold, lowThreshold*ratio2, kernel_size) lines = cv2.HoughLines(edges, 2, cv2.cv.CV_PI /180, 300, 0, 0) if (lines is not None): lines = lines[0] lines = sorted(lines, key=lambda line:line[0]) diff_ngang = 0 diff_doc = 0 lines_1=[] Points=[] for rho,theta in lines: a = np.cos(theta) b = np.sin(theta) x0 = a*rho y0 = b*rho x1 = int(x0 + 1000*(-b)) y1 = int(y0 + 1000*(a)) x2 = int(x0 - 1000*(-b)) y2 = int(y0 - 1000*(a)) if (b>0.5): if(rho-diff_ngang>10): diff_ngang=rho lines_1.append([rho,theta, 0]) else: if(rho-diff_doc>10): diff_doc=rho lines_1.append([rho,theta, 1]) for i in range(len(lines_1)): if(lines_1[i][2] == 0): for j in range(len(lines_1)): if (lines_1[j][2]==1): theta1=lines_1[i][1] theta2=lines_1[j][1] p1=lines_1[i][0] p2=lines_1[j][0] xy = np.array([[np.cos(theta1), np.sin(theta1)], [np.cos(theta2), np.sin(theta2)]]) p = np.array([p1,p2]) res = np.linalg.solve(xy, p) Points.append(res) if(len(Points)==100): result = [] board = [] sudoku1 = cv2.adaptiveThreshold(sudoku1, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,cv2.THRESH_BINARY_INV, 101, 1) for i in range(0,9): for j in range(0,9): y1=int(Points[j+i*10][1]+5) y2=int(Points[j+i*10+11][1]-5) x1=int(Points[j+i*10][0]+5) x2=int(Points[j+i*10+11][0]-5) X = sudoku1[y1:y2,x1:x2] if(X.size!=0): X = cv2.resize(X, (36,36)) num = clf.predict(np.reshape(X, (1,-1))) #Collect the result result.append(num) board.append(num) # Reshape to 9x9 matrix result = np.reshape(result, (9,9)) board = np.reshape(board, (9,9)) # Solve the SUDOKU grid if(SUDOKU.SolveSudoku(result)): # If it can solve SUDOKU matrix, show the result for i in range(0,9): for j in range(0,9): if(array[i][j]==0): cv2.putText(frame,str(result[i][j]),(int(Points[j+i*10+10][0]+15), int(Points[j+i*10+10][1]-10)),font,1,(225,0,0),2) # Show the result picture cv2.imshow("Result", frame) cv2.imshow("SUDOKU Solver", frame) rval, frame = vc.read() key = cv2.waitKey(20) if key == 27: # exit on ESC break vc.release() cv2.destroyAllWindows()
Here is the end of this SUDOKU Solver series.
It's just the simple SUDOKU solver by taking pictures. I hope that you can improve this method or think about the new thing of applying machine learning and computer vision.
If you have any questions or comments, please feel free to contact me by email of Facebook.
All the training data and source code can be found in this GitHub link: https://github.com/huuquan1994/Sudoku-Solver
Enjoy your time!
References
[1] Backtracking Sudoku - http://www.geeksforgeeks.org/backtracking-set-7-suduku/
Thanks a lot!
ReplyDelete