Welcome to the first post of the second season of Simple Sudoku Solvers! If you are unfamiliar with the series, I suggest you start with the first post, otherwise buckle up, because we are going to look at a lot of strange symbols today!
Today we’re going to look at APL, a strange old language fallen out of time known for its terseness and strange alien symbols. Truth be told, I could never get into it, and still can’t. Nonetheless, writing a Sudoku solver seemed like the perfect weird challenge to get my hands dirty on and give it an honest shot. And now I’m going to share the bloody results with you!
Fair warning: in my efforts to make this code as “APL-like” as possible, I’ve done a few iterations of golfing on it. Now the program truly looks like APL, but might also be somewhat inscrutable to those not in the know. To be clear, if I hadn’t written this code, I probably would have trouble following it myself.
Another thing to note is that in this installment, contrary to prior episodes, I will try to explain more or less every expression, in an attempt to be a bit friendlier to my reader.
With all of the encouraging stuff out of the way, let’s dive right in!
Why APL?
APL is a language that looks like someone spilled a box of alien maths onto your screen and then insisted this was a good idea. And maybe they were right, I’m not smart enough to answer this question.
A few things make APL a fun fit for Sudoku even for mere mortals:
- Everything is an array. Sudoku is a 9×9 array problem. Matrices and arrays are APL’s food. It sounds like a match made in heaven.
- Decoding indices and slicing submatrices is built-in. We essentially just lean on basic operators to slice and dice our rows, columns, and boxes.
- Set-ish operations are effortless. “Candidates are digits minus used digits” is basically one operator. So is everything else if you’re creative enough.
- Conciseness is not optional. APL will not let you hide from your data model: if you choose a representation that’s awkward, it will show immediately. It is also unforgiving toward clarity of thought, which is both scary and cool.
This post is not an APL primer. Hopefully I’ll explain enough to follow along, but if you’ve never used APL before, the best strategy is: keep reading, copy/paste code into an interpreter, and allow yourself to be confused for a bit.
The dialect of APL I’m using is Dyalog APL, which seems to be the
industry standard as far as I can tell. It’s a commercial offering, but
you can download the engine and IDE for free if you’re using it mostly
for play like me. It also comes with a program called
dyalogscript, which is a way of running Dyalog programs
from the terminal instead of their somewhat foreign IDE. Unfortunately
it’s pretty underspecified and typing APL is awkward to begin with, so I
spent way too much time trying to get this part to work. I recommend
just running it in their environment instead.
The implementation
As always, we initially represent the board as a matrix (9x9), where
0 means “empty” and 1..9 are known digits. The
solver is the basic shape of filling, MRV, and backtracking/depth-first
search. This time, however, we’ll lean harder on array operations for
candidate computation, and keep everything else simple and obvious
(well, if you know how to read it).
In this installment, we’ll use the 9-bit boolean mask trick we’ve used in previous installments to add extra flavor and because its uniform length plays well with APL’s standard operations. It forces us to compute masks and convert stuff, but since our actual implementation is only ten ultra terse lines, we can afford it.
Importantly, internally we’ll deal with a single array of 81 values
to facilitate quicker operations. So we’ll start by getting a matrix,
and then flatten it, before printing it as a 9x9 matrix instead. The
high-level looks like this (⍝ is the comment
delimiter):
⍝ input matrix m (← is the assignment operator)
m←↑(
(0 0 3 0 2 0 6 0 0)
(9 0 0 3 0 5 0 0 1)
(0 0 1 8 0 6 4 0 0)
(0 0 8 1 0 2 9 0 0)
(7 0 0 0 0 0 0 0 8)
(0 0 6 7 0 8 2 0 0)
(0 0 2 6 0 9 5 0 0)
(8 0 0 2 0 3 0 0 9)
(0 0 5 0 1 0 3 0 0)
)
⍝ flattened p
p←,m
⍝ S is the solver, 9 9⍴ prints it, assigning to ⎕ prints
⎕←9 9⍴S pWe also set indexing to be 0-based (it’s 1-based by default), and
compute the space of possible digits D:
⍝ the ⋄ sigil separates multiple expressions on one line
⎕IO←0 ⋄ D←1+⍳9With that out of the way, let’s look at the algorithm!
The main solver
Staying true to the terseness of APL, we named the main solver
function S. It’s a unary function, and in APL we receive
that argument as ⍵. With that out of the way, the rest of
the algorithm should be self-evident:
S←{
b←P ⍵ ⋄ 0=≢b:⍬ ⋄ ~0∊b:b
i←⍸0=b ⋄ cs←↑(b∘C)¨i ⋄ l←+/cs ⋄ k←l⍳⌊/l ⋄ idx←i[k]
sols←(⊂∘∇)¨({(⍵@idx)⊢b}¨cs[k;]/D)
⊃(((0<(≢∘⊃)¨sols)/sols),⊂⍬)
}Sarcasm notwithstanding, the code is actually not as bad as it looks.
We start by propagating using P—more on that below—, and
assigning that to b. We return ⍬ if we get it
from P here, since this is our unsatisfiability marker
(0=≢b:⍬). If there are no zeros on the board, on the other
hand, we are done and return the board b
(~0∊b:b).
With the preconditions out of the way, we can move on to the main
branching algorithm. We get the indices i of the cells set
to zero (i←⍸0=b) and compute the candidates
(cs←↑(b∘C)¨i) and their respective counts
(l←+/cs). We then pick the cell with the fewest candidates
(k←l⍳⌊/l) and find its index (idx←i[k]).
After all of this, we are ready to solve the branches. We turn the
9-bit mask into the candidate digits (cs[k;]/D), and
produce a new board for all of them ({(⍵@idx)⊢b}¨,
idx being the index, and @ the
functional/copying update). We pipe that into the solver, box each
result, and assign the vector of boxes to sols
(sols←(⊂∘∇)¨). All of that is one expression.
Finally, we just need to return the first match. We unbox each
solution and get its length ((≢∘⊃)¨sols), filter for the
non-empty ones (0<), and take the first one, returning
⍬ if we can’t find anything (⊂⍬).
Quick sidenote: you might ask yourself why we box sols
just to unbox it again. This is due to a feature of Dyalog APL, which
will happily mix the results of ∇¨ into a regular array if
it can, which breaks our filter/take first logic. Dyalog’s shape
coercion rule details are a bit much to get into here, but you can just
think of it as “if the shapes fit, smush them”, and that’s not what we
want here.
So, what we still need to define for this to click is the candidate
search C and propagation P.
Propagation
We will now tackle propagation, which thankfully is a bit less involved (the next part will be simpler still!):
P←{
b←⍵ ⋄ i←⍸0=b ⋄ 0=≢i:b
cs←↑(b∘C)¨i ⋄ l←+/cs ⋄ 0∊l:⍬
f←l=1 ⋄ ~∨/f:b
b[f/i]←(f⌿cs)+.×D ⋄ ∇b
}To remind ourselves: here we repeatedly fill any cell that has
exactly one candidate until we cannot any longer. We return
⍬ on contradiction.
First, we assign our argument to b, because I’m a wuss
who wants descriptive names (b←⍵). Then, we get the indices
of empty cells again (i←⍸0=b, identical to above), and
compute the candidates (cs←↑(b∘C)¨i, again the same) and
their counts (l←+/cs). Here we need to guard against
impossibility: if any empty cell has 0 candidates, the current board is
impossible and we return ⍬ (0∊l:⍬). Then we
get the boolean masks of all cells with exactly one candidate
(f←l=1) and again guard: if there are no cells we can fill,
we return the board (~∨/f:b).
Finally, we can fill the board (b[f/i]←(f⌿cs)+.×D)! This
boils down to just getting the indices of what we need to fill
(f/i), selecting the corresponding masks
(f⌿cs), and converting it to a digit by computing the dot
product between rows and D ((+.×D)). The rest is an array
assignment.
The last expression is tail recursion: we will try to go for another
round of propagation (∇b).
Candidate search
Compared to the previous snippets, candidate search is almost easy to grasp:
C←{
m←9 9⍴⍺ ⋄ r c←9 9⊤⍵ ⋄ r0 c0←3×⌊(r c)÷3
~(D∊0~⍨∪m[r;],m[;c],,m[r0+⍳3;c0+⍳3])
}Here we get a board and index and compute a mask. In “dyadic” APL
functions (one argument goes left and one goes right in the call), the
arguments are ⍺ and ⍵.
So first we reshape the board back into a 9x9 matrix
(m←9 9⍴⍺), because rows, columns, and boxes fall out of
that more easily. We then decode the index into a row/column index pair
(r c←9 9⊤⍵) that we can use for the matrix and get the
start index of the box (r0 c0←3×⌊(r c)÷3, either
0, 3, or 6). We then collect the
row, column, and box values
(m[r;], m[;c], ,m[r0+⍳3; c0+⍳3]), make sure they’re unique
(∪), and remove 0 (0~⍨). We then turn it into
a candidate mask (~(D∊<expr>)) and return it!
In my opinion, this is where APL truly shines. Being able to easily express column, row, and box indices is a superpower you only get from a language that takes arrays and matrices as fundamental.
And this concludes our tour de force! Congratulations, you made it!
Fin
I don’t really know much about APL, but I think we did a pretty good
job of staying faithful to how you can work with it. I probably missed a
whole bunch of things that are obvious to more experienced sigil
slingers, but the easy immutable updating using @,
incredibly simple candidate selection, and very declarative search
algorithm (despite the scary syntax, it felt like just describing “solve
map over candidates, then pick first non-empty“) really did resonate
with me.
Thank you for tuning in for the first part of the second season of our little Sudoku solver series. The next few episodes should be somewhat less esoteric while still scratching that “mind-bending” itch. See you around!