This is a recreational, summer question and could be more well-suited for mathstackexchange. However, some of you on holiday could appreciate the topic. I recently came across Kakuro Puzzles, similar to crosswords but with numbers. Rows and columns (in the following entries) have a clue, and cells must be filled with non-zero digits so that:
- The digits in each entry are distinct;
- The digits in each entry sum up to the clue on the entry.
I have realized that the existence of a (unique) solution can be formulated in terms of (constructible) sheaves, and I was wondering whether this geometric formulation could be used to infer some interesting rules about solving or constructing kakuro puzzles. For example, if the involved sheaves were locally constant on a manifold, one could use the correspondence with representations of the fundamental group and check the action; however, the space is not smooth. Let me briefly outline the construction.
Kakuro puzzles
Abstractly, a Kakuro puzzle comes with:
- A set $C$ of cells;
- A set $A$ of entries;
- A subset of cells $C_a \subset C$ for each entry $a \in A$;
- A clue $s_a \in \mathbb{N}_{> 0}$ for each entry $a \in A$.
We will also write $\Sigma := \{1, \ldots, 9\}$ for the allowed set of fillings, and $n(a) : = |C_a|$ for the length of an entry.
Kakuro space
Let me construct the space where our sheaves live. The space $X$ associated to a kakuro puzzle is just a grid with one vertex for each cell, and (vertically or horizontally) adjacent vertices connected by a segment. It is 1-dimensional simplicial complex, simple to visualize on the puzzle itself. For each entry $a \in A$, we define the associated subspace $X_a$ as the subcomplex generated by vertices on cells $c \in C_a$.
Kakuro sheaf
Now let me sketch the definition of the sheaf of sets $\mathcal{F}$. Preliminarily, note that there is a simple sheaf $\Sigma_X$ such that $\Sigma_X(c) = \Sigma $ for each cell $c$, $\Sigma_X(cc') = \Sigma^2$ for any segment between cells $c,c'$ , and in general $\Sigma_X(Y) \simeq \Sigma^{Y_0}$ (the set of vertices for any closed subcomplex $Y \subset X$. I am unsure about how to compactly define sheaves on stratified spaces, but I guess this is enough.
Each entry has a finite number of digit sequences that respect the constraints. For example, the only way (up to permutation) to write $10$ as the sum of $4$ digits is $10=1+2+3+4$. In general, let us define $$ L(n,m) := \{ (a_1, \ldots, a_m) \in \Sigma^m: a_1+ \ldots + a_m = n, \ \ \ a_i \neq a_j \} $$ where $\Sigma := \{1, \ldots, 9\}$ is the set of digits.
Define $\mathcal{F}(X_a)$ as $L(s_a, n(a) )$, that is sequences that respect the clue and have the prescribed number of cells. Note that $S_{n(a)}$ acts freely on this space since digits are distinct, despite I am not sure if this has an application.
We want to extend this construction to a sheaf on $X_a$. In particular, it will be a subsheaf of $\Sigma_{X_a}$. Let $\pi^{X_a}_U : \Sigma(X_a) \to \Sigma(U)$ be the projection operator for any $U \subset X_a$. For example, if $U = \{c\} \subset C_a$, the map is just the projection of the sequence to the digit on that cell. For any $U \subset X_a$, define $\mathcal{F}(U)$ to be $\pi_U(\mathcal{F}(X_a))$.
At last, we want to glue the sheaves defined on the various $X_a$'s. At the moment, we are not sure that the sheaves agree at the intersection, so that we have to modify the single sheaves a bit. This is a first coarse step in the resolution. For each $c \in C$, there are at most two entries $a=v(c), h(c)$ such that $c \in C_a$: a vertical and a horizontal one. Define $W(c)$ as the intersection in $\Sigma$ of $\mathcal{F}_{h(c)}(c)$ and $\mathcal{F}_{v(c)}(c)$. These are the digits that are actually allowed in the cell, since they have to be allowed for both entries. Define $\tilde{\mathcal{F}}_a$ as the following subsheaf of $\mathcal{F}_a$: $$ \tilde{\mathcal{F}}_a(U) = \{ x \in \mathcal{F}_a(U): \pi_c(x) \in W(c) \ \ \forall c \in C_a \cap U \} $$ In other words, these are the allowed sequences for the entry that also respect the possible digits in the other direction. Now $\tilde{\mathcal{F}}_a, \tilde{\mathcal{F}}_{a'}$ agree on the intersection, and we have a globally defined sheaf $\mathcal{F}$.
Kakuro sheaf and puzzle solutions
The key fact now is that global sections $\mathcal{F}(X)$ are exactly the solution of the puzzle. Indeed, any solution is an element $S \in \Sigma(X)$ such that its restrictions to $\Sigma(X_a)$ lies in $\tilde{\mathcal{F}}_a \subset \mathcal{F}_a$ for all entries $a \in A$. In particular, a Kakuro puzzle is valid iff $|\mathcal{F}(X)|=1$ (unique solution), and the map $\mathcal{F} \to \Sigma_X$ yields the solution in terms of digits.
Question 1: is this construction actually well-defined?
Question 2: If one takes the free abelian group at each step of the construction, does the result on global sections & solutions still hold in some form? It would be nice, for example, if the global sections of the abelian version was spanned by the actual solutions. I think this can be reformultaed in terms of "free abelian functor" commuting with the "gluing of sheaves" operation.
Question 3: If we can use abelian groups, is the resulting sheaf constructible? I studied (sloppily) perverse sheaves a few years ago, but this shares some similarities with gluing solutions of differential equations to a (unique) global solution, and perverse sheaves pop up in the correspondence with $D$-modules. Maybe there is an analogous correspondence here? Maybe the symmetric group action can be exploited in the correspondence?
Question 4: Is there a nice classification of finite-dimensional constructible sheaves on such simple spaces? Can the easy geometry of the underlying space be exploited to get some information on the puzzle, analogously to the monodromy action for locally constant sheaves?
