Why TDD makes a lot of sense for Sudoko

My colleague Thomas sent me a very interesting link about attempts to solve Sudoku using test-driven development. The article, somewhat unfairly, pits Ron Jeffries’ explorations of Sudoku using test-driven development against Peter Norvig’s “design driven” approach.

I found both attempts lacking. However, while Ron Jeffries freely admitted that he didn’t even know the rules of Sudoku when he started, both Norvig himself and his readers fawn over his solution. I didn’t find it very understandable.

So I took it upon myself to examine the problem myself. I did some up-front thinking in the shower and on the subway, then attacked the problem with TDD. I ended up with a solution that works in all cases (unlike Norvig). My implementation has readable code, readable tests, and solves the problem reasonably fast.

Observations and conjectures

Here are a few things I learned from the exercise:

• When you’re using TDD to solve a tricky algorithm, you have to think about both the algorithm and the test approach.
• Solving a problem with a known algorithm using TDD gives more readable code than I otherwise would expect.
• When I solved the problem with TDD, running the solution on real problems worked the very first time I tried it.
• The trick to making TDD work is to work from the outside in.
• When creating a Sudoku solver, don’t think like a human! Think like a machine! The human algorithm is difficult to understand and likely to not work on all problems. This was the biggest problem with Norvig’s code

The journey

I decided on the following approach:

1. I had decided upon an initial design with a solver class and a board class. The solver should use a recursive depth first search. The solver asks the board what options exists per cell, but it has no knowledge of the rules of Sudoku (such as no duplicate numbers on the same row).
2. The first step was to get the solver (“the outside”) correct. For this step, I mocked out the board
3. The second step was to implement the interface that the solver needed for the board. Mainly, this is a matter of specifying the rules for what numbers can occur in which cell on a Sudoku board.
4. Finally, I wrote some code to read and write the Sudoku board. When trying the solver on real problems, it worked the first time, and solved 95 hard problems correct. It was somewhat slow, though.

After solving the problem the first time, I practices a few times and recorded a screen cast of the solution:

The solver

Testing the solver is a matter of creating a mock board and ensuring that the solver does the correct things. This is the most complex test case:

