Creating an algorithm

UPDATE: This article has been re-published with a code example in Dart instead of Tailspin here. The choices made and the TDD process ended up somewhat different so it may be worth looking at both. If you just want to see the code or the TDD process in this post, you can skip to it.

"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.

If you're in a hurry, jump to the summary at the end.

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 950 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, just 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 just 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 my own programming language, Tailspin. If you want an intro to Tailspin, read this. First I set up a test that verifies that an already solved sudoku stays solved.
templates placeDigit
  $ !
end placeDigit

test 'internal solver'
  def sample: [
    [5,3,4,6,7,8,9,1,2],
    [6,7,2,1,9,5,3,4,8],
    [1,9,8,3,4,2,5,6,7],
    [8,5,9,7,6,1,4,2,3],
    [4,2,6,8,5,3,7,9,1],
    [7,1,3,9,2,4,8,5,6],
    [9,6,1,5,3,7,2,8,4],
    [2,8,7,4,1,9,6,3,5],
    [3,4,5,2,8,6,1,7,9]
  ];

  assert $sample -> placeDigit <=$sample> 'completed puzzle unchanged'
end 'internal solver'
That passes and I add a test that the last remaining digit gets placed:
test 'internal solver'
  ...
  assert [
    [[5],3,4,6,7,8,9,1,2],
    $sample(2..last)...] -> placeDigit <=$sample> 'final digit gets placed'
