Cover an n times n grid with non-diagonal non-intersecting n-1 shortest paths

Question

This puzzle was given to me by PhD student colleagues. Suppose that you have a $n\times n$ grid. Is it possible, for a given $n$ to cover all its $n^2$ nodes with $n-1$ non-diagonal and non-intersecting shortest paths? If it is not possible, can you prove it for all $n$?

With $n$ non-diagonal shortest path, it is possible for every $n$. Here is an example with $n=4$.

The following example aims to show you what is a diagonal shortest path which are not allowed:

Two problems with this latter example:

• There is a diagonal shortest path
• Three nodes are not covered

A "shortest path" is a shortest path between any two nodes of the grid. It is not necessarily of length 2 if you chose two far away nodes. The aim is try having $n-1$ of those paths covering the $n^2$ nodes. The length of each paths does not matter as long as it is shortest. The non-intersecting property means that no two paths shall share an edge nor a node.

Answer 1

Terminology: There are two general "orientations" a path can have:

1. bottom left to top right; let's call that "slashy"

2. top left to bottom right; let's call that "backslashy"

These are not mutually exclusive: We'll use the convention that purely horizontal or purely vertical paths belong to both classes.

We'll now prove the claim that given n>0 a covering of an n x n grid by n-1 shortest on-grid paths does not exist.

Otherwise there must be a smallest counter example X. Let n be its size.

We'll show that we can construct from this a counter example Y of size n-1 contradicting minimality of X.

Lemma: If there is a path p in X that contains two distinct points touching two distinct boundaries then Y as above exists.

Proof:

Wlog p is slashy. Extend p to the bottom left and top right corners (erasing the bits of other paths that are in the way). As this extension hugs the boundaries it will not break up any other path. The resulting configuration X' therefore still has at most n-1 paths. To obtain Y, simply remove (the extended) p and push the resulting two leftovers together.

To conclude the proof of the main claim we will show that a similar extension can always be made even if p only touches one boundary. (Such a p always exists.)

Still wlog p is slashy and starts at the left or bottom boundary. Let y,x be the coordinates where it ends. We now show that we can extend p (and keep doing so until we reach the top or right boundary). If either y+1,x or y,x+1, i.e. the points just above or to the right is part of a slashy path q in X we can extend p along q in the top right direction. If we keep going until the end of q this will not change the total number of paths (at least not upwards, it could in theory reduce it as @Jaap Scherphuis points out). Otherwise both y+1,x or y,x+1 are in backslashy paths. If either is an endpoint we can add it to p. This only leaves the case that y+1,x and y,x+1 are part of the same backslashy path q and connected at y+1,x+1. But then we can simply extend p to y+1,x+1 (which way does not matter). This will temporarily create an additional path because q is cut in two. But q will be rejoined at the final "push-the-two-leftovers-together" stage.

Answer 2

Impossible.

For any set of nodes that make up a shortest path from the bottom-left corner to the top-right corner (or similarly from the bottom-right to the top-left), if we remove these nodes, the remaining nodes can be slid together together to form a $n-1$ by $n-1$ grid. It may help to think of shifting the nodes below the removed path up and left by one unit.

In this process, any path that does not involve removed nodes is preserved. Any path that only involves removed nodes is removed.

A path the crosses from one side to the other might not remain a shortest path (and may not even remain connected). To make this precise, the transformed path after removal of a set of nodes will contain all the non-removed nodes that were part of the original path, and after transforming the grid, any newly adjacent pair of nodes that are both part of the path will have a new edge added.

