ECE 5990 | Sudoku Solver

Objective

The objective of this project was to create something which will be fun to work with and at the same time allows us to apply all the concepts learned in the class ECE 5725 to create a Sudoku Solver using Raspberry Pi and PiTFT. Another goal was to use as less additional hardware as possible and only use the components we have been using for the labs.

Introduction

We all know how to solve a Sudoku puzzle. But what if we can use the power of Raspberry Pi to solve many complicated Sudoku puzzles within seconds? We use Pi Camera to read a Sudoku puzzle, then display this incomplete puzzle on PiTFT screen. Then we use our algorithm programmed in Python to solve this puzzle and display the completed puzzle back on the TFT screen again. We also tried different approaches to write a Sudoku Solver algorithm like Brute Force, Backtracking etc. We ended up implementing an improved version of backtracking algorithm.

This is our overall system setup

Design and Testing

List of Components:

1. Raspberry Pi 2 Model B

2. 2.8 Inch PiTFT

3. PiCamera

The project was divided into three different phases:

A. Read the images using PiCamera

B. Separately develop an algorithm to solve the Sudoku puzzle

C. Finally, integrate both the designs to create a Complete Sudoku solver

A. Read the images using PiCamera

The display of the game is fairly simple for our final project. It has an empty Sudoku grid and two buttons: READ and SOLVE buttons. Unfortunately, the setup of the touchscreen was not working, therefore we also implemented hardware buttons placed on the side of the PiTFT. When the button number 17 is pressed, it quits the game. When the button number 22 is pressed, it calls the sudokuCam.py function, which extracts the array from the camera explained thoroughly later in the report. Once the array is extracted it is displayed on the screen. The picture below shows the display at this stage.

Now, the Sudoku is ready to be solved. When the SOLVE button is pressed, it sends the initial array to sudokuSolve.py module which solves the Sudoku and returns the final array. Then, the display prints the solved numbers in read to the screen. The game does not quit until the QUIT button is pressed. If the READ button is pressed again, it reads the Sudoku again according to the Sudoku placed in front of the camera.

Extracting the Sudoku Grid Array from the Camera

For this project we used a picamera. The camera is attached to Raspberry Pi and the Sudoku is placed in front of the camera. In order for algorithm to work the distance between the camera and the Sudoku needs to be fixed. When the READ button is pressed on the screen (touch screen or the button) the camera takes a picture. This picture is then cropped to get rid of the unnecessary pixels such as the box, the table and the pins. This cropped picture is sent through a filter which changes the pixel values in a way that, the grid is all red, the numbers are all black and the rest is all white. The output of this filter is shown below.

Our algorithm then applies edge detection to get the right, left, top, bottom corners. In order to find these corners our algorithm finds the leftmost red pixel and the same thing for the other corners. Then this image is resized to 1080x1080 picture. Also, the grid has no purpose after this point; therefore, all the red pixels are turned into white as well. The output of this calculation is the image below.

This image is 1080x1080. We know that in Sudoku there are 9 rows and 9 columns. So ideally each number is inside a 120x120 area. So this image is divided into 120x120 squares which represent the number and these squares are saved. The result of this below is shown below.

These images are not good for comparison as the numbers are not same size and not spotted at the same place. Therefore, we put each of these images through another edge detection to find the edges of each of these numbers. Then, these images with the edges are resized to 20x40 images. The result of this step is shown below.

Now the images are ready for comparison. Also, for our algorithm to work, we turned the white spaces into red, which show that there is no number in that square of the Sudoku. There are 4 reference images for each number. An example of reference set for number 7 is shown below.

B. Sudoku Solver Algorithm

Even though the Brute Force algorithm is guaranteed to yield a solution for any solvable sudoku, we decided to implement Backtracking algorithm since it is much faster. But even with backtracking, we are still using a superset of 1 to 9 numbers to put in an empty cell. Whenever we encounter a cell for which we have exhausted all the 9 entries and still do not have a solution, we set the value of current cell to zero and then we backtrack to the previous cell and increment the number in superset by 1.

