The code I wrote in the last post would use some refactoring. However, the tests are working, and I feel like I would be spending my time refactoring stuff that already works instead of trying to tackle the actual problem of solving a sudoku.

If you read “The Pragmatic Programmer”, the authors introduce the concept of “tracer bullets”. That is, a minimal version of the application that does something useful and works end to end. The idea is that, when you are unsure about what architecture to use for your code and whether you can finish the project at all, it’s a good idea to write a minimal working system and then refactor and improve iteratively from there. The other approach would be to develop and improve each component before passing to the next one.

The problem with this latter approach is that you cannot be sure you have a working system until very late in the development. It’s also very easy to waste time on developing a perfect component that will never be used because the project fails.

With this line of reasoning, I’ll leave the code in its ugly state, and continue writing the solver. I can improve the design of the code if I get the solver to work.

By the way, the book also motivated me to start this post series, and it has some solid programming advice, so read it!

Writing the Solver

Right now I have a Grid class encapsulating the puzzle state and a Solver.solve static method that takes an initial state and validates it. Right now it just returns the initial state, but I want to extend it so that it actually solves the sudoku.

The method currently looks like this:

public static Grid solve(Grid initialState) throws
    OutOfGridException,
    InvalidInitialStateException
{
    validateState(initialState);
    return initialState;
}

Very useful, I know! I had to bow to the compiler Gods somehow.

I stated in the first post that I want to solve this recursively with a simple algorithm. I explained the idea a little more in depth in the first post. Here I’ll briefly recap for people like me with a 23-second memory span.

The solver tries, for each empty cell, each digit from 1 to 9. When a valid digit is found, it continues to the next cell. If a cell is found where no digit is valid, it goes back to the next digit on the previous cell.

One simple implementation would be something like this… STOP! I was already typing in the implementation. I’m really not used to TDD. I should write a test first.

For this I really need a simple sudoku to solve. 2 minutes of browsing for some easy sudoku with solution and some typing bring me to this new test:

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

@Test
void testSolveSimple() throws
    InvalidGridException,
    OutOfGridException,
    InvalidInitialStateException
{
    Grid sudoku = new Grid(SIMPLE_SUDOKU);
    Grid solution = Solver.solve(sudoku);
    // Assert equal???
}

Now, I should at least get a Nobel Prize for typing precision if I do not have a single typo in there. But the test will fail if I got that wrong, so it’s fine.

Second, I need some way to compare two Grid instances. I could loop and use my accessor method, but I think this time I’ll try to add a better method to Grid.

Grid.equals() method

In Java, objects have a .equals() method, so I’ll write the test for it:

@Test
void testEquals() throws InvalidGridException {
    Grid grid1 = new Grid(KNOWN_GRID);
    Grid grid2 = new Grid(KNOWN_GRID);
    assertTrue(grid1.equals(grid2));
}

@Test
void testNotEquals() throws InvalidGridException {
    int[] reversedKnownGrid = IntStream
            .range(0, KNOWN_GRID.length)
            .map(i -> KNOWN_GRID[KNOWN_GRID.length-i-1])
            .toArray();

    Grid grid = new Grid(KNOWN_GRID);
    Grid reversedGrid = new Grid(reversedKnownGrid);
    assertFalse(grid.equals(reversedGrid));
}

For the second test, I’m using some IntStream magic I found on StackOverflow to reverse the array and generate a different grid.

The first test fails big time, but the second works. I think the problem is that the equals method is defined in Java for every object automatically, and it compares references. Reading that sentence again it does not make sense, I don’t know why is passes.

I have an urge to make the second test fail before starting, but I will resist it. I think the combination of both tests does indeed test for the right thing.

Let’s override the equals method for Grid:

public boolean equals(Grid other) {
    for (int i = 0; i < array.length; ++i) {
        if (array[i] != other.array[i]) return false;
    }
    return true;
}

Now that the tests are passing, we can fix the sudoku test:

@Test
void testSolveSimple() throws
    InvalidGridException,
    OutOfGridException,
    InvalidInitialStateException
{
    Grid sudoku = new Grid(SIMPLE_SUDOKU);
    Grid solution = Solver.solve(sudoku);
    assertTrue(solution.equals(SIMPLE_SUDOKU_SOLUTION));
}

So I fixed a test to make another fail properly. Sounds like progress to me.

A Tiny Refactoring Detour

While adding the Grid test I noticed that for some other Grid tests I am still using another array.

@Test
void testConstruction() throws InvalidGridException {
    // Valid values
    new Grid(new int[]{
            0, 0, 0, 0, 0, 0, 0, 0, 0,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
            1, 2, 3, 4, 5, 6, 7, 8, 9,
    });
}

