Automatic Sudoku Solver

• 

  A full Sudoku grid generated

Inspiration

The satisfying click of placing the correct number in a Sudoku grid whether it be on the mobile apps or newspapers has been a constant in my life. However, the true ignition point for this project came not just from solving puzzles themselves, but from a revelatory university lecture about propositional logic. We delved into logic and its wide impact on computer science, especially how precise SQL commands or even software verification rely heavily on logic. As an example, we were introduced to the logic of sudoku via the mathematical notation. This left me captivated and wondering about the very logic of generating Sudoku puzzles. Over the holidays, I researched online and spent some time looking through tutorials to understand the several ways in which a sudoku puzzle is generated, primarily focusing on the underlying mathematics. My ambition was to think and implement a program that would automatically solve a sudoku puzzle, regardless of how difficult the puzzle is! At first, I thought of implementing an AI algorithm that would learn through mistakes and solve the puzzle, however, after some research, I realised that for a deterministic problem like sudoku an AI algorithm 'doesn't have much to learn' and would be more suited for learning strategies rather than guaranteed solutions. This led me to a backtracking approach with constraint checks to build a more efficient solution. This program presented an ideal challenge for me as I have always been drawn to the beauty of deriving efficient solutions for complex problems and deriving a Sudoku puzzle from scratch seemed the perfect fit as it had some challenging dependencies despite looking simple from the outside.

What it does

A full breakdown of each method is available on the project's README.md but on a high level overview this is an efficient program that generates a valid and different Sudoku puzzle on every run and removes the desired/input number of elements from the grid to generate a puzzle which is then solved by recursively calling another method within the program!

How we built it

I developed this program from scratch in Python so no external libraries or packages were used! Although it is simple, I am proud of successfully implementing this project as it shows my resilience in finding good resources.

Challenges we ran into

One of the biggest challenges for me was when I needed to generate valid Sudoku puzzles. I say this because generating a puzzle with several constraints is not as easy as solving one itself. Through my research, I found out that there are several ways to generate Sudoku puzzles such as using patterns, backtracking forward etc. Deciding the best approach to implement was a difficult choice to make. After some more research I found an efficient and easy to comprehend way to generate a full grid. The next challenge came when I was implementing my solve_sudoku method which takes recursive calls to solve the puzzle. My program wasn't performing as intended and after some debugging I realised there was an issue with the logic in my helper methods. From this, I stepped back and tried to understand the fundamentals before jumping ahead. I learnt that robust testing of helper methods is equally crucial as insufficient testing can create issues in the long term and this is applicable to all software projects. Going forward, I will ensure that I take more time to check that the existing code works correctly before quickly moving onto the next section.

What we learned

Although this is a very simple project, I learnt a lot of things while implementing it. I am a beginner in Python so during the project, I was referring to online documentation and I am now more confident in coding in Python. I also improved my research skills and problem-solving ability and my successful implementation shows this.

Built With

• python