top of page

Solve any Sudoku in seconds

Updated: Mar 16

Sudoku, the popular number puzzle game, is not just a test of logic but also a great exercise in problem-solving for programmers. As someone deeply passionate about software development and AI, I took on the challenge of creating a program that could solve any Sudoku puzzle. Little did I know the journey ahead would be filled with numerous challenges, each requiring its own unique solution.


Challenge 1: Reading the Sudoku Grid


The first challenge I encountered was how to accurately read the Sudoku grid from an image. I started by building a custom AI model to read text from images. I experimented with various datasets from Kaggle and trained my model to recognize characters in the Sudoku grid. However, the results were not as accurate as I had hoped.


I then discovered Tesseract, an OCR engine that uses LSTM-based neural networks to recognize character patterns. Using the Python version of Tesseract, I was able to extract the text from the Sudoku grid with much better accuracy. However, I soon realized that the scanned Sudoku grid was not a perfect square, which impacted the OCR's efficacy.

def get_digit(self, c2, bm, warped1, cnts):
    # To get the digit at the particular cell
    num = []        
    for i in range(0,9):
        for j in range(0,9):
            x1,y1 = bm[i][j] # bm[0] row1 
            x2,y2 = bm[i+1][j+1]
            
            crop = warped1[int(x1):int(x2),int(y1):int(y2)]
            crop = imutils.resize(crop, height=69,width=69)
            c2 = cv.cvtColor(crop, cv.COLOR_BGR2GRAY)
            c2 = cv.adaptiveThreshold(c2,255,cv.ADAPTIVE_THRESH_GAUSSIAN_C, cv.THRESH_BINARY_INV,11,2)
            c2= cv.copyMakeBorder(c2,5,5,5,5,cv.BORDER_CONSTANT,value=(0,0,0))
            no = 0
            shape=c2.shape
            w,h=shape[1], shape[0]
            c2 = c2[14:70,15:62]
            contour, hier = cv.findContours(c2,cv.RETR_LIST,cv.CHAIN_APPROX_SIMPLE)
            if cnts is not None:
                cnts = sorted(contour, key=cv.contourArea,reverse=True)[:1]
            for cnt in cnts:
                x,y,w,h = cv.boundingRect(cnt)
                aspect_ratio = w/h
                area = cv.contourArea(cnt)
                print("Area", area, "Shape", cnt.shape[0], "Aspect", aspect_ratio)
                if area>70 and cnt.shape[0]>10 and aspect_ratio>0.2 and aspect_ratio<=0.9: 
                    c2 = self.find_largest_feature(c2)
                    contour, hier = cv.findContours (c2,cv.RETR_LIST,cv.CHAIN_APPROX_SIMPLE)
                    cnts = sorted(contour, key=cv.contourArea,reverse=True)[:1]
                    for cnt in cnts:
                        rect = cv.boundingRect(cnt)
                        c2 = c2[rect[1]:rect[3]+rect[1],rect[0]:rect[2]+rect[0]]
                        c2= cv.copyMakeBorder(c2,5,5,5,5,cv.BORDER_CONSTANT,value=(0,0,0))
                        # self.show_image("image_to_num", c2)
                    no = self.image_to_num(c2)
                    print("Found Number", no)
            num.append(no)
    return c2, num

Challenge 2: Skewed Square boxes

Scan Sudoku

To overcome this hurdle, I turned to OpenCV, a powerful computer vision library. I was able to implement a four-point perspective transform to correct the skewed grid and convert it into a perfect square. This transformation greatly improved the OCR's accuracy and allowed me to move forward with the next steps.



def four_point_transform(self, image, rect, dst, width, height):
      M = cv.getPerspectiveTransform(rect, dst)
      warped = cv.warpPerspective(image, M, (width, height))
      return warped

Challenge 3: Rendering and Overlaying the Sudoku Grid


With the Sudoku grid successfully extracted, the next challenge was to render it and overlay it with the actual solution. Fortunately, I had prior experience working with Pygame, and I was able to render the Sudoku grid and display it on the screen, making it easier to visualize the puzzle and its solution.


Challenge 4: Solving the Sudoku


The final challenge was to actually solve the Sudoku puzzle. I found that a simple back-propagation algorithm could efficiently solve Sudoku puzzles. I implemented this algorithm, which recursively fills in each empty cell with a valid number based on the Sudoku rules, until the entire puzzle is solved.

def check_row_column_zone(self, grid, row, col, num):
        # Check occurrence of num in row
        for y in range(9):
            if grid[row][y][0] == num:
                return False
        # Check occurrence of num in column
        for x in range(9):
            if grid[x][col][0] == num:
                return False
        # Check occurrence of num in zone
        startRow = row - row % 3
        startCol = col - col % 3
        for i in range(3):
            for j in range(3):
                if grid[i + startRow][j + startCol][0] == num:
                    return False
        return True

def solve_sudoku_from_pos(self, grid, row, col, stack):
        print("."*stack)  
        self.display_sudoku(grid)
        pygame.display.flip()

        if (row == M - 1 and col == M):
            return True
        if col == M:
            row += 1
            col = 0
        if grid[row][col][0] > 0:
            return self.solve_sudoku_from_pos(grid, row, col + 1, stack + 1)
        
        for num in range(1, M + 1, 1): 
            if self.check_row_column_zone(grid, row, col, num):
                grid[row][col] = (num,1)
                if self.solve_sudoku_from_pos(grid, row, col + 1, stack + 1):
                    return True
            grid[row][col] = (0,0)
        return False

Conclusion


Creating a software program to solve any Sudoku puzzle was a challenging yet rewarding experience. By leveraging AI, computer vision, and pygame, I was able to overcome various hurdles and develop a program that can efficiently solve Sudoku puzzles. This project not only improved my programming skills but also deepened my appreciation for the complexities of puzzle-solving algorithms.


Here is the sneak peak:



 

Get complete source code


Recent Posts

See All

コメント


Subscribe

Subscribe to our mailing list for regular updates on news, events, insightful blogs, and free code!

Thanks for subscribing!

bottom of page