Consider nine vertices arranged in a square $3\times 3$ grid. Compute the number of directed graphs that can be drawn on the grid by connecting every vertex to its immediate horizontal and vertical neighbors, if every vertex must have both indegree and outdegree $\ge 1$ (at least one edge entering and at least one edge leaving). If feasible, extend this to general $n\times n$ grids.
I created this problem while idly musing in a linear algebra class recently. I note that the corners each have two edges, so one must be directed in and the other out (either clockwise or counterclockwise). But then I also noticed that the problem can be reduced slightly by reducing the vertex and pair of edges at each corner to a single edge from middle of side to middle of side, upon which a $45^{\circ}$ rotation changes the problem to a $2\times 2$ grid with a single vertex connected to all four outer vertices in the center. I don't know if this actually helps the solution behave any more nicely, but it's something I noticed that I think could possibly help, so I felt I should mention it.
I determined what I believe is an upper bound of $224$ possible arrangements because if the edges connected to the corner vertices all "flow" in the same direction, the four edges connected to the middle vertex can have any of $14$ possible arrangements ($2^4-2$ because they can't all point in or all out), and then we can multiply that $14$ by $16=2^4$ for the number of possible arrangements of the edges connected to the corners of the grid.
So my question is effectively "is there a better way of solving this question than laboriously drawing out all possible directed graphs and seeing whether they work?", not just because a non-brute force solution would be more interesting and almost certainly more enlightening than just brute-forcing it but also because such a technique is completely infeasible for the general question I pose at the end of the stated problem. Also, I'm sorry I don't have a drawing for this- I don't know how to do pictures in LaTeX. If anyone could create a helpful picture to accompany the problem, I'd be deeply grateful.
Edit: Here’s an image of one admissible configuration. I drew it at virtual-graph-paper.com, which makes it very easy to draw this sort of thing. It will be saved there for $90$ days, so you can go and edit it to show further configurations if you like.
Here’s a fun way to do this, though unfortunately it won’t be feasible to apply it to larger grids without a computer.
If we use your simplification, there are only $5$ vertices, and thus only $5$ constraints to be considered in applying inclusion–exclusion.
There are $8$ edges in the simplified graph, so there are $2^8=256$ configurations without constraints.
If the constraint on a vertex is violated, that vertex has either all ingoing or all outgoing edges. For a vertex with $k$ edges, that leaves $2\cdot2^{8-k}=2^{9-k}$ configurations. There are $4$ vertices with $3$ edges and one with $4$, so we have to subtract $4\cdot2^{9-3}+2^{9-4}=288$ configurations.
If the constraints on two vertices are violated, if those vertices are neighbours, one must have all incoming and the other all outgoing edges, whereas if they aren’t neighbours, they can independently have all incoming or all outgoing edges. There are $2$ pairs that aren’t neighbours, and they leave $2$ edges unspecified, so they each contribute $2\cdot2\cdot2^2=16$ configurations. There are $4$ pairs of neighbours that leave $3$ edges unspecified, which also contribute $2\cdot2^3=16$ configurations; and there are $4$ pairs of neighbours that leave $2$ edges unspecified, which contribute $2\cdot2^2=8$ configurations. So in total we have to add back in $2\cdot16+4\cdot16+4\cdot8=128$ configurations.
Now it gets easier, because sets of vertices that contain an odd cycle can’t all have their constraints violated. There are $6$ subsets of three vertices that don’t form a cycle; they all consist of neighbours. $4$ of them fix all but one edge, so they each contribute $2\cdot2=4$ configurations, and $2$ of them fix all edges, so they each contribute $2$ configurations. Thus, we have to subtract $4\cdot4+2\cdot2=20$.
There’s only one set of $4$ vertices that doesn’t contain an odd cycle. It fixes all edges and thus contributes only $2$ configurations; so we have to add $2$ back in.
The entire set of five vertices contains an odd cycle, so we’re done.
The total is
$$ 256-288+128-20+2=78\;. $$
This is considerably below your upper bound – which makes sense, since most of the configurations of the outer four edges constrain the inner edges.
Come to think of it, it’s actually not too difficult to count using the configurations of the outer edges, so let’s do that, too.
There are $2$ configurations of the outer edges that never change direction, $2\cdot\binom42=12$ configurations that change direction twice and $2$ configurations that change directions $4$ times.
As you wrote, the configurations that never change direction allow for $14$ configurations of the inner edges.
The configurations that change direction twice fix the two inner edges incident at the vertices with the changes in direction. Those inner edges satisfy the constraint at the central vertex, so the remaining $2$ edges can be freely chosen, which makes $2^2=4$ configurations of the inner edges.
Four changes in direction completely fix the inner edges, so that only leaves $1$ configuration.
The total is
$$ 2\cdot14+12\cdot4+2\cdot1=78\;, $$
in agreement with the inclusion–exclusion calculation.