This approach is definitely faster than Brute Force, but we can still improve the runtime of this algorithm by making use of the entries present in the incomplete sudoku. That is we reduce the size of superset to reach the solution faster. To do this we first create a list of all the possible entries for each and every empty cell. We get these possible entries by making use of the constraints put the Sudoku puzzle i.e. no two entries in a column or a row or a 3x3 box should be the same. So we create a list, each with 9 entries corresponding to the each entry in the cell. Initially all the entries in the list are 1’s i.e. all the numbers from 1-9 are possible for a particular empty cell. Then we call a function which checks for conflicts in a corresponding row, column and a 3x3 box. After this check, we will have few 0’s in the possible entries list and the remaining numbers are the possible entries. In this we are able to reduce the size of our superset.

Now when we backtrack, we do not need to check all the numbers from 1-10. We just check against the entries present in the superset and can reach the solution quickly. Note that in the previous version of backtracking, we were performing a check for a possible conflict on every iteration but with improved version, we do this check only once.

This is the overall algorithm:

C. Final Integration

After rigorously testing our hardware for reading the sudoku images and separately testing the sudoku solver algorithm for different sudoku puzzles like easy puzzles, hard puzzles, puzzles with invalid entries, puzzles with valid but duplicate entries, puzzles with all valid entries but no solution, we were ready to integrate both the designs. To be able to call ‘sudokuSolve’ from ‘sudokuDisplay’ program, we made some changes to our ‘sudokuSolve’ program and it is slightly different from what is shown in the Code appendix.

Results

This is the final result that we get for the puzzle which was introduced earlier. We also tested the entire system with couple of other puzzle images and we got the correct results on those puzzles as well. For the purpose of this report, we are only showing the result of one puzzle.

Problems faced ....

One problem that we spent a lot of time debugging on was the issue with PiTFT touch screen. We were getting 100’s of hits even for couple a of touches to the screen and that to with coordinates all mixed up. This was not a new problem as we all know, since many groups during lab sessions faced the exact similar problem. The very first attempt in trying to solve this problem was to check the environment variables for any typographical errors. It turned out that there was indeed a typographical error since environment variables ‘SDL_MOUSEDEV’ and ‘SDL_MOUSEDRV’ look very similar. After fixing this, we were confident that we have solved this problem, but surprisingly we were still getting the same irregular touch screen behaviour. As a way around, we ended up using the on screen buttons for ‘READ’ and ‘SOLVE’ functionality.

Another problem was with reading the images using PiCamera. As we decided to go with simple implementation to read the images, we decided to fix the distance between the camera and the sudoku image. Even the slightest of change in the distance or the angle at which the camera was placed resulted in the image which could not be used for the edge detection.

Also for the Sudoku solver algorithm, differentiating between the valid puzzle with no solution and invalid puzzle with no solution was a little tricky. We solved this problem by simple adding initial validation on the incomplete sudoku puzzle. If the puzzle passes all the validation but still results in no solution, then we know that the puzzle can not be solved.

Future work and Conclusion

We had planned to implement a functionality to show the numbers on the screen as the algorithm traverses each empty cell or sometime backtracks to fill the sudoku grid. This would give us more intuitive understanding of how the algorithm actually works. Since for easy puzzles the algorithm finds the solution very quickly, we will need to incorporate some delay routine to show the numbers in the correct sequence.

During the demo, we only used valid puzzles with unique solutions. Since we have already added all the validation in the Sudoku solver algorithm to detect invalid puzzles or valid puzzles with no solution, we can add functionality to show error messages on the PiTFT screen.

We can still optimize the Sudoku solver algorithm by further exploiting the structure in the incomplete sudoku. For example, if the number 5 is present on the line 1 in the left box and on line 2 in the middle box, then it can appear in the right box only on the line three. In this way we can further reduce the size of the superset.

