6
$\begingroup$

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$.

nested 90-degree bends used, each completely covering two sides of the remaining node grid

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

one path is the bottom and left side, another is the remaining right side and one connection along the top, and a third connecting the two nodes furthest from each other left

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.

$\endgroup$
10
  • $\begingroup$ Risking to sound like an idiot, what is a shortest path, and do paths need to touch all nodes (and why are there three paths in the 3x3 grid when there should only be two) $\endgroup$
    – Auribouros
    Jun 20 at 11:47
  • $\begingroup$ Isn't there one node not covered in your first example? $\endgroup$
    – hexomino
    Jun 20 at 11:47
  • $\begingroup$ @hexomino, you are right, I have corrected my example accordingly, thanks! $\endgroup$
    – JKHA
    Jun 20 at 11:58
  • $\begingroup$ @Auribouros, there are three shortest path because I was showing that for $n$ non diagonal shortest path, it is possible. The difficulties lie when you ask for $n-1$. Yes, path must touch all nodes, they must cover the nodes. $\endgroup$
    – JKHA
    Jun 20 at 12:00
  • $\begingroup$ Going back to my initial "What is a shortest path" question, on the first grid, you mention there are 3 shortest paths, which, by the definition of "shortest", doesn't make sense to me. I see a path of length 2, one of length 4, and one of length 6. The shortest path should be the one of length 2 solely, right? And if those are just the "walls" for the paths, it still doesn't fit, there is a length 6 path in the first grid amongst the length 5 ones. $\endgroup$
    – Auribouros
    Jun 20 at 12:08

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Very nice! I had been trying something similar, but got fixed on the idea that p had to fully lie on the boundary to reduce to the n-1 case. Then the any solution with minimal n must have path endpoints at all four corners (any corner that is not an endpoint must lie on a path that goes along the boundary). And that is where I got stuck. $\endgroup$ Jun 22 at 20:46
  • 1
    $\begingroup$ One minor correction/clarification: "this will not change the total number of paths". Actually, it may theoretically reduce the number of paths: If it first hits q at an end point, then extending p fully absorbs q, decrementing the number of paths. This would seem unlikely to occur in a minimal solution, though I can't immediately rule it out. Of course, this does not matter at all to the argument of the proof. $\endgroup$ Jun 22 at 20:58
  • $\begingroup$ @JaapScherphuis very astute, Fixed. One can probably rule it out in a minimal solution, But at a later iteration when we already have some temporally cut in two q's lying around I don't see how to rule it out. $\endgroup$
    – loopy walt
    Jun 22 at 21:13
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Did you just beat me by 30 seconds? $\endgroup$
    – loopy walt
    Jun 22 at 20:08
  • $\begingroup$ And our proofs are more or less identical! $\endgroup$
    – loopy walt
    Jun 22 at 20:14
  • $\begingroup$ @loopywalt: Indeed. Great minds think alike, I guess. :) $\endgroup$
    – tehtmi
    Jun 22 at 20:14
-1
$\begingroup$

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..

$\endgroup$
3
  • $\begingroup$ I don't think that is a complete proof. It basically shows that the greedy algorithm for choosing the paths does not work. But maybe some other strategy exists that works? $\endgroup$ Jun 20 at 13:20
  • $\begingroup$ You right, more in-depth proof incoming $\endgroup$
    – Auribouros
    Jun 20 at 13:41
  • 2
    $\begingroup$ Looking forward to it. I'm stuck so far. $\endgroup$ Jun 20 at 13:41
-1
$\begingroup$

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:

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

$\endgroup$
1
  • $\begingroup$ A U-shaped path is not a "shortest path". (Oh, okay... it's an answer to a modified problem.) $\endgroup$ Jun 23 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.