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:

## Comments