Sudoku Library

Sudoku Solving

After gaining a lot of programming experience in the past few years, I wanted to see how much my skills have improved. What can be a better way to do this than to work on a problem I have already attempted to solve once? This problem is writing a Sudoku solver. It needs to reliably solve sudoku puzzles in a reasonable time. At the time, this was a bonus assignment for the programming seminar at my university. In the following, I describe what new skills have helped me the most, how I managed to go beyond the original assignment and show you my results.

Language

For this project I use Java. It is not that I cannot use any other object-oriented language, but Java is the language I currently work with. C was the mandatory language in the class. I think using C helped us to understand concepts like working directly with the memory and it is useful for programming microcontrollers. However, Java brings with it very useful tools, that make the job easier. To create and manage the project I use Maven. Also, I use Eclipse IDE for development and testing instead of the text editors I used in the university, which did not offer more than syntax highlighting.

Test-driven development

Another useful habit is using Test-driven development. For a long time, I was not a fan of tests.  I considered them to be a waste of time and could not understand how they would be of help. It was not until I saw them working on real projects and saving the developers a lot of time and tedious searching through code, that I became a believer. The Sudoku solver project is a great opportunity to write a few tests and see them helping you to achieve your goal. All you need is some input data in the form of unsolved puzzles and you can test your creation with a few clicks in the IDE of your choice. I do not write tests for everything and maybe I should, but this was supposed to be fun.

Solution

I have actually solved the original problem in a shorter time than what I have spent on it in the university. First, I wrote a solver, which attempts to input all possible numbers starting from one. This solver can work in a lot of cases, but eventually, you will find puzzles, where it takes too long to find a solution. Then I have created a solver, which prioritizes which cells to solve first based on the number of possible solutions. This solver takes a reasonable time for all puzzles. You can read about it more here. After I was done, I have created a solver that attempts to solve puzzles like a human. This enabled me to create a generator, which creates puzzles that can be solved by people. After all that, I wanted to see the produced Sudokus on paper and I added PDF output.

Results

You can see the PDF output of my Sudoku generator here. The generator is still a work in progress. Although the PDF file contains the Sudokus of the lowest difficulty, it takes a long time to solve them for a human. However, I am very confident that every puzzle can be solved by a hand and has only one solution. In addition to generating PDFs, I decided to share some Sudokus in string format as test data, so you can attempt to write your own solution. Finally, I decided to upload some of the code to github for inspiration.

Conclusion

I have managed to do the assignment in a fraction of the time I spent on it in the university. The main advantage is the tests, which enable me to see the impact of my changes to the code right away. Also, using the object-oriented programming has its own benefits.  It was a fun project and it assured me, that I have come a long way since the university.

Leave a Reply

Your email address will not be published. Required fields are marked *