Practical Objects: Modeling Sudoku in Object Oriented Design

Photo by Florian Olivo on Unsplash

The Goal of Practical Objects

I love programming, but programming is hard and existing paradigms that inflexibly insist upon perfection do not make it easier. This is not to say that paradigms and patterns produce bad code, but certain statements from peers, thought leaders, and friends permeate the space in my head when attempting to solve problems.

  • “This approach is better because it runs faster”
  • “This code violates SOLID”
  • “We should roll our own library instead of using this framework”

I took these statements to heart. I over-analyzed, I created problems to solve where none had previously existed, I anticipated issues rather than solving the ones at hand. I think the goal I had was controlling complexity, but many times the complexity created just by by adhering to “best practices” grew out of control. We have a tendency to think of our classes as little gardens. We sprinkle design patterns throughout our code as if words like Decorator, Factory, and Flyweight because we want the satisfaction of seeing those words the next time we open the editor and not because they actually solved a problem.

I love design patterns. They can solve many problems, but they do add complexity and keeping away from that complexity is the focus of this series. I want to express my thoughts on preventing complexity and introducing it slowly. Don’t worry, we will write plenty of code along the way. This is a journey into the practical usage of objects and how to use them to solve problems productively.

What You Need for This Article

Unfortunately, this is not a “beginning C#” article. Fundamentally, I am hoping you already understand the C# programming language (or at least a language with classes, so that you follow the general outline of the code being written). So to understand this material you should probably have at least some familiarity with:

  • The C# Programming Language
  • A code editor or IDE
  • The dotnet command line tools

Let’s Talk about Sudoku

An example Sudoku puzzle.

To introduce the concepts in this series of articles, we are going to focus on the Sudoku puzzle game. If you haven’t seen Sudoku before, the basic premise is that you are given a 9x9 grid. This grid can be viewed as 9 independent rows, 9 independent columns, and 9 independent 3x3 squares. The goal of Sudoku is to fill out each of these independent items with the numbers 1 through 9. If you use the same number twice in one of these places (rows, columns, squares), then the puzzle is invalid.

We use Sudoku for a few reasons:

  1. It’s a well-explored problem. There is a ton of theory as well as a lot of concrete detail on how Sudoku works. This means that you can take any lesson I give you here and go deeper into the subject without me.
  2. Sudoku as a game has a surprising amount of use cases. This means that we can explore validating puzzles, solving puzzles, creating new puzzles, creative presentations, and much more.
  3. Fundamentally, the representation is simple (it’s just 81 numbers in a box), so we can start off with something trivial and introduce new abstractions as the problem becomes more complex.

Today’s Problem: Validating a Puzzle

Imagine you work a small publisher, potentially a newspaper that has daily circulation. Your job title is Web Developer but since you know how computers work, you often get these one-off projects from other departments. Usually they involve rebooting computers or writing excel formulas, but one morning you receive this email from your manager.

Hey Quill, the editor for our daily puzzle section has a project for you. I think you might find this one interesting! He gets Sudoku puzzles from a contractor every day and they frequently have mistakes. Can you write him a quick utility so that he can double-check that it’s a valid puzzle? The puzzles are really important to our readers, so can you cook something up by the end of the day?

We do not find this interesting. But we’re scrappy! We will take opportunity to uncover a challenge.

However, we also have to figure out why the website keeps crashing so this problem needs to be off our plate. Also, part of the problem being solved is that the editor is already fed up with mistakes in his puzzles. This means we need to put as much effort as possible into getting the answer right. This gives us two priorities:

  • Development Speed
  • Correctness

We may briefly think that these two are at odds, but with a little thought to our process and by leveraging objects appropriately, we can achieve both.

The Decision to Use Objects

If our primary concerns are speed and correctness, then we have basically decided that the overall quality of the code is either less important. However, we also want it to be correct, so a great way to achieve that is to write preliminary tests relatively early on in the process. This may sound like more work overall, but it will save us time with a well-understood problem like Sudoku. Remember, this is about achieving two challenging goals at once and providing the requested business value (you know, the reason you’re paid to write code) on time. Let’s go over the benefits of using an object as an abstraction.

