The other day, in the first post of the series, I started writing a sudoku solver with TDD.

In particular, I wrote a simple Grid class to encapsulate the game’s state. I think it’s now time that we start writing a solver for the puzzle.

Solver Interface

As I’m trying to use TDD, I first need a test for the solver. To write a test I need to think of an interface. My first instinct would be to have a function taking a Grid with the initial state and returning a Grid with the solved sudoku. Some exceptions could happen if the sudoku has no solution or if the initial state is invalid.

The interface could be easily extended to use other types of solving algorithms through polymorphism if I make the function a class method, and that sounds cool to me.

I think this of thinking about the interface before jumping at the code is a benefit of TDD, but I should also not plan too much and see in practice how this works out.

I’ll start with a test for the validation of the initial state. If I pass an invalid initial state, the solver should throw an InvalidInitialStateException exception.

class SolverTest {
    @Test
    void testWrongInitialState() throws
            InvalidGridException,
            InvalidInitialStateException
    {
        Grid grid = new Grid(new int[]{
                1, 0, 0, 1, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
        });
        assertThrows(
                InvalidInitialStateException.class,
                () -> Solver.solve(grid)
        );
    }
}

The entrypoint of the algorithm is the Solver.solve static method.

Now that I wrote a basic test, I see that I should maybe test different types of errors. For instance: a duplicate in row, a duplicate in column and a duplicate in box. This is cool, because I will need the logic to perform the checks also in the algorithm and not only in the initial validation.

I’ll parametrize the test to test for the different scenarios above:

static final int[] DUPLICATE_ROW = {
        1, 0, 0, 1, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
};
static final int[] DUPLICATE_COLUMN = {
        0, 0, 0, 1, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 1, 0, 0, 0, 0, 0,
};<
static final int[] DUPLICATE_BOX = {
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 1, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 1, 0, 0,
};

static Stream<Grid> invalidGrids() throws InvalidGridException {
    return Stream.of(
            new Grid(DUPLICATE_ROW),
            new Grid(DUPLICATE_COLUMN),
            new Grid(DUPLICATE_BOX)
    );
}

@ParameterizedTest
@MethodSource("invalidGrids")
void testWrongInitialState(Grid grid) {
    assertThrows(
            InvalidInitialStateException.class,
            () -> Solver.solve(grid)
    );
}

Now, forget about the fancy JUnit syntax for passing arguments, what’s happening here is the test gets run three times, each time with a different grid with the various errors, and we expect an exception from it.

Now it does not compile, so let’s fix the tests by introducing the exception class boilerplate

public class InvalidInitialStateException extends Exception {
    public InvalidInitialStateException(String message) {
        super(message);
    }
}

After that, I’m adding a Solver class that does nothing

class Solver {
    public static Grid solve(Grid initialState) {
        return initialState;
    }
}

For now, I’m returning initialState just to please the compiler. The tests are now running but fail.

I’ll head straight into implementing the validation logic. I’m adding a function to validate the rows:

static void validateRows(Grid state) {
    for (int row = 0; row < 9; ++row) {
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < 9;++i) {
            // Need to get value of state at row*9 + i
        }
    }
}

Writing this, I realized I need some accessor method to get the value of a cell from the Grid.

Grid Accessor Method

I’ll quickly make one, but I have to leave the Solver tests broken for a while. I’ll first add another couple of tests for my cell accessor method:

static final int[] KNOWN_GRID = {
        0, 1, 2, 3, 4, 5, 6, 7, 8,
        9, 0, 1, 2, 3, 4, 5, 6, 7,
        8, 9, 0, 1, 2, 3, 4, 5, 6,
        7, 8, 9, 0, 1, 2, 3, 4, 5,
        6, 7, 8, 9, 0, 1, 2, 3, 4,
        5, 6, 7, 8, 9, 0, 1, 2, 3,
        4, 5, 6, 7, 8, 9, 0, 1, 2,
        3, 4, 5, 6, 7, 8, 9, 0, 1,
        2, 3, 4, 5, 6, 7, 8, 9, 0,
};

