2
$\begingroup$

I have 2D grid of adjastent square cells, which is square itself, with even side length (always exists some central cell)

Each cell represents some field of a labyrinth or a maze, which some "pawn" must "visit". Pawn starts in center and could make use only of horisontal and vertical moves. I count minimal possible amount of that moves. Obviously, for any such empty maze it would be some "spiral" trajectory and moves count would equan cell count minus one.

However i can draw "walls" between cells, prohibiting horizontal or vertical moves, if and only if each cell will still remain visitable. Sometimes that may force pawn to visit some cells twice, maximizing minimal path.

How to draw walls in such manner that moves count would be maximum? In other words, What is the ultimate wall solution, to make pawn's minimal path of maximal length?

$\endgroup$
  • 1
    $\begingroup$ To make things clear... the pawn has to visit every square at least once during its path? $\endgroup$ – user14972 Jun 27 '18 at 18:57
2
$\begingroup$

We might as well assume that we draw a maximal collection of walls: if there's another wall we can draw that will still leave the maze connected, then we should draw that wall, and that can only increase the length of the maximal path.

In that case, the maze contains no cycles: the only kind of path that starts at a location $X$ and comes back to $X$ is a path that retraces every step it takes.

In particular, a path that starts at the center, visits every location, and returns to the center must make every possible move twice. If we go from location $X$ to an adjacent location $Y$, then we enter a fragment of the maze which we can only leave by returning from $Y$ back to $X$.

If the grid is $n \times n$, there are $n^2$ cells, so $n^2-1$ pairs of adjacent cells without a wall between them, and so we need $2n^2-2$ moves to do this. This number of moves is always possible: just double every edge, then take an Eulerian tour.

If a path starts at the center and visits every location, but does not return to the center, then we can follow it up by a path from the final location to the center, and the result must have length at least $2n^2-2$. So the original path must have length at least $2n^2-2-d$, where $d$ is the distance from the center to its final location.

Moreover, we can always find a path that starts at the center, visits every location in $2n^2-2-d$ steps, and ends at a cell $d$ steps away from the center. Just take a path of length $d$ from the center to that cell, and double every edge not on the path. Then the resulting graph has an Eulerian path from the center to that cell of length $2n^2-2-d$.

There is always a cell that's at least $n-1$ steps away from the center: one of the corners. (The distance can only increase when we add walls.) So to make the minimal path as long as possible, make sure every cell is reachable in $n-1$ steps from the center; then there will be no path shorter than $2n^2-n-1$.

There are many ways to do this; here's one which is easy to generalize.

walls

$\endgroup$
  • $\begingroup$ but how to draw walls? is there some regular pattern that i can just repeat? or maybe some algorithm like in drawing hilbert curve? $\endgroup$ – xakepp35 Jun 28 '18 at 9:39
  • 1
    $\begingroup$ There are many ways, but I've added an example which is easy to generalize. $\endgroup$ – Misha Lavrov Jun 28 '18 at 19:25
  • $\begingroup$ Given side length n, How could we count number of possible ways of drawing walls, that satisfy this condition(max possible path)? $\endgroup$ – xakepp35 Jun 28 '18 at 19:40
  • $\begingroup$ It would be difficult. There are $2^{(n-1)^2}$ ways chosen as follows: for each non-center cell, leave open exactly one wall in the direction of the center (this can be done in one way for $2(n-1)$ cells, and two ways for $(n-1)^2$ cells.) There are also many other options that don't follow this pattern, which are harder to count. $\endgroup$ – Misha Lavrov Jun 28 '18 at 20:07
  • $\begingroup$ There are, however, at most $2^{2n(n+1)} = 2^{O(n^2)}$ mazes total, which gives us an upper bound. $\endgroup$ – Misha Lavrov Jun 28 '18 at 20:25

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.