end 'internal solver'
Which fails, as expected:
internal solver failed:
assertion that final digit gets placed failed with value [[[5], 3, 4, 6, 7, 8, 9, 1, 2], ...
I add a fairly large amount of code to try to pass this test, which makes me wonder if that code is fully tested. It is usually fun to play a game of trying to outsmart the tests by writing simpler code than you need, e.g. I should look for the first open position instead of the best to begin with. But I'll leave that for a day when I'm a better person.
templates placeDigit
  templates nextDigit
    @:{options: 10};
    $ -> \[i;j](when <[](..~$@nextDigit.options)> do @nextDigit: {row: $i, col: $j, options: $::length}; \) -> !VOID
    $@ !
  end nextDigit
  templates set&{pos:}
    $ -> \[i;j](
      when <?($i <=$pos.row>)?($j <=$pos.col>)> do $(1) !
      otherwise $ !
    \) !
  end set
  $ -> set&{pos: $ -> nextDigit} !
end placeDigit
Surprisingly, I get an error (I need to file a bug report to get a better diagnostic here).
Exception in thread "main" java.lang.NullPointerException: No value defined for $pos.row
It turns out that I no longer handle the first case, so I have to add a check for that.
templates placeDigit
  templates nextDigit
    @:{options: 10};
    $ -> \[i;j](when <[](..~$@nextDigit.options)> do @nextDigit: {row: $i, col: $j, options: $::length}; \) -> !VOID
    $@ !
  end nextDigit
  templates set&{pos:}
    $ -> \[i;j](
      when <?($i <=$pos.row>)?($j <=$pos.col>)> do $(1) !
      otherwise $ !
    \) !
  end set
  def given: $;
  $ -> nextDigit -> #
  when <{options: <=10>}> do $given !
  otherwise def next: $; $given -> set&{pos: $next} !
end placeDigit
The tests pass and I add an assert for an unsolvable puzzle that fails and then code to make it pass:
templates placeDigit
  ...
  def given: $;
  $ -> nextDigit -> #
  when <{options: <=0>}> do [] !
  when <{options: <=10>}> do $given !
  otherwise def next: $; $given -> set&{pos: $next} !
end placeDigit

test 'internal solver'
  ...
  assert [
    [[],3,4,6,7,8,9,1,2],
    $sample(2..last)...] -> placeDigit <=[]> 'no remaining options returns empty'
end 'internal solver'
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. I also have to make a recursive call at the end to keep solving all remaining digits.
templates placeDigit
  ...
  templates set&{pos:}
    def digit: $($pos.row;$pos.col) -> $(1);
    $ -> \[i;j](
      when <?($i <=$pos.row>)?($j <=$pos.col>)> do $(1) !
      when <[]?($i <=$pos.row>)> do [$... -> \(<~=$digit> $! \)] !
      when <[]?($j <=$pos.col>)> do [$... -> \(<~=$digit> $! \)] !
      when <[]?(($i-1)~/3 <=($pos.row-1)~/3>)?(($j-1)~/3 <=($pos.col-1)~/3>)> do [$... -> \(<~=$digit> $! \)] !
      otherwise $ !
    \) !
  end set
  ...
  otherwise def next: $; $given -> set&{pos: $next} -> placeDigit !
end placeDigit

test 'internal solver'
  ...
  assert [
    [[5],3,4,6,[2,5,7],8,9,1,[2,5]],
    $sample(2..last)...] -> placeDigit <=$sample> 'solves 3 digits on row'

  assert [
    [5,3,4,6,7,8,9,1,2],
    [[6,7,9],7,2,1,9,5,3,4,8],
    [1,9,8,3,4,2,5,6,7],
    [8,5,9,7,6,1,4,2,3],
    [4,2,6,8,5,3,7,9,1],
    [[7],1,3,9,2,4,8,5,6],
    [[7,9],6,1,5,3,7,2,8,4],
    [2,8,7,4,1,9,6,3,5],
    [3,4,5,2,8,6,1,7,9]
  ] -> placeDigit <=$sample> 'solves 3 digits on column'

  assert [
    [5,3,[4,6],6,7,8,9,1,2],
    [[6],7,2,1,9,5,3,4,8],
    [1,[4,6,9],8,3,4,2,5,6,7],
    $sample(4..last)...
  ] -> placeDigit <=$sample> 'solves 3 digits in block'
end 'internal solver'
One thing you may have noticed is that my test data would never come up in a real run of the program. The test depends on the knowledge that my algorithm doesn't care about the already placed digits. 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.
  // This gives a contradiction if 3 gets chosen out of [3,5]
  assert [
    [[3,5],[3,4,6],[3,4,6],[3,4,6],7,8,9,1,2],
    $sample(2..last)...] -> placeDigit <=$sample> 'contradiction is backtracked'
The test fails, as expected.
internal solver failed:
assertion that contradiction is backtracked failed with value []
Now we can't just output the result of the recursive call, we have to see if it resulted in a contradiction and, if so, remove the guess we made and make another.
templates placeDigit
  templates nextDigit
    ...
  end nextDigit
  templates set&{pos:}
    ...
  end set
  @: $;
  $ -> nextDigit -> #
  when <{options: <=0>}> do [] !
  when <{options: <=10>}> do $@ !
  otherwise def next: $;
     def result: $@ -> set&{pos: $next} -> placeDigit;
     $result -> \(<~=[]> $! \) !
     $result -> \(<=[]> $! \) -> ^@($next.row;$next.col;1) -> $@ -> nextDigit -> #
end placeDigit
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 (test first, of course!). Tailspin has a special syntax called a composer for specifying the result you want with regex-matchers for snippets of the input string. So we want an array that has three sections, each consisting of three rows and optionally ended with a line of dashes that we ignore, where each row has groups of three digits optionally separated by an ignored pipe-character.
composer parseSudoku
  [<section>=3]
  rule section: <row>=3 (<'-+'>? <WS>?)
  rule row: [<triple>=3] (<WS>?)
  rule triple: <digit|dot>=3 (<'|'>?)
  rule digit: [<'\d'>]
  rule dot: <'\.'> -> [1..9]
end parseSudoku

test 'input sudoku'
  def parsed:
'53.|.7.|...
 6..|195|...
 .98|...|.67
 -----------
 8..|.6.|..3
 4..|8.3|..1
 7..|.2.|..6
 -----------
 .6.|...|28.
 ...|419|..5
 ...|.8.|.79' -> parseSudoku;

 assert $parsed <[<[<[]>=9](9)>=9](9)> 'parsed sudoku has 9 rows containing 9 columns of lists'
end 'input sudoku'
I was confident that would work, but it doesn't:
Exception in thread "main" java.lang.IllegalStateException: No composer match at '53.|.7.|...
This is turning out to be more educational than I intended! Obviously I don't fully understand how this works (or I just made a mistake), but now I have to back up and check some underlying assumptions. First I'll check that the digit and dot rules are correct.
composer parseSudoku
  <digit|dot>
  rule digit: [<'\d'>]
  rule dot: <'\.'> -> [1..9]
end parseSudoku

test 'input sudoku'
  assert '9' -> parseSudoku <=[9]> ''
  assert '.' -> parseSudoku <=[1..9]> ''
end 'input sudoku'

out:
input sudoku failed:
assertion that  failed with value [9]
That's a surprise, the output looks like what I expect. It turns out, though, that the string '9' gets displayed like the integer 9 (filing an issue for better test output). It doesn't actually matter whether I use character strings or integers, the internal solver handles either, as long as we use the same type throughout. I will use characters (chosen by coin-flip), but that wasn't really the problem because the parsing actually works. So I extend the experiment a bit:
composer parseSudoku
  <digit|dot>=3 (<'|'>?)
  rule digit: [<'\d'>]
  rule dot: <'\.'> -> [1..9 -> '$;']
end parseSudoku

test 'input sudoku'
  assert ['139' -> parseSudoku] <=[['1'],['3'],['9']]> 'plain'
  assert ['139|' -> parseSudoku] <=[['1'],['3'],['9']]> 'with |'
end 'input sudoku'

out:
Exception in thread "main" java.lang.IllegalStateException: Composer did not use entire string. Remaining:'|'
So there we have it, my rule to match <'|'> doesn't match a '|' because it's a special character in regex syntax. I have to escape it with a backslash. I correct the issues, reinstate the original test and the test passes. I add two more assertions which pass immediately.
 assert $parsed(1;1) <=['5']> 'a digit'
 assert $parsed(1;3) <=['1','2','3','4','5','6','7','8','9']> 'a dot'
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.
templates solveSudoku
  $ -> parseSudoku -> placeDigit -> #
  when <=[]> do 'No result found' !
  otherwise def result: $;
    [1..7:3 -> $result($..$+2) -> \section('$:1..11 -> '-';$#10;' ! $... ->
      \row( def r: $;
        [1..7:3 -> $r($..$+2) -> \triple('|' ! $... ! \triple)] -> '$(2..last)...;$#10;' !
      \row)
    !\section)] -> '$(2..last)...;' !
end solveSudoku

test 'sudoku solver'
  assert
'53.|.7.|...
 6..|195|...
 .98|...|.67
 -----------
 8..|.6.|..3
 4..|8.3|..1
 7..|.2.|..6
 -----------
 .6.|...|28.
 ...|419|..5
 ...|.8.|.79'
  -> solveSudoku <=
'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'> 'solves sudoku and outputs pretty solution'
end 'sudoku solver'
And there we have it! Apart from some whitespace errors it works like a charm. I correct those and look over the code. I don't like the names I have assigned to the templates. I can also consolidate the code for updating remaining possibilities and simplify the backtracking a bit because I will never find another position to continue from. The finished code is 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.

Comments

Post a Comment

Popular Posts