what it is

Sudoku is that puzzle commuters do on the train or bus when their smartphone’s battery is dying and playing Angry Birds or Fruit Ninja isn’t a viable option.

In your standard sudoku, you have a 9 × 9 cell grid, subdivided into nine 3 × 3 boxes. Some of the cells have starting digits from one to nine in them, and the goal is to fill in the empty cells so that each digit from one to nine appears each row, column and box exactly once.

ersatz man page

java -jar Sudoku [--width=w] [--height=h] "puzzle" where

--width

the width of a box, optional if the boxes are square

--height

the height of a box, optional if the boxes are square

--puzzle

the initial puzzle, as a string of numbers or letters separated by non-alphanumeric, non-space characters. If the sudoku has \(w\) cells to a row, then the \(rw + c\)th alphanumeric or space character in the puzzle sequence is the initial value of the cell in row \(r\), column \(c\). One or more space characters represents an initially empty cell.

Example 1:

The command to input and solve this puzzle might be something like the long and awkward:

java -jar Sudoku.jar --width=5 --height=2 "[1| | | | | |9|8| | ][8|9| | | |6| | |5|3][ | |9|10| | | | | |8][6| | | |3| | | |1|2][ |10| | |6| | |7|3| ][ |2|4| | |9| | |10| ][4|3| | | |5| | | |6][5| | | | | |2|3| | ][10|6| | | |1| | |7|9][ | |7|3| | | | | |4]" 

The brackets delineating each row aren’t strictly necessary, but they make the command (slightly) easier to read, at least in my opinion.

Also viable is the equally awkward PHP Markdown Extra code that makes the sudoku in the first place:

java -jar Sudoku.jar --width=5 --height=2 "| 1|  |  |  |  |  | 9| 8|  |  |
| 8| 9|  |  |  | 6|  |  | 5| 3|
|  |  | 9|10|  |  |  |  |  | 8|
| 6|  |  |  | 3|  |  |  | 1| 2|
|  |10|  |  | 6|  |  | 7| 3|  |
|  | 2| 4|  |  | 9|  |  |10|  |
| 4| 3|  |  |  | 5|  |  |  | 6|
| 5|  |  |  |  |  | 2| 3|  |  |
|10| 6|  |  |  | 1|  |  | 7| 9|
|  |  | 7| 3|  |  |  |  |  | 4|"

Example 2:

The --width and --height parameters aren’t necessary since the puzzle is a square.

java -jar Sudoku.jar ", , , ,3,5, , , , ,, ,1, , , ,8, , , ,, , , ,1, , ,6, ,4,, ,6, ,5, ,2,4, ,9,,8, , , , , , , ,6,,7, ,9,8, ,1, ,2, ,,1, ,3, , ,4, , , ,, , , ,7, , , ,9, ,, , , , ,9,5, , , ,"

On the surface, sudoku seems like a prime candidate to tackle with an algorithmic solver. It turns out that sudoku is a prime candidate for an algorithmic solver, just not the algorithm I thought it would be. One of the most interesting discoveries I made while designing this code was the enormous gulf between the sudoku solver in my head and the sudoku solver in bits and bytes. Consider the sudoku in Figure 1, which I preprocessed, notating each cell with its candidate digits.

I guess I can’t really speak for your mind, but when I see that puzzle, there are a bunch of cells and regions that jump out at me. A quick glimpse tells me that in the center box (or the fourth column), the only cell with 3 as a candidate digit is \(r6c4\). In the fourth row, cells \(r4c5\) and \(r4c6\) share the candidate digits \(\{5,9\}\), which implies that none of \(r4c1\), \(r4c2\) or \(r4c3\) can be 5 and \(r4c8\) cannot be 9.

As an even more complicated example, row 6 can be partitioned into two sets. Since there is a set of cells \(S = \{r6c4, r6c7, r6c8, r6c9\}\) with cardinality 4 and the candidate digits of all the members of \(S\) are in the set \(T = \{1,3,4,9\}\), also with cardinality 4, we know that the empty cells that are not in \(S\) must have only candidate digits that are not in \(T\). Unfortunately, getting an algorithm to find this partition is far from trivial. Maybe find the power set \(\mathcal{P}\) of the candidate digits for the row, iterate over each element \(e \in \mathcal{P}\) and every permutation of \(|e|\) cells and see if the candidates…

It’s more trouble than its worth, mimicking my thought process. But the good news is that computers have enough of the electronic equivalent of patience to solve the problem in a way that I’d never consider: trial and error. And the nature of the problem gives us a relatively intelligent way to minimize the number of trials and errors, by reframing sudoku as an exact cover problem and approaching it in a systematic way.

Logic problem → constraint satisfaction problem

Candidates: Let’s define a sort of structure that associates a digit with a cell and call said structure a Candidate:

static class Candidate {
    final int r, c, d;
    
    Candidate(final int r, final int c, final int d) {
        this.r = r;
        this.c = c;
        this.d = d;
    }
    
    /* ... */
}

The candidate \(\left(r,c,d\right)\) represents the digit \(d\) in the cell at row \(r\) and column \(c\). In Figure 1, the candidates \(\left(6,1,8\right)\) and \(\left(4,9,2\right)\) are among the givens. Many candidates trivially conflict with the puzzle, such as \(\left(2,6,1\right)\): we know that cell \(r2c6\) cannot be 1 since that cell is 8.