@Test
void testGetCellValue() throws InvalidGridException {
    Grid grid = new Grid(KNOWN_GRID);
    assertEquals(grid.getCellValue(0, 1), 9);
    assertEquals(grid.getCellValue(7, 4), 7);
    assertEquals(grid.getCellValue(8, 8), 0);
    assertEquals(grid.getCellValue(8, 0), 9);
    assertEquals(grid.getCellValue(0, 8), 2);
}

I created the KNOWN_GRID by just typing 0, 1, …, 9 repeatedly into the array. This grid seems to have some interesting properties; in particular rows and columns with the same index are different, which is good for testing.

I then picked some values, avoiding the diagonal (because there it’s difficult to spot indexing mistakes in the code) and picking the top-right and bottom-left corners. I also picked a random coordinate pair.

I’ll also add a test for an exception when the coordinates are out of bounds. For this I’ll check some values that are too large, too small, and the boundary values (9 is out of the grid since indices start from 0).

@ParameterizedTest
@ValueSource(ints = {-500, -1, 9, 100})
void testGetCellValueErrors(int value) throws InvalidGridException {
    Grid grid = new Grid(KNOWN_GRID);
    assertThrows(
            OutOfGridException.class,
            () -> grid.getCellValue(value,5)
    );
    assertThrows(
            OutOfGridException.class,
            () -> grid.getCellValue(5, value)
    );
}

Cool. I’m a little scared I’m spending more time to write validation for edge cases and exception classes than trying to solve the puzzle. But TTD seems to call for this line of action, so let’s continue and see if it leads me to project doom.

To fix these last two tests (ignoring the others), I’ll make the boilerplate for the new exception. Maybe I should simply have started with a single exception class, but it’s a little too late now. I’ll refactor later if this is too detailed:

public class OutOfGridException extends Exception {
    public OutOfGridException(String message) {
        super(message);
    }
}

Then, I’ll write the accessor:

public int getCellValue(int x, int y) throws OutOfGridException {
    if (x < 0 || x >= 9 || y < 0 || y >= 9) {
        throw new OutOfGridException(String.format(
                "Coordinate out of grid bounds: x=%d,y=%d"
                x, y
        ));
    }
    return array[y*9 + x];
}

The second test is passing, but damn, the first fails!

org.opentest4j.AssertionFailedError:
Expected :3
Actual   :7

I confused x with y when setting the assertion true value, so the test is wrong. It should be

assertEquals(grid.getCellValue(7, 4), 3);

It still fails:

org.opentest4j.AssertionFailedError:
Expected :8
Actual   :9

I am puzzled at first. I need to swap the arguments to assertEquals, otherwise the error message inverts actual with expected… I even ignored my IDE’s hints.

Still the test fails, because I set 9 as actual value, but it should be 8 as above. No way I was getting that right the first time :-). Sneaky.

So the final version of the tests is:

@Test
void testGetCellValue() throws InvalidGridException, OutOfGridException {
    Grid grid = new Grid(KNOWN_GRID);
    assertEquals(9, grid.getCellValue(0, 1));
    assertEquals(3, grid.getCellValue(7, 4));
    assertEquals(0, grid.getCellValue(8, 8));
    assertEquals(8, grid.getCellValue(8, 0));
    assertEquals(2, grid.getCellValue(0, 8));
}

A Little Refactoring

My getCellValue method looks like this

public int getCellValue(int x, int y) throws OutOfGridException {
    if (x < 0 || x >= 9 || y < 0 || y >= 9) {
        throw new OutOfGridException(String.format(
                "Coordinate out of grid bounds: x=%d,y=%d"
                x, y
        ));
    }
    return array[y*9 + x];
}

Are you bothered that I’m catching everything with a single huge if and that my exception a bit generic? I’m not disturbed, what I do not like is the 9 magic number. I’m using that all over the place.

Making a static constant is easy:

final int GRID_SIZE = 9;

