Idea 1: Build your software from the outside-in

Idea 2: Specify behavior rather than implementation

Idea 3: Increase the rate of feedback

Idea 4: Grow the API rather than designing it up front

Idea 5: Grow the design rather than speculating

Idea 6: It's supposed to work the first time around

Observations and conjectures

• 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

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.

The solver

@Test
public void shouldBacktrackWhenNoMoreOptions() throws Exception {
    SudokuSolver solver = new SudokuSolver();
    SudokuBoard board = mock(SudokuBoard.class);
    when(board.getOptionsForCell(anyInt(), anyInt()))
            .thenReturn(singleOption());

    when(board.getOptionsForCell(8, 7))
            .thenReturn(moreOptions(1, 2));
    when(board.getOptionsForCell(8, 8))
            .thenReturn(noOptions())
            .thenReturn(singleOption());

    assertThat(solver.findSolution(board)).isTrue();
    InOrder order = inOrder(board);
    order.verify(board).setValueInCell(1, 8,7);
    order.verify(board).setValueInCell(2, 8,7);
}

public boolean findSolution(Board board, int cell) {
    if (cell == SIZE*SIZE) return true;

    boolean wasEmpty = board.isEmpty(row(cell), col(cell));
    for (Integer value : board.getCellOptions(row(cell), col(cell))) {
        board.setValueInCell(value, row(cell), col(cell));
        if (findSolution(board, cell+1)) return true;
    }
    if (wasEmpty) board.clearValueInCell(row(cell), col(cell));

    return false;
}

@Test
public void shouldDisallowOptionsInSameRow() throws Exception {
    int row = 4;
    board.setValueInCell(1, row, 5);
    board.setValueInCell(2, row, 8);
    board.setValueInCell(3, row+1, 5);
    assertThat(board.getOptionsForCell(row, 0))
            .excludes(1,2).contains(3);
}

public List getOptionsForCell(int row, int col) {
    if (!isEmpty(row,col)) return Arrays.asList(cells[row][col]);
    List result = allOptions();
    removeAllInRow(result, row);
    removeAllInCol(result, col);
    removeAllInBox(result, row, col);
    return result;
}

TDD as a design guide

• With shorter iterations, the planning time may go down. But this takes practice - it doesn't happen automatically.
• With very short iterations, you may not have experienced enough to learn much from the retrospective. However, if you find that you do a timeline, and most of the things people remember happened the last week, it may not be because that's the only time something significant happened.
• You may consider different frequencies for different ceremonies. For example, on my current project we want to have demos with our power users. But they have to travel far to visit us. So we only have a full demo every other four weeks. We plan every two weeks and have an internal review and retrospective every two weeks.