The puzzle starts with a Set<Candidate> candidates, one element in candidates for each given in the puzzle. For the puzzle in Figure 1, we’d start with something like:

Set<Sudoku.Candidate> s = new HashSet<Sudoku.Candidate>();
s.add(new Sudoku.Candidate(1,1,2));
s.add(new Sudoku.Candidate(1,6,4));
s.add(new Sudoku.Candidate(1,9,6));
s.add(new Sudoku.Candidate(2,2,1));
...
s.add(new Sudoku.Candidate(9,4,5));
s.add(new Sudoku.Candidate(9,9,1));
sudoku = new Sudoku(9, s);

Then the solution is a Set<Candidate> with size * size elements, such that none of the set’s elements violate the puzzle’s constraints. Speaking of which…

Constraints: Each Constraint in the puzzle is also a Set<Candidate>, some subset of the universe of candidates:

static class Constraint {
    Set<Candidate> candidates;
    
    Constraint(final Set<Candidate> candidates) {
        this.candidates = candidates;
    }

    /* ... */
}

A Set<Candidate> s satisfies a Constraint c iff there is exactly one candidate x such that s.contains(x) && c.candidates.contains(x). The solution is the set of candidates that satisfies all of the puzzle’s constraints.

Each candidate is in four constraints, one each of the following types:

• row-digit constraint: Each digit must appear in exactly one cell in each row.

• column-digit constraint: Each digit must appear in exactly one cell in each column.

• box-digit constraint: Each digit must appear in exactly one cell in each box.

• row-column constraint: Each cell must have exactly one digit in it.

Each constraint is uniquely labeled by two digits, so it makes sense to store the constraints in a com.google.guava.commons.collections.Table. There are four tables, one for the row-digit constraints, one for the column-digit constraints, one for the box-digit constraints, and one for the row-column constraints:

Table<Integer, Integer, Set<Candidate>> rowColumnConstraints = HashBasedTable.create(digits, digits), /* ... */;

for(Candidate candidate : candidates) {
    rowColumnConstraints.get(candidate.r - 1, candidate.c - 1).add(candidate);
    rowDigitConstraints.get(candidate.r - 1, candidate.d - 1).add(candidate);
    columnDigitConstraints.get(candidate.c - 1, candidate.d - 1).add(candidate);
    boxDigitConstraints.get((candidate.r - 1) / rows * rows + (candidate.c - 1) / columns, candidate.d - 1).add(candidate);
}

That is, for Table t, t.get(row, column) returns a Constraint c. A Constraint is a wrapper for a Set<Candidate>. c.add(candidate) delegates to c.candidates.add(candidate). By the end of the loop, each candidate \(\left(r,c,d\right)\) appears in one constraint in each table, provided that there isn’t a given \(d\) in the same row, column, or box as cell \(\left(r,c\right)\).

Unfortunately, the Candidates are one-indexed while the Table is zero-indexed, hence the gratuitious subtraction.

It’s convenient that I have a computer to generate all two-hundred constraints for the problem (there are 50 empty squares and each empty square appears once as each of the four types of constraints), or else I’d go mad. Or madder.

Bonus!

We have a set of candidates — call it \(C\) — and a set of constraints, and the goal is to find a subset of \(C\) that satisfies each constraint.

More generally let’s say we have sets \(P\) and \(Q\) and a binary relation \(R \subseteq P \times Q\). Then the exact cover problem is to find a subset \(P^{\ast}\) of \(P\) such that for each member of \(Q\), \(R^{-1}\) obtains for exactly one element in \(P^{\ast}\). Here, \(P\) is the set of candidates, \(Q\) is the set of constraints, and \(R\) is the relation “is an element of”.

With this generalization, we can expand the sudoku framework into an exact cover problem framework, which I’ve conveniently provided for you. I also included a pentomino solver, just as another example of putting this generalization to work on another, superficially different, exact cover problem.

Algorithm X

My algorithm for solving exact cover problems is called Algorithm X, apparently because no better name could be found for it. I pretty much copied it straight from Donald Knuth’s original paper, which is downloadable here, and translated it into Java.

The heart of the algorithm is the toric grid of intersecting circular doubly-linked lists, encapsulated in the ExactCoverProblem<P,Q>.Node object:

class Node {
    Node up, down, left, right;
    P elementP;
    /* ... */
}

The Constraints are represented as circular doubly-linked lists where each Node in the list (except for the header node) wraps a Candidate covered by the Constraint. They’re labeled in ExactCoverProblem<P,Q>.ColumnHeader nodes:

class ColumnHeader extends Node {
    Q elementQ;
    /* ... */
    
    public ColumnHeader(final Q element) {
        this.elementQ = element;
        up = down = column = this;
    }
    /* ... */
}

For any Node n, n.up and n.down point to another node wrapping a Candidate covered by one of the Constraints that covers n (or they point to the ColumnHeader, which makes for a great sentinel value while iterating over the list). n.right and n.left point to another node wrapping n, although under a different Constraint.

The idea behind this data structure is that, as long as we iterate to the right and down, we can hide a node m by calling m.right = m.right.right and m.down = m.down.down. BUT if we iterate to the left and up, we can unhide m by calling m.left.right = m and m.up.down = m. This fact probably has many applications, although I can’t think of them right now.

The rest of the exact cover problem is surprisingly straightforward, and I can’t think of anything profound to say about it. So I’ll shut up.