@Test
<span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000066; font-weight: bold;">void</span> shouldBacktrackWhenNoMoreOptions<span style="color: #009900;">(</span><span style="color: #009900;">)</span> <span style="color: #000000; font-weight: bold;">throws</span> <span style="color: #003399;">Exception</span> <span style="color: #009900;">{</span>
    SudokuSolver solver <span style="color: #339933;">=</span> <span style="color: #000000; font-weight: bold;">new</span> SudokuSolver<span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    SudokuBoard board <span style="color: #339933;">=</span> mock<span style="color: #009900;">(</span>SudokuBoard.<span style="color: #000000; font-weight: bold;">class</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    when<span style="color: #009900;">(</span>board.<span style="color: #006633;">getOptionsForCell</span><span style="color: #009900;">(</span>anyInt<span style="color: #009900;">(</span><span style="color: #009900;">)</span>, anyInt<span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
            .<span style="color: #006633;">thenReturn</span><span style="color: #009900;">(</span>singleOption<span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
 
    when<span style="color: #009900;">(</span>board.<span style="color: #006633;">getOptionsForCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">8</span>, <span style="color: #cc66cc;">7</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
            .<span style="color: #006633;">thenReturn</span><span style="color: #009900;">(</span>moreOptions<span style="color: #009900;">(</span><span style="color: #cc66cc;">1</span>, <span style="color: #cc66cc;">2</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    when<span style="color: #009900;">(</span>board.<span style="color: #006633;">getOptionsForCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">8</span>, <span style="color: #cc66cc;">8</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
            .<span style="color: #006633;">thenReturn</span><span style="color: #009900;">(</span>noOptions<span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
            .<span style="color: #006633;">thenReturn</span><span style="color: #009900;">(</span>singleOption<span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
 
    assertThat<span style="color: #009900;">(</span>solver.<span style="color: #006633;">findSolution</span><span style="color: #009900;">(</span>board<span style="color: #009900;">)</span><span style="color: #009900;">)</span>.<span style="color: #006633;">isTrue</span><span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    InOrder order <span style="color: #339933;">=</span> inOrder<span style="color: #009900;">(</span>board<span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    order.<span style="color: #006633;">verify</span><span style="color: #009900;">(</span>board<span style="color: #009900;">)</span>.<span style="color: #006633;">setValueInCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">1</span>, <span style="color: #cc66cc;">8</span>,<span style="color: #cc66cc;">7</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    order.<span style="color: #006633;">verify</span><span style="color: #009900;">(</span>board<span style="color: #009900;">)</span>.<span style="color: #006633;">setValueInCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">2</span>, <span style="color: #cc66cc;">8</span>,<span style="color: #cc66cc;">7</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
<span style="color: #009900;">}</span>

It specifies that all cells, except (8,7) and (8,8) return exactly one option. (8,7) returns two options. (8,8) returns no options the first time it is called, and one option the second time. The test verifies that a solution is found, and the solver tries to set both options for (8,7).

This drives a rather simple algorithm. Here’s basically the whole algorithm:

<span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000066; font-weight: bold;">boolean</span> findSolution<span style="color: #009900;">(</span>Board board, <span style="color: #000066; font-weight: bold;">int</span> cell<span style="color: #009900;">)</span> <span style="color: #009900;">{</span>
    <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">(</span>cell <span style="color: #339933;">==</span> SIZE<span style="color: #339933;">*</span>SIZE<span style="color: #009900;">)</span> <span style="color: #000000; font-weight: bold;">return</span> <span style="color: #000066; font-weight: bold;">true</span><span style="color: #339933;">;</span>
 
    <span style="color: #000066; font-weight: bold;">boolean</span> wasEmpty <span style="color: #339933;">=</span> board.<span style="color: #006633;">isEmpty</span><span style="color: #009900;">(</span>row<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span>, col<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">(</span><span style="color: #003399;">Integer</span> value <span style="color: #339933;">:</span> board.<span style="color: #006633;">getCellOptions</span><span style="color: #009900;">(</span>row<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span>, col<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span> <span style="color: #009900;">{</span>
        board.<span style="color: #006633;">setValueInCell</span><span style="color: #009900;">(</span>value, row<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span>, col<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
        <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">(</span>findSolution<span style="color: #009900;">(</span>board, cell<span style="color: #339933;">+</span><span style="color: #cc66cc;">1</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span> <span style="color: #000000; font-weight: bold;">return</span> <span style="color: #000066; font-weight: bold;">true</span><span style="color: #339933;">;</span>
    <span style="color: #009900;">}</span>
    <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">(</span>wasEmpty<span style="color: #009900;">)</span> board.<span style="color: #006633;">clearValueInCell</span><span style="color: #009900;">(</span>row<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span>, col<span style="color: #009900;">(</span>cell<span style="color: #009900;">)</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
 
    <span style="color: #000000; font-weight: bold;">return</span> <span style="color: #000066; font-weight: bold;">false</span><span style="color: #339933;">;</span>
<span style="color: #009900;">}</span>

The algorithm tries all available options for a cell in order. If no solution works for the rest of the board, the algorithm returns false (for “no solution”).

The algorithm is not how a human would solve Sudoku. But then again, we’re not writing a tutorial on how to solve Sudoku, we’re writing a program that solves Sudoku.

The board

As I implemented the solver, the interface for the board started to emerge. At that point in time, I had to create tests for the Sudoku board itself. A typical test verifies that the board doesn’t allow duplicate values in a row:

@Test
<span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000066; font-weight: bold;">void</span> shouldDisallowOptionsInSameRow<span style="color: #009900;">(</span><span style="color: #009900;">)</span> <span style="color: #000000; font-weight: bold;">throws</span> <span style="color: #003399;">Exception</span> <span style="color: #009900;">{</span>
    <span style="color: #000066; font-weight: bold;">int</span> row <span style="color: #339933;">=</span> <span style="color: #cc66cc;">4</span><span style="color: #339933;">;</span>
    board.<span style="color: #006633;">setValueInCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">1</span>, row, <span style="color: #cc66cc;">5</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    board.<span style="color: #006633;">setValueInCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">2</span>, row, <span style="color: #cc66cc;">8</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    board.<span style="color: #006633;">setValueInCell</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">3</span>, row<span style="color: #339933;">+</span><span style="color: #cc66cc;">1</span>, <span style="color: #cc66cc;">5</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    assertThat<span style="color: #009900;">(</span>board.<span style="color: #006633;">getOptionsForCell</span><span style="color: #009900;">(</span>row, <span style="color: #cc66cc;">0</span><span style="color: #009900;">)</span><span style="color: #009900;">)</span>
            .<span style="color: #006633;">excludes</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">1</span>,<span style="color: #cc66cc;">2</span><span style="color: #009900;">)</span>.<span style="color: #006633;">contains</span><span style="color: #009900;">(</span><span style="color: #cc66cc;">3</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
<span style="color: #009900;">}</span>

The essence of SudokuBoard is finding out what values are legal in an open cell:

<span style="color: #000000; font-weight: bold;">public</span> <span style="color: #003399;">List</span> getOptionsForCell<span style="color: #009900;">(</span><span style="color: #000066; font-weight: bold;">int</span> row, <span style="color: #000066; font-weight: bold;">int</span> col<span style="color: #009900;">)</span> <span style="color: #009900;">{</span>
    <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">(</span><span style="color: #339933;">!</span>isEmpty<span style="color: #009900;">(</span>row,col<span style="color: #009900;">)</span><span style="color: #009900;">)</span> <span style="color: #000000; font-weight: bold;">return</span> <span style="color: #003399;">Arrays</span>.<span style="color: #006633;">asList</span><span style="color: #009900;">(</span>cells<span style="color: #009900;">[</span>row<span style="color: #009900;">]</span><span style="color: #009900;">[</span>col<span style="color: #009900;">]</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    <span style="color: #003399;">List</span> result <span style="color: #339933;">=</span> allOptions<span style="color: #009900;">(</span><span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    removeAllInRow<span style="color: #009900;">(</span>result, row<span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    removeAllInCol<span style="color: #009900;">(</span>result, col<span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    removeAllInBox<span style="color: #009900;">(</span>result, row, col<span style="color: #009900;">)</span><span style="color: #339933;">;</span>
    <span style="color: #000000; font-weight: bold;">return</span> result<span style="color: #339933;">;</span>
<span style="color: #009900;">}</span>

TDD as a design guide

I invite you to compare Peter Norvig’s solution to mine (you can find the full source code for my solution in my github repository).

It would probably have been possible for me to code the solution faster without tests, but it probably would not have worked the first time I tried it. I also would have much less confidence in the code. Finally, I think the design imposed by the tests made my code easier to understand.