Tricky Graph Theory Puzzle

Question

I ran into an intriguing puzzle on Reddit that I thought could use some attention.

You start with a 3x3 grid labeled with numbers 1-9 like this:

$$ 1 \text{ }\text{ }\text{ }2\text{ }\text{ }\text{ }4 \\ 5 \text{ }\text{ }\text{ }6\text{ }\text{ }\text{ }8 \\ 9 \text{ }\text{ }\text{ }3\text{ }\text{ }\text{ }7$$

To complete the puzzle, you must connect directed edges between the numbers so that:

1. The numbers connect in order from 1-9. There can be intermittent numbers when connecting them. For example, some puzzle may have the solution: 1, 3, 2, 9, 4, 3, 9, 4, 8, 5, 7, 8, 6, 7, 8, 2, 9.
2. The edges cannot overlap each other.
3. The vertices (the numbers) can have multiple edges connecting to it.
4. You cannot go back over edges (no overlaps).

Here's a picture of a completed puzzle:

I have a couple of question relating to this problem:

If there are impossible puzzles, then what criteria determines if a puzzle is unsolvable? If I were to make it 4x4 or 5x5 or NxN, would the criteria extend to those? What proportion of puzzles for an NxN puzzle are solvable.

Here's the link to the Reddit post: https://www.reddit.com/r/math/comments/8b032u/need_help_for_an_eulerian_path_game_i_made/

Answer 1

Condition 4: Not being allowed to go back over edges definitely changes the complexion of the problem. In fact, for ALMOST ALL numberings of an $n \times n$ grid as $n$ gets large, such a completion of the puzzle is impossible.

Why? The resulting digraph on the $n \times n = n^2$ vertices (vertices here taken as points on the grid) would be planar due to Condition 2. This would imply for some subset $S$ of $\frac{n^2}{2}$ vertices of the digraph, then for some $R$ no more than $4n$, there are exactly $R$ edges leaving $S$. (Theorem of Lipton-Tarjan I believe). However, [one can check that] for $n$ sufficiently large, a random bijective numbering $\cal{N}$ of the $n \times n$ vertices of the grid (where the numbers used are $1,2,3,\ldots, n^2\}$), would be such that there are many more than only $4n$ integers $i$ that satisfy the following: $i$ is in $S$ but $i+1$ is outside of $S$. However, one can check that if $\cal{N}$ is a numbering such that there are $R'> R$ integers $i$ such that $i$ is in $S$ and $i+1$ is not, then solving the puzzle with the numbering as $\cal{N}$ is impossible. Indeed, such a path would have to leave $S$ at least $R' > R$ times which means that an edge leaving $S$ would be repeated.

Answer 2

Here's a possible counterexample: Consider the board $$\begin{array}{ccc} 3& 5& 7\\ 1& 9& 2\\ 4& 6& 8 \end{array}$$

Let the first row be set $A$, the second row be set $B$, and final row be set $C$.

First, notice that there can be at most $7$ edges crossing between $A$ and not-$A$ (you can check the possible cases for yourself), and similarly for $C$. So if you take a path from $1$ to $2$ that enters $A$, you use up $2$ of those crossings.

Since there has to be at least $6$ crossings going into $A$ that deal with hitting $3$ $5$ and $7$ (you have to go into $A$ before each number, and out of $A$ after each number), if you went into $A$ between $1$ and $2$, you wouldn't have enough edges to accomplish this. Thus, you cannot go into $A$ between $1$ and $2$. Same for $C$.

Thus, you have to start off your walk as $1\to9\to2$. But by doing this, you cut off the possibility of two of these edges between $A$ and not-$A$, leaving only $5$ possible edges, which isn't enough to hit everything in $A$.

Disclaimer: This answer was adapted from the linked reddit thread, and is not my own work.

Answer 3

ETA: I just reread condition 4, cannot overlap edges. Without condition 4 this would be easy.

If I understand correctly, for such a path to exist, it suffices that edges are put in so that the resulting digraph is strongly connected w no crossing edges.

But this is always possible. Suppose that you can put do such a thing w an $(n-1) \times (n-1)$ grid. Let us now add the $n$-th row $(1,n), \ldots, (n,n)$ and $n$-th column $(n,n-1), \ldots, (n,1)$. Put an arc directed from $(i,n)$ and directed to $(i+1,n)$ for each $i$, and then put an arc directed from $(n,i)$ and directed into $(n,i-1)$ for each such $i$. Then put an arc directed from $(1,n)$ and directed into $(1,n-1)$, and then from $(1,n-1)$ to $(1,n)$. Then the resulting graph on the $n \times n$ grid is strongly connected and has no connecting edges.

Answer 4

I am assuming that the connecting edges allowed can be chosen to run in one direction along the following edges:

except that only one of the crossing pairs of red lines may be used.

In this case it is easy to see that there can be at most five edges crossing from one layer to the next.

Now consider the following numbers placed in the grid:

It's clear that we will have used 5 connections into the bottom line by the time the trail reaches $6$. There will be no unused connections to get off the bottom layer to continue the path.

If you look at the solved puzzle in the answer, you can see something similar going on in the bottom layer of that puzzle. It only succeeds because there are no more numbers to get after $9$, but there is no way off that layer.

---

Edit to add: If a knight's move arrow is allowed, this could in principle give us one or two extra ways on and off the top and bottom layers. However this would come at the cost of breaking the links along the middle row shown here which would obviously mean an impossible extra requirement of links to the edge layers to navigate between those locations.