Division of Work:

The project responsibilities were clearly divided as Hardware and Software components. Baturay Turkman worked on the Hardware component i.e. reading the sudoku images to display on the screen. Ashish Shinde worked on the Software component i.e. to solve the incomplete sudoku read in the previous part. For final report, Baturay Turkman worked on the ‘Read the images using PiCamera’ section and Ashish Shinde worked on rest of the sections and the website template.

Appendix

####################################################################
# Final Project Dec 3rd,2016                                       #
# Sudoku Solver - Array Extraction                                 #
# Ashish Shinde(ahs278) Baturay Turkman(bt268)                     #
####################################################################

from picamera import PiCamera
from picamera.array import PiRGBArray
import time
from PIL import Image

#Creates the camera
camera = PiCamera()  
camera.rotation = 180
camera.resolution = (2592, 1944)
camera.hflip = True
  #camera.color_effects = (128, 128)

def readGrid():

  print "Start reading..."
# Captures the image from the camera
  camera.capture('/home/pi/Desktop/sudokuImage.jpg')
  
# Crops the image to get rid of unnesseray pixels  
  im      = Image.open('/home/pi/Desktop/sudokuImage.jpg')
  cropped = im.crop( (400, 100, 1800, 1500) )
   
  cropped.save('/home/pi/Desktop/cropped.jpg')
  pix = cropped.load()
  cropsize = 1400 
 
 #Turns the cropped image into a black and white image with the grid outlines being red
  for x in range(0, cropsize):
    for y in range (0, cropsize):
      if ((pix[x,y][0] > 90) and (pix[x,y][1] < 90) and (pix[x,y][2] < 90)):
        pix[x,y] = (255,0,0)
      elif ((pix[x,y][0] < 90) and (pix[x,y][1] < 90) and (pix[x,y][2] < 90)):
        pix[x,y] = (0,0,0)
      else:
        pix[x,y] = (255, 255, 255)

  cropped.save('/home/pi/Desktop/cropped_red.jpg')

  top = cropsize
  bottom = 0
  left = cropsize
  right = 0

#Edge detection to find the corners of the red grid, then turns the red pixels into white
  for x in range(0, cropsize):
    for y in range (0, cropsize):
      if(pix[x,y][0] == 255 and pix[x,y][1] == 0 and pix[x,y][2] == 0 ):
        if (x < left)  : left   = x
        if (x > right) : right  = x
        if (y < top)   : top    = y
        if (y > bottom): bottom = y
        pix[x,y] = (255, 255, 255) 
  
  print "corners"
  print top
  print bottom
  print right
  print left
  
  #Crops the image from the edges and resize it to a 1080x1080 image
  cropd  = cropped.crop( (left, top, right, bottom) )
  cropds = cropd.resize((1080, 1080)) 
  cropds.save('/home/pi/Desktop/crop.jpg')
  
  edgex = 120#(right - left) / 9
  edgey = 120#(bottom - top) / 9 
  
  topn    = edgey
  bottomn = 0
  leftn   = edgex
  rightn  = 0
  
  initGrid   = [[0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],

                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],
               ]
  
  
  # 1-3 2-3 3-4 4-2 5-2 6-2 7-3 8-2 9-3
  
  for j in range(0, 9):
    for i in range(0, 9):
      
      # Crops each square by 120x120 images to grab each image
      path2 = '/home/pi/Desktop/sudoku/array2/sq_{}_{}.jpg'.format(j+1, i+1)

      path = '/home/pi/Desktop/sudoku/array/sq_{}_{}.jpg'.format(j+1, i+1)
      crp  = cropds.crop((i*edgex-2, j*edgey+2, (i+1)*edgex-2, (j+1)*edgey+2))
      pix = crp.load()

      crp.save(path2)

      top    = edgey-2
      bottom = 2
      left   = edgex-2
      right  = 2
      empty  = 0

      #Edge detection to find the corners of the number and save each square by 20x40
      for x in range(2, edgex-2):
        for y in range (2, edgey-2):
          if(pix[x,y][0] == 0 and pix[x,y][1] == 0 and pix[x,y][2] == 0 ):
            if (x < left)  : left   = x
            if (x > right) : right  = x
            if (y < top)   : top    = y
            if (y > bottom): bottom = y
          if (pix[x,y][0] == 255):
            empty = empty + 1
      if (empty > 13300):
        for x in range(2, edgex-2):
          for y in range(2, edgey-2):
            pix[x,y] = (100,0,0)
        crp3  = crp.resize((20, 40)) 
        crp3.save(path)
      else:
        crp2  = crp.crop((left, top, right, bottom))
        crp3  = crp2.resize((20, 40)) 
        crp3.save(path)
     
      pix = crp3.load()
      dif = 1000000
 
      #Compares each 20x40 number images to reference images and does pixel comparison
      #Finds the least different number and saves that into the array
      difitem = 0
      for k in range(0,10):
        for l in range(1,5):
          path = '/home/pi/Desktop/sudoku/{}/{}.jpg'.format(k, l)
          tset = Image.open(path)
          pixt = tset.load()
          diftemp = 0
          for x in range(0, 20):
            for y in range(0, 40):
              if (pix[x,y][0] != pixt[x,y][0]):
                diftemp = diftemp + 1
          #print diftemp
          if (diftemp < dif):
            dif     = diftemp
            difitem = k
 
            if (diftemp < dif):
              dif     = diftemp
              difitem = k
  
      initGrid[i][j] = difitem   
  #Returns the array    
  print "Done reading." 
  print initGrid  
  return initGrid