@ParameterizedTest
@ValueSource(ints = {-5, -1, 10, 100})
void testConstructionOutOfRange(int value) {
    assertThrows(
            InvalidGridException.class,
            () -> new Grid(new int[]{
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
                1, 2, 3, 4, value, 6, 7, 8, 9,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
                1, 2, 3, 4, 5, 6, 7, 8, 9,
            })
    );
}

To remove some duplication and make the code a little shorter, I can use KNOWN_GRID there too:

@Test
void testConstruction() throws InvalidGridException {
    // Valid values
    new Grid(KNOWN_GRID);
}

@ParameterizedTest
@ValueSource(ints = {-5, -1, 10, 100})
void testConstructionOutOfRange(int value) {
    int[] data = KNOWN_GRID.clone();
    data[37] = value;
    assertThrows(
            InvalidGridException.class,
            () -> new Grid(data)
    );
}

Back to the Solver

So I now have a failing test for a single sudoku. I’m still a bit skeptical that it’s a small enough feature to implement all at once using TDD, but since I don’t know how else to proceed, I’ll give it a try.

Since it is a bit involved, I’m starting with this implementation partial code:

class Solution {
    public final boolean valid;
    public final Grid grid;

    public Solution(boolean valid, Grid grid) {
        this.valid = valid;
        this.grid = grid;
    }
}

class Solver {
    public static Grid solve(Grid initialState) throws
            OutOfGridException,
            InvalidInitialStateException
    {
        validateState(initialState);
        Solution solution = solveCell(initialState);
        if (!solution.valid) {
            // Throw an exception
        }
        return solution.grid;
    }

    static Solution solveCell(Grid state) {
        // 1. Find next empty cell
        // ...

        // 2. If no cell is empty, return state as solution!
        // ...

        int value = 0;
        Solution solution;
        do {
            ++value;

            // 3. Set value to state cell from (1)
            // ...

            // 4. Check solution validity
            // ...

            solution = solveCell(state);
        } while (!solution.valid);

        // No solution found, return invalid solution
        return new Solution(false, null);
    }
}

Firstly, I added a Solution private class to return multiple values from later methods. Secondly, after the initial state validation, I am now calling a new internal static method solveCell. If the solution exists, it returns a valid Solution object, if now, we have a condition that is not tested yet. I should add a test, but to avoid trying to tackle too many things at once, I’ll leave it undone for now.

Thirdly, the new solveCell method is supposed to do some things: (1) find the first empty cell, (2) if the cell does not exist we found a solution as the grid is full, (3) try different values for the cell, (4) check the validity of the state. All these things cannot yet be implemented because I miss some methods in Grid.

What can be implemented right now is the looping through values. If the value is valid, I recursively try to solve the next cell and check the result. If the result is not valid, I try the next value for this cell and repeat the procedure. Finally, if no valid value is found, I return an invalid Solution object.

This mostly implements the solver infrastructure, minus the edge case of invalid sudoku puzzles. I still miss most of the meat of the algorithm, that I have to implement in the Grid class:

  1. Find first empty cell.
  2. Generate new Grid from previous Grid by setting a value.

Extending Grid Again

The simplest way to represent a cell is its array index. I will treat this as an opaque pointer that can be passed in and out of a Grid object. -1 will mean that there is no empty cell.

Again here TDD forces me to think about a contract. With this settled, I can add two tests for finding the first empty cell:

@ParameterizedTest
@ValueSource(ints = {0, 1, 77})
void testFindEmptyCell(int index) throws InvalidGridException {
    int[] data = IntStream.generate(() -> 1).limit(81).toArray();
    data[index] = 0;

    Grid grid = new Grid(data);
    assertEquals(grid.findEmptyCell(), index);
}

@Test
void testFindEmptyCellNone() throws InvalidGridException {
    int[] data = IntStream.generate(() -> 1).limit(81).toArray();
    Grid grid = new Grid(data);
    assertEquals(grid.findEmptyCell(), -1);
}

In the first, I test that the index of the zero element is returned. On the second, I test that an array with no zero value returns -1.

I’ll write the code for this:

public int findEmptyCell() {
    for (int i = 0; i < array.length; ++i) {
        if (array[i] == 0) return i;
    }
    return -1;
}

Wow, my monitor is flashing in green. One thing still bothering me with this opaque indices is that they do not fit well with getCellValue. But that’s OK, as I am going to make that function disappear, I believe.

It’s late night here on my balcony in Sozopol. I have a great view of the harbour. I’ll stop for today. Tomorrow, I’ll try to add another function to “mutate” a Grid instance.

Extending Grid Again: Part 2

Sunny but windy day on the beaches of the Bulgarian Black Sea. It was worth a day of relax even if it’s late september and the water is rather cold.