Objects shield our problems from our user’s problems

Our current task is to solve a business problem for our editor. To do this we need to give them a solution that removes as much mental overhead as possible. Fundamentally, this is the purpose of an interface. Keep in mind I am not talking about the concept of a C# interface, but simply the idea of creating a set of commands that allow our user (the editor in this case) to focus on the problem they want to solve and not on the details of how we are assisting them. We then take the data this interface provides us and use that to more narrowly define our own business problem. In doing this, we shrink the problem for our user down to a manageable piece and give ourselves a well-defined space to work in.

This is the basic interface we define for our user.

When we examine the problem given to us above, it really doesn’t have to be anymore complicated than this. We create a Sudoku class, tell our consumer that they need to provide us a list of integers that represent the puzzle, and then provide a simple method (Check) to evaluate whether our puzzle is valid. Whoever consumes this object has to know two things:

  1. How to instantiate a Sudoku class
  2. What is means for a call to Check() to return true or false.

Objects hide the details until we need them

Now that we have a way to tell our user what we need and what we will give back to them, we need to actually solve our own problem, which is validating a Sudoku puzzle. At this point, our primary concern is speed, so we will take a naive approach and simply copy the list of numbers to an internal representation. We might also validate the numbers just a little to ensure that nothing unexpected is entering our puzzle’s problem space.

What did we gain by writing code this way? We allowed ourselves to take a naive approach and just use an array. We could have used multi-dimensional array or a jagged array and stored our numbers in a structure that more closely matched a grid. However, we fundamentally just wanted our user to enter a list of numbers, so any internal representation that deviated from that would have to be translated, meaning we would spend more time on the constructor and not on the problem before us. This might have been a more maintainable approach in the long-term, but this was a trade-off we made in the interest of time. This is probably the most relevant lesson I am hoping to impart with this series. I want to teach you strategies to evaluate these trade-offs with confidence.

It’s also important to note that “more maintainable” is a very subjective measure. You could just as easily find a flat array to be the most naive approach depending upon your skill-set and abstract thinking skills. The most important thing to note here is that this approach afforded us the luxury of writing something that we could reason about fast.

Objects enable testing our solution efficiently

A lot of this boils down to our ability to focus on a given problem and handle it with minimal distraction. Fundamentally, the last piece we need in order to free us from distractions is a process that allows us to write code, get fast feedback, and understand what is going wrong. For an object-oriented approach, few things accomplish this like a unit test. It may sound counterintuitive to spend more time writing code to just test our existing code, but this is where the developer tools can be used to speed up our process. And realistically, you are going to test your code on a valid puzzle anyway, so writing code to repeat that test forever will eventually save you more time than it uses.

Our test puzzles with unit tests for validation

I ended up writing more tests overall, but I felt comfortable starting with just two. The goal is to write and tweak code until these pass. The real power comes from just running these tests live. If you use the dotnet command line tools, this is simple.

It’s that last line that is most important: Waiting for a file to change before restarting dotnet.... This allows us to make changes quickly, save a file, and see if our changed worked right in the console. At this point, just line up your console window next to your text editor, and refactor your way to glory. If you run into a problem or find yourself stuck, you can always run your code in a debugger and step through slowly, but this is great when you generally know what you need to write and just want confirmation that your work is complete.

Now for the Big Finish

By this point, it should be apparent that the actual code for the Sudoku puzzle solver is not really the point of this post, but it would also be incomplete without it. If you are interested in practicing the approach I’ve outlined, then I would encourage you to set up a project and write your own naive approach. Give yourself a time limit if you want a challenge. I will include the code for the Sudoku checker class below, and if you would like to peruse the whole solution, you can check out this Github link.

What’s Next

Right now, my goal is that this series continues and helps outline my strategies for making practical trade-offs with object oriented programming. Some other topics I’ll approach in the future are:

  • Refactoring for maintainability
  • Refactoring for performance
  • Extending your objects with more features
  • Extending the configurability of your objects

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Casey McQuillan

Casey McQuillan

Casey is a technologist, freelancer, and creator specializing in .NET, Azure, and the web. He can be reached at casey@quilltechnologies.com or @QuillCodes