I’m going to imitate Ron Jeffries. In his series of posts, Ron tried writing a sudoku solver using TDD (Test Driven Development) to see if the methodology works and what would happen. He eventually quit the project without completing it.
So I am going to write a sudoku solver, posting my progress as I go along. I’m going to try using TDD and document my thought process. Let’s see where I end up, if I manage it or quit and if we can learn something new along the way.
I’m doing this because I find it amusing to compare the thought processes of different programmers. I’d also like to try using TDD for real. I think it’s a cool project to do during my vacation in Bulgaria.
Just like for Ron’s case, if nothing, it might be fun to watch me quit crying.
What’s TDD?
I won’t go into too much detail here, just a quick recap for those who are not very familiar with TDD. Test Driven Development (TDD) is a development practice where tests are written before writing the code. Writing a test forces us to define the behavior of the code before trying to write out the implementation.
Proponents of TDD claim that this enables us to think about the interface and the requirements before diving into the code, possibly saving time. It also helps to have tests for refactoring and to be confident the code it doing what it’s supposed to do.
The Task
sudoku, in its common version, is a puzzle played on a 9x9 grid. Each number must appear in each row, column and box. The puzzle begins with some numbers already set and constraining the solution. Easy puzzles will have more constrains, difficult ones might leave some cells open with different possibilities so that many attempts might be necessary to solve the game. The image belows shown an unsolved sudoku.
An unsolved sudoku
I did solve some sudokus by hand some years ago, but I don’t know how to solve it algorithmically.
The Plan
I’ll use Java as an exercise to learn the language. My plan is to write a simple solver that tries all combinations until it finds one that works, as described in the “Backtracking” section of the Wikipedia article.
If I understood it right, the simplest algorithm is as follows: take the first empty cell, put 1 in there and checks if some constraint is violated (a row, column or box contain the same number twice). If not, move to the next cell, otherwise try with 2, then 3, 4 and so on until a valid digit is found. If a cell is found where no number is valid, move back to the previous cell and try the next number on that cell.
The Code
Let’s Dive In
I’m tempted to write a smart solver that takes some constraints into account. I think it would be more efficient. But that would be premature optimization, so I’d better start with a dumb solver and see if it’s fast enough, and change it later if not.
The algorithm above sounds simple and seems a good use case for recursion… I think I’ll write in a functional fashion even though I’m using Java.
Too bad, I should be thinking about the tests first, I’m doing TDD after all. I think I’ll use JUnit for the tests (it’s not important that you know what JUnit is and how it works to follow the code, I think it’s mostly self-explanatory. Actually you can also not know Java, the syntax is pretty easy if you know any C-like language). Uff, It took me at least half an hour just to find the way to install JUnit and configure maven. I told you I’m a java newbie!
To offset that, here the first test:
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SomeTest {
@Test
void test() {
assertEquals(2, 1+1);
}
}
Green! But let’s move on. This being Java, I am forced to write a class (free-standing functions do not exist). I could start writing the solver and testing for a solution, but that feels to overwhelming to do all at once.
Writing the Tests
I’ll start with a class to represent a sudoku. I will use an array of length 81 with row-major ordering, where the integers from 1-9 indicate a value in the grid cell and 0 indicates an empty cell (admittedly stolen from Ron).
public class Grid {
private final int[] array;
public Grid(int[] init) {
array = init;
}
}
Again, I’m thinking about the implementation first… Let’s quickly cover up this heresy with a test:
class GridTest {
@Test
void testConstruction() {
new Grid(new int[]{1, 2, 3});
}
}
Passes. I should be thinking a little about what makes a good Grid.
Theinit argument must have length 81 and the values must be in the
0-9 range (inclusive). So we can change the basic test to
something valid
@Test
void testConstruction() {
// 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,
});
}
I’ll add some test for the case the array’s length is wrong
@Test
void testConstructionWrongLength() {
assertThrows(
InvalidGridException.class,
() -> new Grid(new int[]{1, 2, 3})
);
}
Another tests case for when an array value is out of range:
@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,
})
);
}
For this test, I used a parameter that changes the tested value,
with some values too small, some too large. Each value is tested
separately, I passed the correct length (81) and tested the
boundary values -1 and 10. I also used the same
InvalidGridException class for both to keep it simple
(the class does not exist yet).
Now the test do not run. Maybe I should write each test, then fix it and then proceed instead of writing both at once. I still believe it’s not too bad to do both at once.
Tomorrow I have to go hiking, so I’ll stop here with the broken tests and go to bed.
Implementation: Making test Green
The hike was great, we delayed it by a day due to the weather and had great luck with it eventually. We’ve been to 2700 m and seen a lot of nice alpine lakes.
I left my project with broken tests the other day. Let’s now continue by fixing them. Firstly, add the exception class:
public class InvalidGridException extends Exception {
public InvalidGridException(String message) {
super(message);
}
}
Now at least the tests compile, but still fail. Then,
I’ll throw and exception if the size of the init
array is wrong:
public Grid(int[] init) throws InvalidGridException {
validateLength(init);
array = init;
}
private void validateLength(int[] init) throws InvalidGridException {
if (init.length != 81) {
throw new InvalidGridException("Array length must be 81 (9x9 grid).");
}
}
Similarly, I’ll check if the values are in range.
public Grid(int[] init) throws InvalidGridException {
validateLength(init);
validateValuesInRange(init);
array = init;
}
private void validateValuesInRange(int[] init) throws InvalidGridException {
for (int i = 0; i < init.length; ++i) {
int value = init[i];
if (value < 0 || value > 9) {
String message = String.format(
"Array value must be in the [0, 9] range, found %d at position %d",
value, i
);
throw new InvalidGridException(message);
}
}
}
Tests are passing now!
I wrote enough for the first post. I now have a basic Grid class
validating the grid values and encapsulating the game data.
I will use this class to start writing a solver in the next post.
See you soon!
The complete source of the code as shown in this post can be found at GitLab.
Next post of the series: sudoku, the solver interface