"How do you create an algorithm?" is a question i saw on Quora recently and it started me thinking. What are the steps I follow and could there be something that someone could learn from that? Since I've been wanting to write a sudoku solver just for fun, I decided to write up the process.

Interestingly, the task of writing a sudoku solver has been the subject of debate previously. That debate was about the limitations of TDD and might be well worth reading. I am a big fan of TDD and would add my vote to those who claim that it helps you develop faster and more fearlessly, when done right. But when done wrong, it probably can slow you down and prevent you from doing the right thing.

Now I don't want to get into a long discussion about TDD, but there is one thing I want to point out: tests are mainly about verifying your assumptions. A failing test verifies your assumption about what was wrong with the code. A failing test that starts passing verifies that the code you just wrote fixes the problem. An automated unit test that you run regularly verifies your assumption that "this change couldn't possibly affect that code". I've previously written about how assumptions slowed me down here and here. So for effective testing, make sure your tests verify assumptions about the code. If you're only verifying that the code was written in a specific way (easy to do with mocks), you should probably re-assess the usefulness of the test. Even with tests, don't forget to make the code readable, and do code reviews, pair programming or mob programming according to your preference. (If you do want to read a longer recent post on TDD, I suggest this one).

OK, when creating an algorithm we must first make sure we understand the problem and the requirements, so if you don't know sudoku, go read up on it.

Now we can start thinking about how we would go about solving it. The easiest solution would be to just type up the rules in some constraint solver software or programming language like Prolog. But that kind of programming is a very different mindset and it might be hard to switch to even if using a language like Shen or Curry that has it built-in, so I'm not doing that.

What else do we know or can decide? I'm pretty sure I want to input the problem as text something like this:

534|678|912
672|195|348
198|342|567
-----------
859|761|423
426|853|791
713|924|856
-----------
961|537|284
287|419|635
345|286|179

with '.' for unknowns, and output it the same way. Maybe I'll allow more versions for the input, adding whitespace, ignoring lines, zeroes instead of dots. I don't think I need to explore any variations here. I can think of at least wanting to test one known sudoku puzzle as an acceptance test that I am done. I might also want to test edge cases like inputting an already solved puzzle and inputting a puzzle with all unknowns. So should I go ahead and write these tests? The problem is that I cannot make them pass immediately, so running them all the time is going to introduce noise into the process with these expected failing tests. On the other hand, I am thinking about it now, so it would be good to capture that thinking. I'm pretty sure that my assumption is correct that my code won't work right now, I don't need a failing test, so I'll just write a TODO for now.

So what about writing the input and output code? No! One of the biggest problems in the software industry, even inside Google, is that programmers are too quick to start writing code, which means there's just more and more code solving the wrong problem or solving it the wrong way and then you leave it to someone else to clean up. We are not ready to make a quick decision on what the internal data structure is going to be as that is directly interacting with our algorithm. A premature bad choice is going to throw a big spanner in the works.

What ideas do we have for how we will find the solution?

  • We could try to do it like humans do, with different heuristics like "if two positions both need one of the same two values, then either of those values cannot be assigned to a third position". This seems like it might be complicated and we can't be sure we have all the needed heuristics. Also unclear what data structure would best support the algorithm.
  • We could just store the placed digits and open spaces in a mutable array, much like our input format, and try each value in each open position and check for validity. The good thing about this is that we can easily try the states in order because we can reverse each decision easily, just replace the last placed digit with a '.' and backtrack. The bad thing is that we probably won't finish until the end of the universe, with about 9^50 possibilities (with 31 givens). We might still be ok if we check for consistency after placing each digit, but it seems likely we won't be reducing the search space fast enough, with too many high multipliers at the beginning of the search.
  • What if we kept track of the remaining possibilities in each open position and always selected the one with the fewest alternatives to try? That should keep the multiplicative combinatorial explosion down. This sounds promising and there are some data structure options, but before exploring those, let's see if we have any more ideas about how to solve the problem.
  • Another idea could be to try and fill out all occurrences of a digit before moving on to the next, but that just seems like a variation of the previous with unclear benefits. It's a possible extension if needed. I can't think of any way to generate look-up tables or otherwise speed things up. No other approaches come to mind right now.