One case where a crossing path remains a shortest path is when exactly two nodes are removed: a corner (meaning one connection at that node is vertical and one is horizontal) and one of its neighbors can be safely removed if the slope of the path is negative (meaning it's left endpoint is higher than its right endpoint). This is because shifting the cells up and left by one will put one of the corner's neighbors on top of the other one.

It is also possible for a path to intersect the removed nodes in the middle, but not cross from one side to the other. This case won't be of any concern.

Given a covering of the grid with shortest paths, we will remove a set of nodes that make up a shortest path from one corner to the opposite corner. This path might not be one of the paths in our covering, but we will choose it so that it completely contains at least one path from the covering and also so that all of paths of the covering that aren't completely removed remain shortest paths in the smaller grid.

Start with the node in the lower-left corner. If this is a corner of a path in the covering, then we will just remove the bottom row and left column. This will remove the path that contains this corner node entirely and clearly won't cause problems for other paths.

If it is not a corner, it is an endpoint and we will follow the path until its end. Then (if we are not in the upper-right corner yet), we must choose to step either up or right. If we can step onto a horizontal, vertical, or positively sloped path from the covering, we will do so and follow it to its end. Thus, this path will just be truncated (or maybe completely removed) by removal of the chosen path.

Otherwise, if we can step onto the endpoint of a path from the covering, we will do so and follow it as long as we can without stepping down or left. Thus, this path will also just be truncated; and since it is negatively sloped, after leaving it, we cannot meet if again by traveling right and up.

The last case is the node above and the node to the right are both part of the same negatively sloped path from the covering. In this case, we can step up by one and right by one (in either order) which will remove a corner and one adjacent node from a negatively sloped path which, as noted above, will preserve that path. Since this path is negatively sloped, we won't meet it again.

This process is repeated until reaching the top-right corner. Then the chosen path is removed. This reduces the grid to $n-1$ by $n-1$ and completely removes at least one path (the path that covered the original bottom-left node). The remaining grid is still covered by shortest paths.

Thus, if it was possible to cover an $n$ by $n$ grid with $n-1$ paths, we could repeat this removal process $n-1$ times to reduce it to a $1$ by $1$ grid covered by at most $0$ paths. This is clearly impossible, so it is impossible to cover an $n$ by $n$ grid with $n-1$ paths.

Answer 3

The minimum amount of paths you need to fill an $n*n$ grid is:

$n$

Proof:

Greedy version:
An $n*n$ grid contains a total of $n^2$ nodes, in the example shown above, 16. The maximum amount of nodes a path can pass depends on:
- The number of paths put down previously
- The shape of the paths (An L shape or a staircase occupy the most space, a U would break the rules and make it a path longer than it needs to be)
- The size of the grid The maximum number of nodes passed for any path $p_x$ in an $n*n$ size grid is: $N_x = 2(n-x-1)-1$ starting with $N_1$
A path can clear a full row, along with a full column, the however they will have a node in common. So that's $2n -1$ nodes cleared. The path after that will see its field reduced to an $(n-1) * (n-1)$ square, and will continue on. In the example given above, that's 7, then 5, then 3, then 1. Which shows we can only use a minimum of $n$ paths to clear all nodes.

Analysis of the square and paths:
Each path can only have two directions, up or down, and right or left. After choosing those directions, the path can at most pass $n$ nodes in both axis ($n$ nodes horizontally, and $n$ nodes vertically), but by removing a full row and a full column of nodes, there will inevitably be an intersection point, robbing us of one node pass.
We need to clear $n^2$ nodes in ($n-1$) steps, taking an example with $n=3$ that's 9 nodes in 2 steps. The only way to clear those 9 nodes would require us to clear 5 nodes (as we figured in the greedy proof, we cannot clear anymore than 5 nodes in one go) and 4 nodes with the next path. To do so, we need to have as much space possible after our first clear, which is sadly also equal to our greedy algorithm. And despite our best efforts, we will only be able to clear 3 nodes on the second go, making it impossible to reach the 9th node in only 2 steps.
Now for any $n$, the issue is going to be similar, for $n=4$, 16 can be deconstructed in chunks: $16 = 7 + 5 + 4$ (greedy)$, 6 + 6 + 4, 5 + 5 + 6$
Every deconstruction of $n^2$ has the square of a smaller $n$ inside it (5 + 5 + 6 doesn't, but we'll see that later), and those smaller squares do the same, they can be deconstructed until we reach the fatal square of side 1, the single node that needs to be cleared without any paths. For those deconstructions, it's impossible to clear all nodes of a square of side $n$ with $n-1$ paths.
For the other deconstructions, the problem comes in the form of a crossroads, we can use our smaller length paths to fill in the blanks, but as the area inevitably shrinks, so does the maximum length of a path when a square is present on the shape, and as soon as a square of size $n$ is formed in one of the resulting shape, we fall into the same issue as we did before, deconstructing the resulting shape, sooner or later, gives us a smaller square, and with it comes the impossible resulting 1 side square.

And if $n$ paths are needed, we can do simply make stripes, and that fulfills every requirement. That is, unless circular paths are allowed..

Answer 4

If we assume that the minimal length of a path is independent of the rest of the grid, then Auriboros' result is optimal.
However, if the minimal length of a path is defined with regards to the other endpoints, then achieving n-1 is easy:

It is straightforward to see that each path cannot get any shorter even if you allow paths to cross.