Solve any Sudoku in seconds

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

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

Github: https://github.com/IGNITE-Pathways/Sudoku