Result and Improvement

Result

This project has successfully applied a "Backtracking" algorithm to solve Sudoku puzzles. It can solve puzzles of varying difficulty levels, from easy to hard, within one second. The project uses OpenCV to detect and automatically import the Sudoku grid, and Textract to extract numbers with a high level of accuracy.

This project is architected on the AWS Cloud, which provides high availability and scalability. The EC2 auto-scaling feature is used to adjust resources based on the number of requests. The web interface utilizes the Bootstrap library to make it more user-friendly.

Improvement

Algorithm

"Backtracking" is a simple algorithm that does not guarantee a solution for the Sudoku problem within a limited time. For example, for very hard level Sudoku puzzles, it can take up to 2 minutes to solve.

Consider using other methods, such as Constraint propagation or Heuristics, to optimize the Backtracking Algorithm. Another efficient algorithm for solving sudoku problem is Dancing links X algorithm.

   
[[0 0 0 0 0 0 3 0 0]
 [0 7 0 0 6 0 0 0 4]
 [0 0 0 0 0 0 5 0 1]
 [1 0 3 0 0 0 0 0 0]
 [0 0 0 0 8 0 7 0 0]
 [0 0 0 0 0 0 0 4 0]
 [0 0 0 1 0 3 0 0 0]
 [0 8 0 0 0 5 0 2 0]
   [0 0 0 2 0 0 0 0 0]] 
        

The above is an example of a very hard level of Sudoku puzzle.

Recognize

There are two issues with the recognition of the uploaded image: incorrect placement of recognized numbers and recognize of incorrect numbers.
• Incorrect placement: The location of the number in the grid is determined base on the calculation of the number’s location in recognized result. In case of slanted image, misplacement often occurs.
• Incorrect recognize number: The accuracy of number extraction depends on the input quality and pre-processing of images. To enhance recognition, adhere to the image upload guidelines and improve image pre-processing for more accurate results.

Conclusion

In conclusion, this project has successfully developed a solution for solving Sudoku puzzles using Backtracking algorithm and AWS Cloud services. This algorithm has solved puzzles of varying difficulty levels, and high level of accuracy in number extraction. However, in order to effectively handle high-level, both the solving algorithm and number recognition must be improved.