A Hierarchy of Abstractions

So far we've seen two lattices: the concrete powerset lattice and the abstract partial-assignment lattice. But there's nothing special about having exactly two — we can stack multiple levels of abstraction, each connected by a Galois connection.

For Sudoku, three natural levels emerge:

𝒫(Loc → N) is the powerset lattice from step 3 — the most precise representation. It tracks every possible complete grid, but storing and manipulating sets of grids is expensive.

Loc → 𝒫(N) tracks, for each cell, the set of numbers still possible there. This is what Sudoku players do when they "pencil in" candidates. What do we lose? Relational information. We know which numbers are possible at each cell, but not which combinations across cells are jointly possible.

Loc → (N ∪ {⊥, ⊤}) is the partial-assignment lattice from the beginning — for each cell, we either know its value for certain, or we don't. This is the cheapest representation: we only keep what we're sure about, discarding even the pencil marks.

Each pair of levels is connected by a Galois connection. Moving down the hierarchy, we trade precision for efficiency. Here are three grids and what each level of abstraction sees. Hover over a grid thumbnail:

The choice of which level to work at depends on how much precision we need and how much computation we can afford.