####################################################################
# Final Project Dec 3rd,2016                                       #
# Sudoku Solver - Game Display                                     #
# Ashish Shinde(ahs278) Baturay Turkman(bt268)                     #
####################################################################

import sys, pygame, os, copy
import RPi.GPIO as GPIO
from sudokuCam import readGrid
from sudokuSolve import big

# Set variables for touchscreen
os.putenv('SDL_FBDEV', '/dev/fb1')
os.putenv('SDL_MOUSEDRV', 'TSLIB')
os.putenv('SDL_MOUSEDRV', '/dev/input/touchscreen')
os.putenv('SDL_VIDEODRIVER', 'fbcon')

pygame.init()

GPIO.setmode(GPIO.BCM)
pygame.mouse.set_visible(True)


#Creates button for read, solve, quit buttons
GPIO.setup(17, GPIO.IN, pull_up_down = GPIO.PUD_UP)
GPIO.setup(22, GPIO.IN, pull_up_down = GPIO.PUD_UP)
GPIO.setup(23, GPIO.IN, pull_up_down = GPIO.PUD_UP)

size     = 320, 200
black    = 0  , 0  , 0
white    = 255, 255, 255
blue     = 0  , 0  , 255
red      = 255, 0  , 0
green    = 0  , 155, 0
bgrnd    = 200, 200, 0

screen   = pygame.display.set_mode (size)
grid1    = pygame.image.load('/home/pi/Desktop/grid.png').convert()
grid     = pygame.transform.scale(grid1, (160, 160))

my_font  = pygame.font.Font(None, 23)
x        = 0
y        = 0

text_slv = my_font.render("SOLVE", True, green)
text_rd  = my_font.render("READ", True,  blue)

text0    = my_font.render("SUDOKU", True, black)
text1    = my_font.render("SOLVER", True, black)

# This function displays the initial grid array extracted on display
def init_grid(initGrid):
  screen.blit(grid1, (10, 7))
  for x in range(0, 9):
    for y in range(0, 9):
      if (initGrid[x][y] != 0):
        string = str(initGrid[x][y])
        txt1   = my_font.render(string, True, black)  
        # Each pixel is printed on the grid at the right place
        screen.blit(txt1, (20 + x*20, 12 + y*20))
 
 # This function displays the final grid array solved with our algorithm