public int getCellValue(int x, int y) throws OutOfGridException {
    if (x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE) {
        throw new OutOfGridException(String.format(
                "Coordinate out of grid bounds: x=%d,y=%d",
                x, y
        ));
    }
    return array[y*GRID_SIZE + x];
}

Since, I’m at it, I replaced the other places where 9 is used in this class and replaced them with the constant. I also changed the function validating the array length:

final int ARRAY_LENGTH = GRID_SIZE*GRID_SIZE;

void validateLength(int[] init) throws InvalidGridException {
    if (init.length != ARRAY_LENGTH) {
        throw new InvalidGridException(String.format(
            "Array length must be %d (%dx%d grid).",
            ARRAY_LENGTH, GRID_SIZE, GRID_SIZE
        ));
    }
}

Now, that’s DRY (Don’t Repeat Yourself). I can change the grid size in a single place.

Going Back to the Solver

After this long detour, let’s go back to the solver implementation. I was trying to write a function to validate the rows:

static void validateRows(Grid state) {
    for (int row = 0; row < 9; ++row) {
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < 9;++i) {
            // Need to get value of state at row*9 + i
        }
    }
}

I can now use getCellValue to get the cell values and complete the validation:

static void validateRows(Grid state) throws
        OutOfGridException,
        InvalidInitialStateException
{
    for (int row = 0; row < 9; ++row) {
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < 9; ++i) {
             int value = state.getCellValue(i, row);
             if (value == 0) continue;
             if (visited.contains(value)) {
                 throw new InvalidInitialStateException(String.format(
                         "Row %d contains duplicate value %d",
                         row, value
                 ));
             }
             visited.add(value);
        }
    }
}

I like to put as much data as possible in my error messages, I think it makes it easier to debug the problems later. It would be cool to print the entire Grid instance, but that would require a bunch of extra printing logic. I’ll tackle that later if I need it.

Anyhow, one of the tests is now green! To fix another, I’ll copy-paste the function and slightly change it to check the columns:

static void validateColumns(Grid state) throws
        OutOfGridException,
        InvalidInitialStateException
{
    for (int col = 0; col < 9; ++col) {
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < 9; ++i) {
            int value = state.getCellValue(col, i);
            if (value == 0) continue;
            if (visited.contains(value)) {
                throw new InvalidInitialStateException(String.format(
                        "Column %d contains duplicate value %d",
                        col, value
                ));
            }
            visited.add(value);
        }
    }
}

Another test is green. The final validation function for the boxes is a little more involved:

static void validateBoxes(Grid state) throws
        OutOfGridException,
        InvalidInitialStateException
{
    for (int startRow = 0; startRow < 9; startRow += 3) {
        for (int startCol = 0; startCol < 9; startCol += 3) {
            Set<Integer> visited = new HashSet<>();
            for (int row = startRow; row < startRow + 3; ++row) {
                for (int col = startCol; col < startCol + 3; ++col) {
                    int value = state.getCellValue(col, row);
                    if (value == 0) continue;
                    if (visited.contains(value)) {
                        throw new InvalidInitialStateException(String.format(
                                "Box at (%d, %d) contains duplicate value %d",
                                startRow, startCol, value
                        ));
                    }
                    visited.add(value);
                }
            }
        }
    }
}

That’s a monster. If they see me at work writing this stuff, I’ll get fired immediately. I’ll keep this post hidden from them just to be sure. But hey, all tests are now successful, so I’m done! I’ll see if I can refactor it next time.

One thing which is really annoying is that I’m again using this magic number 9 in the code. My first thought was making a public method in Grid to access it, but then it sounds code smell of one class that wants to use internal data of the other. Probably I should have methods in Grid to fetch rows instead of exposing internals of the class. After all, why should Solver loop itself over cells if it can ask Grid to do it?

Another violation of DRY is that the validation functions all look similar. Probably, that would also be solved by letting Grid to more work of selecting data and delegating the validation to a single method.

Maybe then writing an accessor for a cell was not the best idea. I’ll keep you posted on how I’ll fix this or choose to ignore it in the next post. See you soon!

You can find the state of the code for this post in this commit at GitLab.