Sriram's Blog: Sudoku Solver

Hello Everyone!. Ever got bored of solving sudoku's. Then for you the solution is here, to create something that could solve and show us the solved sudoku . I have done it using python and an opencv python library. The functions used in this can be easily found out in the Opencv documentation refer them or comment below for any further clarification.

In this I have used KNearest(), a machine learning algorithm that is available in Opencv, which can be used to recognize stuffs but here I have used it to recognize the digits in the sudoku. Well Before that you have create your training data, which will be used for recognizing the digits.

Input Image

Int MAIN():

This is the basic sudoku solver which does not require any complex image processing techniques because the image taken is a binary image without any noise. Hence just finding the contours will satisfy the needs.

Let's first look at training the OCR for recognizing the numbers in the given input image

Basically, training the OCR requires hundreds of images for it to be used in recognizing images of different types. Since the images we use are only computer typed digits and the given input image is assumed to be taken in the binary form we are going to use only 1 image for each digit. I hope this enough for recognizing images which are in the binary form without any noise. Let's look forward towards training the OCR.

The first Part of the code reads the input image and converts the given image into gray.

The we find contours in the given image with the arguments saying the function to find contours in the tree form and to make simple approximation on the contours found, hence only minimum number of points required to draw the contour are saved.

from matplotlib import pyplot as plt
import numpy as np
import cv2
img = cv2.imread('sudoku.png',1)
frame=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
samples=np.empty((0,100))
responses=[]
keys = [i for i in range(48,58)]
_,cnt,hr = cv2.findContours(frame,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
#cv2.drawContours(img,cnt,-1,(255,0,0),2)

Image with contours

The below code snippet extracts each and every individual box of the sudoku and checks out whether the box considered has any child contour. If it does then the box having the child is extracted out and the user is asked to enter the response of the extracted image and the entered response is recorded in a variable. The sample used is resized into 10X10 image which is again reshaped into row array and its type converted and saved into a file. It's done so because the file size is reduced when the size of the image is small.

The sample image and its corresponding response is saved into a npz file.

Thus training the OCR can be accomplished.

count=0
numb=[]
for i in range(len(cnt)):
 area=cv2.contourArea(cnt[i])
 if area>=40000:
  x,y,w,z=hr[0][i]
  if w!=-1:
   a,b,c,d=cv2.boundingRect(cnt[w])
   print c,d
   errx=100-c
   erry=180-d
   b=b-(erry/2)
   a=a-(errx/2)
   c=100
   d=180
   roi=frame[b:b+d,a:a+c]
   cv2.imshow("1",roi)
   cv2.rectangle(img,(a,b),(a+c,b+d),(0,255,0),4)
   q=cv2.resize(img,(400,400))
   cv2.imshow("frame",q)
   count=count+1
   key=cv2.waitKey(0)
   if key in keys:
    responses.append(int(chr(key)))
    roismall=cv2.resize(roi,(10,10))
    roismall=roismall.reshape(1,100)
    samples=np.append(samples,roismall,0)
    if key not in numb:
     numb.append(key)
     picname= chr(key)+".png"
     cv2.imwrite(picname,img[b:b+d,a:a+c])
plt.imshow(img),plt.title("frame")
plt.xticks(),plt.yticks()
plt.show()
cv2.waitKey(0)
print count
samples=np.array(samples,np.float32)
responses = np.array(responses,np.float32)
responses = responses.reshape((responses.size,1))
np.savez('knn.npz',train=samples,traindata=responses)
print "training complete"

SudokuTrain.py

Part-2:

The next part is loading the training data and extracting the individual boxes and processing them by converting the given images to the form it has been saved and then giving it to the findNearest function which gives the nearest out an array containing the calculated result. The values recognized are stored in a matrix. The matrix is then given to the sudoku solving algorithm. The algorithm first checks out for an empty cell and assigns it a value from 1 to 9 which is passed to the a function which checks the validity. The function checks whether the assigned value is valid or not, if it is valid the recursively calls itself which again does the same job. If suppose the is not compatible with any of the values assigned for the function returns to its parent function which was recursively called and then the previous function assigns another value to and the process repeats itself.

Output Image

from matplotlib import pyplot as plt
import numpy as np
import cv2
img = cv2.imread('sudoku\sudoku.png',1)
deflt="D:\sudoku\\"
frame=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
print frame.shape
samples=np.empty((0,100))
responses=[]
keys = [i for i in range(48,58)]
_,cnt,hr = cv2.findContours(frame,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
cv2.drawContours(img,cnt,-1,(255,0,0),2)
count=0
model= cv2.ml.KNearest_create()
with np.load('D:\Sriram\pyprograms\sudoku\knn.npz') as data:
 print data.files
 train1=data['train']
 train_labels= data['traindata']
 print train1
 print train_labels
model.train(train1,cv2.ml.ROW_SAMPLE,train_labels)
matrix=np.zeros((9,9),np.uint8)
print matrix
for i in range(len(cnt)):
 area=cv2.contourArea(cnt[i])
 if area>=40000:
  x,y,w,z=hr[0][i]
  if w!=-1:
   a,b,c,d=cv2.boundingRect(cnt[w])
   #print c,d
   errx=100-c
   erry=180-d
   b=b-int(erry/2)
   a=a-int(errx/2)
   c=100
   d=180
   roi=frame[b:b+d,a:a+c]
   cv2.rectangle(img,(a,b),(a+c,b+d),(255,0,0),4)
   q=cv2.resize(img,(400,400))
   cv2.imshow("frame",q)
   roismall=cv2.resize(roi,(10,10))
   roismall=roismall.reshape(1,100)
   roismall1=np.float32(roismall)
   r=model.findNearest(roismall1,1)
   print int(r[1][0])
   count=count+1
   count1=81-count
   row=int(count1/9)
   col=int(count1%9)
   matrix[row][col]=int(r[1][0])
  else:
   count=count+1
   count1=81-count
   row=int(count1/9)
   col=int(count1%9)
   matrix[row][col]=0
print count
#print matrix
def nextcell(matrix,i,j):
 for x in range(i,9):
  for y in range(j,9):
   if matrix[x][y]==0:
    return x,y
 for x in range(0,9):
  for y in range(0,9):
   if matrix[x][y]==0:
    return x,y
 return -1,-1
def checkcell(matrix,i,j,val):
 rowcheck=colcheck=1
 for x in range(9):
  if val==matrix[i][x]:
   rowcheck=0
 if rowcheck==1:
  for x in range(9):
   if val==matrix[x][j]:
    colcheck=0
 if colcheck==1 and rowcheck==1:
  topx=3*(i/3)
  topy=3*(j/3)
  for x in range(topx,topx+3):
   for y in range(topy,topy+3):
    if matrix[x][y]==val:
     return False
  return True
 return False
def sudokusolve(matrix,i=0,j=0):
 i,j=nextcell(matrix,i,j)
 if i==-1:
  return True
 for val in range(1,10):
  if checkcell(matrix,i,j,val):
   matrix[i][j]=val
   if sudokusolve(matrix,i,j):
    return True
   matrix[i][j]=0
 return False

if sudokusolve(matrix,0,0):
 print matrix
 print "Eureka"
else:
 print "Could not solve"
count=0
val=0
for i in range(len(cnt)):
 area=cv2.contourArea(cnt[i])
 if area>=40000:
  x,y,w,z=hr[0][i]
  if w!=-1:
   count=count+1
   continue
  else:
   count=count+1
   count1=81-count
   row=int(count1/9)
   col=int(count1%9)
   val=matrix[row][col]
   s=str(val)
   a,b,c,d=cv2.boundingRect(cnt[i])
   im=cv2.imread(deflt+s+".png",1)
   img[b+10:b+190,a+50:a+150]=im
plt.imshow(img),plt.title("frame")
plt.xticks([]),plt.yticks([])
plt.show()
cv2.destroyAllWindows()

Test.py

Thank you
Happy Coding.
Cheers!!!
#IIE

Sriram's Blog

Sunday, December 6, 2015

Sudoku Solver

No comments:

Post a Comment