def final_grid(initGrid, finalGrid):
  for x in range(0, 9):
    for y in range(0, 9):
      if (initGrid[x][y] == 0):
        string = str(finalGrid[x][y])
        txt1   = my_font.render(string, True, red)  
        screen.blit(txt1, (20 + x*20, 12 + y*20))
 
initGrid  = [[0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0], 
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
            ]


finalGrid = [[0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0], 
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
             [0,0,0,0,0,0,0,0,0],
            ]

#Displays the empty grid 
screen.fill(bgrnd)
screen.blit(grid1, (10, 7))

#Creates and display Read Button
pygame.draw.rect(screen, white, (230, 80, 60, 25), 0)
pygame.draw.rect(screen, black, (230, 80, 60, 25), 2)
screen.blit(text_rd, (239, 84))

#Creates and displays the Solve button
pygame.draw.rect(screen, white, (230, 120, 60, 25), 0)
pygame.draw.rect(screen, black, (230, 120, 60, 25), 2)
screen.blit(text_slv, (234, 124))

#Displays the name of the app "Sudoku Solver"
screen.blit(text0, (230, 24))
screen.blit(text1, (230, 44))

var = True
while var:

#Quit button quits the game
  if (not GPIO.input(17) ):
    var = False

#When read button is pressed, it extracts the array from the camera
  if (not GPIO.input(22) ):
    screen.blit(grid1, (10, 7))
    initGrid = readGrid()
    screen.blit(grid1, (10, 7))
    init_grid(initGrid)

#When solve button is pressed, it solves the sudoku and displays the result
  if (not GPIO.input(23) ):
    inputGrid = copy.deepcopy(initGrid) 
    finalGrid = big(inputGrid)
    final_grid(initGrid, finalGrid)

  for event in pygame.event.get():
    if event.type == pygame.QUIT: sys.exit()  
    elif event.type == pygame.MOUSEBUTTONDOWN:
      pos = pygame.mouse.get_pos()
    elif event.type == pygame.MOUSEBUTTONUP:
      pos = pygame.mouse.get_pos()
      x,y = pos
#When read button is pressed, it extracts the array from the camera (touchscreen)
      if  ((x>230) and (x<290) and (y>80) and (y<105)) :
        screen.blit(grid1, (10, 7))
        initGrid = readGrid()
        screen.blit(grid1, (10, 7))
        init_grid(initGrid)

#When solve button is pressed, it solves the sudoku and displays the result (touchscreen)
      elif((x>230) and (x<290) and (y>120) and (y<145)) :
        inputGrid = copy.deepcopy(initGrid) 
        finalGrid = big(inputGrid)
        final_grid(initGrid, finalGrid)

  pygame.display.flip()

####################################################################
# Final Project Dec 3rd,2016                                       #
# Sudoku Solver – Sudoku Solver                                    #
# Ashish Shinde(ahs278) Baturay Turkman(bt268)                     #
####################################################################

# Function to print the board
def print_board(board):
    for x in range(9):
        for y in range(9):
	    print board[x][y],
	print "\n "

# Get the index of empty cell
def find_empty(board,l):
    for x in range(9):
        for y in range(9):
	    if(board[x][y] == 0):
	        lst[0] = x
	        lst[1] = y
	        return True
    return False

#Check for conflicts in Row, Column & 3x3 boxes 
def row_conflict(board,r,n):
    for i in range(9):
	if(board[r][i] == n):
	    return True
    return False
		
def col_conflict(board,c,n):
    for i in range(9):
	if(board[i][c] == n):
	    return True
    return False

def box_conflict(board,r,c,n):
    for i in range(3):
	for j in range(3):
	    if(board[r+i][j+c] == n):
		return True
    return False

# Return True if no conflict
def no_conflict(board,r,c,n):
    return not row_conflict(board,r,n) and not col_conflict(board,c,n) and not box_conflict(board,r-r%3,c-c%3,n)


