Oct 24, 2012
Digging through /r/learnprograming I noticed a lot of new developers were asking questions about how to solve small computational problems, for either homework or self learning. Many of the posts showed now work in the direction of a solution and after posting a solution to a Sudoku solver application I realized that one of the most valuable skills I've learned over the years was how to plan out a solution and visualize how everything will work.
Defining your World
Probably the most necessary step, and most likely the most overlooked step, is trying to define the world in which your problem resides. In a simply defined problem like a Sudoku solver the world in which the problem exists can still be difficult to visualize at the beginning.
What is our problem?
Firstly, you must ask yourself "What is the problem I am trying to solve?" This will not always generate a straight forward answer. In our Sudoku problem we are trying to solve the problem of "Can a computer solve a Sudoku Puzzle?" From this problem we can see that our world view incorporates a computer and a puzzle. This may sound a little silly at first but it brings up another question of how we can connect the two pieces.
When programming developers must figure out ways to take real world situations, objects, and concepts and turn them into mathematical representations. In our problem, how to create a mathematical model of the puzzle. What type of attributes does a Sudoku puzzle have? At first glance the puzzle is a 9 by 9 grid containing numbers and empty spaces that we fill in during our attempt at solving. Our first stab at creating a model is to make a two dimensional array containing 81 squares. But will this work? How do we represent empty squares? How do we identify givens as compared to our attempts at a solution? Now you can see the complexity increase in our world.
Give me your data
Transitioning data from the real world problem to our model is the next hurdle we must overcome. Some problems require large amounts of historical data to be analyzed, some require user input. Proper planning of your problem's world must include the mechanisms for gathering the inputs that define the specifics of what are are attempting to solve. In our Sudoku problem many ideas come to mind ranging from simple (hard coding the values into the array) to the complex (using OCR to read the puzzle with a scanner). Resolving givens and empty cells is part of this process.
Change is Inevitable
As you start working on your problem's solution you will inevitably find that your original view of the world was incorrect...or better yet, misguided. Your first pass through you may not know everything about the problem. Your representation may have flaws that were not obvious in the beginning so don't be afraid to come back periodically and glance over your world view. As you work through the problem you will become more knowledgeable and may be able to resolve previously unseen negative aspects of your world view.
Once you've created your world and able to enter your real world data you can go one of two ways. Many people will go right to attempting to solve the problem. If you choose to go this route I wonder, "How will you know if your solution is correct?" Without being to verify that your solution actually solves the problem you'll eventually head down the road of making your verification fit your solution, rather than fitting your solution to the verification.
Every problem has a set of rules you must follow. Physics engines must not defy the laws of physics, homework grading systems can't give a D grade. Our Sudoku solver has rules as well.
- Each Row must contain a single instance of 1 - 9
- Each Column must contain a single instance of 1 - 9
- Each Zone must contain a single instance of 1 - 9
Once you've defined your rules you can now create ways of verifying the rules are followed in your solution. Go through all of your rules and brainstorm ways to check your solution has met a given rule. Depending on your problem, as well as your solution, this rule checking process may run many, many times so getting this correct and simple is key. As with the World, you will want to come back and tweak your rule checking so creating straight forward, simple test cases will make this process much easier.
Rules can apply to the problem as a whole as well as individual parts of the problem. Unit testing is a great way to break down the problem into smaller parts and verify individual rules of your problem are met. At some point it may start to become overwhelming to creating so many unit test. You should remind yourself that working on unit tests now will help pin-point bugs in your code much faster than just reading through code. No one ever writes perfect code so why not spend some time up front to save yourself time in the future.
Verification of your Verification
The last step in creating your verification process is to check that it actually works. Again, this is one of those cases where it may sound silly but pitfalls do exist. Scope of testing verification code is always a problem for me. I may write a unit test giving, what I think at the time to be, a good range of valid and invalid cases. I can't even count the number of times I've been burned because I did not broaden the scope of my verification code testing.
Looking at our 3 rules of Sudoku at first I'd say we only need 4 test cases:
- A Bad Row
- A Bad Column
- A Bad Zone
- A Solve Puzzle
It may be unnecessary in our case here, but having a single example of each rule failure only really proves our code can find that specific instance of the rule failure. If you only test a case where the first row is bad, we can only really say our verification code can identify when the first row is bad. Expand this idea out as far as you feel is needed in your actual problem.
Now to the fun stuff. You have your World and the ability to manipulate it as well as a way to figure out if you have found your solution. So lets start coming up with ways of solving the problem.
Thats the worst idea I've ever heard
Even though there is a lot to think about when solving any problem, I like to start out by just coming up with the most simple, dirty way of getting the problem solved. Since you are just brainstorming at the moment things like cost, implementation time, CPU power, etc. shouldn't factor in. We just want to get the creative juices flowing here and not worry about all of the minutia that will soon follow.
If you've ever had a job interview you've run into questions where the potential employer asks "So how would you solve XXX problem?" Obviously you don't have time to create rules and unit tests for this hypothetical problem. What the interviewer is looking for is your ability to visualize a problem and then generate a solution. It may not be optimal, it may not even work correctly. But it shows that you can understand an issue and work with it.
There are many solutions to any problem
Now that you are thinking about solutions you'll want to slowly add in additional requirements to your thought process. Things like algorithm complexity, system loading, or iterations of verification should be used to weed out possible solutions that just will not work realistically. I use tons of dry-erase markers at work as I am constantly drawing different solutions to a given problem, crapping bad ideas and extending on possible good ones. Brainstorming costs very little as compared to implementation so taking a good chunk of time here is worth it.
Once I've come up with a few good ideas I start to compare them trying to make one stand out from the others. For larger projects you'll use this time to come up with future problems and features that may be added later to the project and see how each implementation would deal with these changes. One solution may be cheaper to produce now, but pigeon hole you later where as your other solution may be more flexible in the end.
Reduce, Reuse and Recycle
If you are like me, you tend to keep a repository of all the code you've ever written. If you aren't like me...maybe you should be in this case. Every program you write resolves many problems, not always the direct one you are solving. I go through my repository of code to find the many ways I've solved simple things like Memory Management, Sorting Algorithms, etc. and constantly come back to this code. In software development this is called Software Design Patterns. There are millions of books out there that cover a whole mess of patterns and its worth your while to read up on some. The one problem with many of these books is they only show pseudo-code and when it comes to implementation theres always a little bit of an art when it comes to putting these into action. If you use the same languages over and over for multiple projects you'll be able to go back to your repository and get a good start on porting them to your new problem.
If you go online or read any books about Project Management you'll hear all sorts of quotes about how many Man-Hours of planning goes into a single line of code. When it comes to development, planning is going to be cheaper than reimplementation and extremely cheaper than having to come back later and resolve bugs that could have been eliminated with proper planning.