Where did I leave? Oh yes, I need a method to generate a new modified Grid instance by replacing a value. Why generating a new instance instead of mutating the previous one? Because I’m working in a functional manner and immutable state is easier to manage and less bug prone. Let me try writing a test:

@Test
void testWithCell() throws InvalidGridException, OutOfGridException {
    Grid grid = new Grid(KNOWN_GRID);
    assertEquals(5, grid.getCellValue(6, 1));

    Grid newGrid = grid.withCell(15, 7);
    assertEquals(5, grid.getCellValue(6, 1));
    assertEquals(7, newGrid.getCellValue(6, 1));
}

withCell accepts two arguments: a cell pointer extracted with some other method and a value to set to the cell.

For this test, I’m assuming an GRID_SIZE of 9. The test would break if I change it. For now, I’m fine with it. I keep promising a refactoring, and I should not delay it by too much.

I should also test the error conditions:

@ParameterizedTest
@ValueSource(ints = {-10, -1, 81, 100})
void testWithCellOutOfBounds(int index) throws InvalidGridException {
    Grid grid = new Grid(KNOWN_GRID);
    assertThrows(
            OutOfGridException.class,
            () -> grid.withCell(index, 7)
    );
}

@ParameterizedTest
@ValueSource(ints = {-10, -1, 10, 100})
void testWithCellWrongValue(int value) throws InvalidGridException {
    Grid grid = new Grid(KNOWN_GRID);
    assertThrows(
            InvalidGridException.class,
            () -> grid.withCell(15, value)
    );
}

In the second case, I’ve been lazy and reused InvalidGridException, but I think it makes sense to have a single exception class for operations that lead to an invalid Grid such as length or value. I see no reason to add granular classes.

As usual, I’m testing some values including all boundary values.

My implementation of withCell looks like this:

public Grid withCell(int index, int value) throws OutOfGridException, InvalidGridException {
    if (index < 0 || index >= array.length) {
        throw new OutOfGridException(
                String.format("Invalid index %d", index)
        );
    }
    if (value < 0 || value > GRID_SIZE) {
        throw new InvalidGridException(
                String.format("Cannot set value %d to cell", value)
        );
    }
    int[] data = array.clone();
    data[index] = value;
    return new Grid(data);
}

More error checking code than implementation code? That’s how production-ready software looks like. Jokes aside, the JUnit is happy, so I am too!

Can We Please Finally Write This Solver?

Yes, I’ll try. Remember, we left it at this state:

static Solution solveCell(Grid state) {
    // 1. Find next empty cell
    // ...

    // 2. If no cell is empty, return state as solution!
    // ...

    int value = 0;
    Solution solution;
    do {
        ++value;

        // 3. Set value to state cell from (1)
        // ...

        // 4. Check solution validity
        // ...

        solution = solveCell(state);
    } while (!solution.valid);

    // No solution found, return invalid solution
    return new Solution(false, null);
}

So we can now implement a bunch of things:

static Solution solveCell(Grid state) throws OutOfGridException, InvalidGridException {
    int emptyCell = state.findEmptyCell();
    if (emptyCell == -1) {
        // All cells are filled
        return new Solution(true, state);
    }

    int value = 0;
    Solution solution;
    do {
        ++value;
        Grid newState = state.withCell(emptyCell, value);
        solution = solveCell(newState);
    } while (!solution.valid);

    // No solution found, return invalid solution
    return solution;
}

First, I changed solveCell(state), which was wrong, to solveCell(newState), which is right.

Second, I realized the looping logic is wrong. After exiting the while, the found solution should be returned.

Third, I also noticed that I do not have a stopping condition for my while to exit after 9. The return value is what I mistakenly put at the final return.

I’ll have to fix this immediately:

do {
    if (value == 9) {
        return new Solution(false, null);
    }
    ++value;
    Grid newState = state.withCell(emptyCell, value);
    solution = solveCell(newState);
} while (!solution.valid);

Now this sounds convincing. I still have another couple of comments:

  • That -1 is introducing coupling between the classes, as Solver needs to know how the index is implemented. I should make a static constant for this value.
  • I have the 9 here again.

But let’s run the test. Surprise, surprise, it fails! The problem now is that I do not have a way to inspect the states, so it’s hard to debug it.

Tonight I’ll stop here. This article is becoming very long. In the post, I’ve set up a test for the solver and implemented most of it, although it’s failing for an unknown reason. This is a big step forward that bring me closer to completion of the project, although I’m still ignoring a large chunk of refactoring in the hope of getting the solver to work first.

Will I manage to debug the solver? Did I say that I’ll refactor “later” meaning I’ll refactor never? Follow me in the next post to see what will happen.