OK, so, keeping track of remaining possibilities we could store the state as an array with each cell containing either a placed digit or a list of possibilities. Since we want to search for the open position with fewest options, it might be more efficient to keep a list of just the open positions separate from a list or array of placed digits. For faster access to each open position we could even key them into a map/dict. But do we need it?

Thinking more about how we will move forward and backtrack (undoing choices that didn't work) through potential solutions, it seems easiest to just copy the new state for the next step. If we're copying all the state anyway, we may as well just go with the simpler array option.

Almost ready to code! What shall we do about the initial input state? Shall we represent the given digits as already placed and work out what the remaining options for the open positions are? Or shall we represent the given digits as open positions with one remaining possibility, setting the open positions to have all possibilities remaining, and then just run it through the same algorithm all the way? The second option seems to be a slam-dunk so we don't get two pieces of code interpreting the same rules.

If this code has to be part of a large code base, we would also have to study the structure of the code base so we can add the code in a good place. Don't just add code at the first place it could work, that will just start to accumulate a mess, usually at the edge of the system.

Now we need to choose how we want to drive the tests, either through the text input described above or with the internal representation. Since it isn't too hard to create an internal representation in my chosen language and I think it might be easier to verify properties of the internal output, I will drive it internally, then separately drive the text conversion and add an integration test at the end.

The code

Right, let's code! I will be using Dart for this example. If you know Java or Javascript or anything similar you should be able to follow along. If you feel you want an intro to Dart, try this.

I first want to add a test for when the puzzle is complete, or when there are no more choices to be made. Since I'm not entirely thrilled about working too much with two-dimensional arrays (or lists of lists) in Dart, I think I will use a list of open positions as my internal input format and return a two-dimensional array with the solution.

The minimal implementation passes and I add a test that the last remaining digit gets placed, with the minimal code to make it compile (failing to compile is a failing test, but that has a bit quicker turnaround):

Which fails, as expected:

00:03 +1 -1: internal solver last digit gets placed [E]                                                                                                
  Expected: satisfies function
    Actual: [
              ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
              ...

The following code makes the test pass:

You may have noticed that my code is flawed. I should have made a deep copy of "remaining" before passing it on, as should become clear soon. Today I think of it, but other days I might not, that's how it goes when values are mutable. I deliberately choose not to fix this now because my tests should force me to do it (let's see if they do!).

Another thing you may notice is that I do more than the test requires by selecting the position with least options. On a day when I'm the best version of myself, I might play a game of trying to outsmart the tests to force myself to specify things better, e.g. by just selecting the first open position. Not today.

Still oblivious and proceeding in a good rhythm, I add tests for propagating constraints in rows, columns and blocks, one at a time with the corresponding code that makes them pass.

One thing you may have noticed is that my test data would never come up in a real run of the program because there would be more constraints working together. The test depends on the knowledge that my algorithm doesn't care about those other constraints. It could be a risk to depend on knowledge about the algorithm in the tests, but it's worth it for having tests that are much simpler and easier to understand. I've carefully chosen to make the middle digit be alone (first pick) in the test cases to reduce my knowledge of the inner workings, so that whether the code picks the first or the last option of many I should discover whether the constraints are propagated or not.

The next test depends even more on knowledge of the inner workings, but again I prefer that the test is simpler. I add a comment about it because my reasoning is perhaps not immediately obvious. At least I am still mostly testing assumptions about results of the code and not how the code is written. Just note that it's a slippery slope.

The test fails with an exception "Bad state: No element" and I realize that I haven't handled the simple case where there are no options for an open position, so I comment out the failing test and deal with that first.

Going back to the backtracking test, it now returns null and fails, as expected since we hit the contradiction and don't make another choice. I decide I need to restructure the code quite a bit, still just mutating objects.

Running the test gives a very strange result that I'm not sure I understand.

00:02 +6 -1: internal solver contradiction is backtracked [E]                                                                                          
  Expected: (satisfies function and satisfies function and satisfies function and satisfies function)
    Actual: [
              ['3', '6', '.', '.', '.', '.', '.', '.', '.'],
              ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
              ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
              ...

Thinking really hard, I realize it is because I remove the best open positions from the same "remaining" array, so when we backtracked and try to place '3' and then '6', the "remaining" array is empty and the algorithm returns a solution. I obviously need to copy the remaining array before the recursive call.

Well, that did something, we're back to failing with a null (no solution found). Of course, I need to copy the OpenPosition objects as well so that each backtrack has the right options available!

Great, that works! Now I am quite confident that this will solve a sudoku. We just have to transform the input into internal form. Adding a new function to parse the input and the corresponding test for it (run the failing test first, of course!).

I was sure that would work, but I only get 77 elements, I'll have to re-examine my assumptions. When I check the "digits" list, I see that it contains '0'-'8', not '1'-'9'. Doh! There are 4 nines in the input, so that should cover it.

I add a few more assertions to verify the parsed input, which all pass.

Excellent! Now we just need to put it all together and I write the test I deferred at the beginning of this article. The printing code takes a bit of thought but I decide that I can easily distinguish errors in printing from errors in solving so I don't need a separate test right now.

Surprisingly, I get 'No solution found'. What is going wrong here? I take a look at the code and have the idea that perhaps "choices.toList()" does not create a new list. So I add a check and run again.

That doesn't seem to be the problem though, I have to go deeper. I add a test to see what happens if I input an already solved sudoku. That also fails to find a solution. I double-check that it is a valid sudoku. WAT? I'm about to start extending the tests for rows, columns and blocks, when it jumps out at me from the constraint propagation code:

I remove that line and verify that the block-filling test fails. It does, but I see from the test output that I had placed the block in the top left corner, which has the same x and y coordinates, a bad choice for a test that depends on both x and y. So I change that test to be three rows further down, verify it still fails and that putting back the removed code line still fails until I correct it.

That does the trick, but now I get a type error on my full solution " type 'MappedListIterable<List, String>' is not a subtype of type 'List'". I have to do a websearch for that and it seems that the error is that the compile-time type-checking isn't quite working here. When I create the "rows" variable I just do a "map" operation, but that does not return a List, so I have to append ".toList()".

That was a bit sweaty, but now it works, apart from a newline missing from the end. I correct that, and I look over my code to see if I can clean it up a bit, e.g. some names need changing or code can be rephrased clearer. You can see the final result here.

Summary of the process

  1. Don't start coding until you understand the problem.
  2. Don't start coding until you understand well enough how you are going to solve it
    • Explore various possibilities and evaluate
    • Choose the simplest solution that is good enough
    • If you cannot decide, ask yourself what information will help you decide and go find that out.
    • Don't get stuck, flip a coin if you have to. If it turns out bad you will have learned something along the way.
  3. Don't start coding until you know how the new code will fit into existing code, don't just add it the first place you think it might work. Refactor existing code to create a good fit, if needed.
  4. Use tests to validate (or disprove) your assumptions.
    • A failing test validates your assumption about what your code does not yet do correctly.
    • A failing test that starts to pass validates your assumption that the code you wrote actually does something useful.
    • An automated unit test that is kept and run periodically tests your assumption that "this code couldn't possibly break that code".
  5. When you don't fully understand how your tools work, you need to explore, observe and test your assumptions about them. Just don't confuse exploratory coding with production coding, you still need to validate that you can't simplify the experimental code.
  6. When everything works, make sure your code is easy to read and understand and clean up whatever can be cleaned up. Another pair of eyes is good here, do code reviews or pair or mob programming.