Building a Sudoku Solver

Sudoku Solver

A couple of weeks ago I tried my hand at building a game, Tic-tac-toe. Today, I finished building something else. I wrote a command line program that solves Sudoku puzzles. The input to the program is a series of numbers representing a sudoku puzzle board, and the output is printed to a terminal screen.

What did I do?

I built the program in C++ with the help of 3 different libraries (google test/mock for testing, boost for handling command line arguments, and ncurses for drawing to the terminal). I had already used google test and boost before, so it was simple to use them in this project. Ncurses was new for me, but it basically worked right out of the box (after updating the link line and including the header). I think I could have written this program without any of these libraries, but it would have been a lot more painful and buggier.

The program is designed to have a MVC (Model, View, Controller) architecture. The model is the puzzle board data, the view is the command line terminal, and the controller is something that observes the model and calls the view to draw. TODO: Learn more about the MVC pattern. Then make my code conform the pattern better, or stop calling what I wrote "MVC".

The business logic of this program was to solve a Sudoku puzzle. The reason I started writing this program was to practice writing a backtracking dynamic programming algorithm. For the current version, I chose a pretty simple algorithm that walks through the grid cell by cell in order. It works for the few test inputs that I gave. However, there is lots of room for improvement.

What did I spend my time on?

I spent almost all of my time setting up the apparatus for the game - ingesting input, updating the view, connecting the components together, etc ... I spent very little time on the algorithm used to calculate the answer. Now that the apparatus works ok, (if I want to) I can work on improving the solving algorithm.

Takeaways

Building a real application can be a good way to learn, but it's easy to fall into the trap of only reusing techniques, approaches and tools that you are already familiar with. Unless you keep asking yourself, "is there a better way to do this?", you may never expand your skills.

Positive feedback is really important. It feels good to see your unit tests passing and your output displayed on some screen. That sense of accomplishment can keep you motivated when you are lacking the motivation to finish a project.