# Function to find possible entries
def possible_entries(board,i,j):
    possible_entries = {}
    for x in range(1,10):
	possible_entries[x] = 1
    for y in range(0,9):
	if board[i][y] != 0:
	    possible_entries[board[i][y]] = 0
    for x in range(0,9):
	if board[x][j] != 0:
	    possible_entries[board[x][j]] = 0
    for x in range(i-i%3,(i-i%3)+3):
	for y in range(j-j%3,(j-j%3)+3):
	    if board[x][y] != 0:
		possible_entries[board[x][y]] = 0
    return possible_entries


# This function is called recursively
def solve_sudoku(board):
    lst = [0,0]
    if(not find_empty(board,lst)):
	return True
    r = lst[0]
    c = lst[1]

    possibilities = possible_entries(board,r,c)

    for n in range(1,10):
        if possibilities[n] == 1:
	    if no_conflict(board,r,c,n):	    
	        board[r][c] = n
	        if(solve_sudoku(board)):
		    return True
	        board[r][c] = 0
    return False
	

# Validation for invalid puzzles
# This function is called from sudokuDisplay.py
def big(board):
    var = True
    for x in range(9):
        for y in range(9):
	    if (board[x][y] < 0 or board[x][y] > 9):
	 	 var = False
                 print " "
                 print "Invalid number at Row:%d Col:%d"%(x+1,y+1)
		 print " " 
	       
    if var:
	for x in range (0,9):
	    count_row = 0
	    j = 0
            while(j != 8):
		for y in range(j+1,9):
		    if (board[x][j] == board[x][y]) and (board[x][y] != 0):
			count_row = count_row + 1
                        var = False
			break
                j = j + 1
	    if(count_row):
		print "%d duplicate number(s) in Row:%d"%(count_row,x+1)

	for y in range (0,9):
	    count_col = 0
	    j = 0
            while(j != 8):
		for x in range(j+1,9):
		    if (board[j][y] == board[x][y]) and (board[x][y] != 0):
			count_col = count_col + 1
                        var = False
			break
                j = j + 1
	    if(count_col):
		print "%d duplicate number(s) in Col:%d"%(count_col,y+1)
	
	for x in range (0,3):
	    for y in range (0,3):
		i = 0
  		j = 0
		count_box = 0
		while(i != 2 and j != 2):
		    for x in range(i+1,3):
			for y in range(j+1,3):
			    if (board[i][j] == board[x][y]) and (board[x][y] != 0):
				count_box = count_box + 1
				var = False
				break
			j = j + 1
		    i = i + 1
		if(count_box):
		    print "duplicate number in the boxes" 

    if(solve_sudoku(board) and var):
	print " "
	print "Sudoku Solved :) "
        print " "
	print_board(board)
        return board
    else:
	print "Sudoku has no solution :("
	print " "
        return -1

def main():

    
    board = [[0 for x in range(9)] for x in range(9)]
    board = [
	     [7,3,0,0,0,5,0,0,0],
	     [0,4,0,0,6,0,0,0,0],
             [0,0,1,0,0,9,0,5,0],
             [0,5,0,0,0,1,0,9,2],
	     [0,0,0,0,0,0,0,0,0],
	     [0,0,0,0,4,7,5,0,8],
             [3,2,0,0,7,0,0,0,0],
             [6,9,0,0,0,0,2,0,0],
	     [0,0,0,6,3,0,4,0,0]
	    ]  
    print " "
    print "Incomplete Sudoku"
    print " "
    print_board(board)
    
    big(board)

main()

Cost Analysis

Lab Components used :

Raspberry Pi 2 Model B ($35)

2.8 Inch PiTFT SCreen ($35)

Total = $80

Components Purchased :

PiCamera ($5)

Sudoku Solver

Ashish Shinde ahs278

Baturay Turkman bt268