7
$\begingroup$

This video shows a grid maze with a type of tile that I'd call turnstiles.

The mechanics of those tiles are described below.

  • A turnstile tile has two bars on adjacent sides of the tile.
  • You cannot step into a turnstile tile if it would mean crossing a bar.
  • You can exit a turnstile tile in any direction.
  • If you exit the tile in a direction where there was one of the bars, then the pair of bars rotate by a 1/4 turn such that there's no more bar in the direction you exited the tile from (see video at 7:02).

Here's an example before and after exiting a turnstile tile:

        On a turnstile tile         Exited the turnstile tile to the south

Turns out, finding the shortest path from A to B in a maze containing this kind of tile is fairly easy. Long story short: even with turnstiles, the shortest path don't involve revisiting a node, therefore the usual algorithms work.

However, if we introduce a single waypoint, like fetching a key before going to the door, then we can no longer ignore the state in which we left the turnstiles. We might indeed revisit some tiles. Although taking the shortest path from A to K and then from K to B would produce a valid A-K-B walk, we can easily construct examples where this wouldn't produce the shortest walk overall, like this one:

        Example of suboptimal iterative solution

I couldn't figure out a way to turn this problem into a regular shortest path without blowing up the graph size exponentially with the number of turnstiles.

So, if the problem of finding the shortest walk with a single waypoint in a grid maze with turnstiles is NP-hard, any idea of proof?

If it's not NP-hard, how do we find a solution efficiently?

$\endgroup$
6
  • 1
    $\begingroup$ Assuming edges are all weight 1 then you could do standard BFS. You would need to keep track of a few things at each node though: 1) which direction are my turnstiles? and 2) does this path contain the waypoint? You'd be doing a BFS over the game state rather than the game board (e.g. the turnstile could be pointed 2 different directions for 2 different game states). $\endgroup$
    – ryan
    Jun 4, 2021 at 4:59
  • 3
    $\begingroup$ @ryan It's indeed the trivial approach I briefly mentioned. It would take an exponential amount of time and memory w.r.t the number of turnstiles. If this is required, do we have an NP-completeness proof? $\endgroup$
    – Celelibi
    Jun 4, 2021 at 9:18
  • 1
    $\begingroup$ It's not the same problem, but you might enjoy scottaaronson.com/blog/?p=5402 $\endgroup$
    – D.W.
    Jun 9, 2021 at 7:19
  • $\begingroup$ You may be able to reduce Hamiltonian Path to this problem by using the waypoints as vertices. Still unclear how to enforce that every waypoint is only visited once though. $\endgroup$
    – ryan
    Jun 10, 2021 at 4:28
  • $\begingroup$ These last days I've been thinking exactly on that. The Hamiltonian Path problem and its relation to SAT and TSP make it a good inspiration, if not a candidate for reduction. But I keep getting stuck on approaches that don't require a short path and turnstiles and waypoints. And removing any of those definitely simplify the problem. $\endgroup$
    – Celelibi
    Jun 11, 2021 at 0:16

3 Answers 3

1
$\begingroup$

I guess this is another non-answer.


$k$ waypoints $\in \mathrm{NP\ hard}$

The generalization of this problem ($k$ waypoints) is NP-hard even without turnstiles.

The reduction can be seen in Amiri et al. [1] from subset traveling salesman problem (TSP):

In the subset TSP, the task is to find a shortest closed walk that visits a given subset of vertices [38]. As optimal routes for WRP [Waypoint Routing Problem] and subset TSP traverse every edge at most twice, optimal solutions for both are identical when $\forall e \in E : c(e) \geq 2$.

Note that this also holds for planar graphs such as ours.

$1$ waypoint and $0$ turnstiles $\in \mathrm{P}$

That being said, when $k = 1$ and there are no turnstiles, we can solve this in polynomial time via a reduction to minimum cost integer flow (Amiri et al. [2]).

Indeed, the common endpoint $w$ can be leveraged to employ a reduction to an integer flow formulation: introduce a super-source $S^+$ and a super-destination $T^+$, connect $S^+$ to $s$ and $t$, and $T^+$ to $w$ with two links, all of unit capacity...

Next, solve the minimum cost integer flow problem from $S^+$ to $T^+$ with a demand of $2$. By performing flow decomposition and removing $S^+$, $T^+$, we obtain an $s - w$ and a $w - t$ flow, whose combined length is minimum.


$1$ waypoint and $k$ turnstiles and $c(e) = 1$ $\in \mathrm{NP\ hard}$, maybe?

If we restrict each edge to having capacity $1$, meaning it can only be included once in the shortest path, then we can make a reduction from the NP-complete $2$-link-disjoint paths problem. See section 2.3 of Amiri et al. [2] for the full proof. The idea is that with $c(e) = 1$ we can make our graph directed by using turnstiles to establish the direction of each edge.

However, this is only true for non-planar graphs. If we restrict it to planar graphs, the question appears to be open [3]. That being said, it is known to be in P under certain constraints [4], but still unclear for the general case.

$1$ waypoint and $k$ turnstiles and $c(e) = 2$ $\in$ ???

I'm not quite sure where your problem lies, but the allowance of turnstiles imposes a certain directionality on the graph even in the presence of $c(e) = 2$ which would incline me to believe this is NP-hard. Though, the results on the edge-disjoint path problem with congestion make me think there may be a poly time solution for $1$ waypoint.


$^1$ https://arxiv.org/abs/1708.09827

$^2$ https://arxiv.org/abs/1705.00055

$^3$ https://www.sciencedirect.com/science/article/pii/0304397580900092

$^4$ https://dl.acm.org/doi/10.1145/1132516.1132621

$\endgroup$
1
  • $\begingroup$ Interesting ideas, using flow algs. However, using a min-cost flow for 1 waypoint & 0 turnstiles (1W0T) seems overkill and the assumption $c(e)=1$ miss solutions that exist. For 1W0T we could copy the graph, connect them with the waypoint, put the goal on the replica and use a shortest-path. Easily generalize to k ordered waypoints. Actually, if k is constant, the unordered kW0T problem is still in P, we only need $2^k$ replicas. But of course, number of turnstiles is not constant, but rather a constant fraction of the total number of nodes. $\endgroup$
    – Celelibi
    Jun 11, 2021 at 14:55
3
$\begingroup$

This is not an answer, but also too many words for a comment and I didn't want to post a handful of comments.

I am not sure if this is NP-hard or not, but I have some ideas for a proof.


Proving NP-hard

I would take an approach similar to the NP-hardness proof for Super Mario Bros. Please watch this lecture: https://youtu.be/7d73E1DiH0w?t=2851

First you would need to change your question to "Has Path" rather than "Shortest Path". That is, does there exist a path from start to finish at all? For example, the answer is clearly no for the following (where green is start and red is finish):

turn1

We can then try to reduce a given 3SAT instance to this problem. My idea is not complete, but the idea is to use turnstiles as boolean "switches" which will determine a literal true or false.

For example, let's say (A) means a literal is false and (B) means a literal is true:

turns2

We can construct variables in such a way that the given path from source to end only allows one of the literals to be true. For example, the following would be such a variable:

turns3

If the top path is taken then $x$ is true, if the bottom is taken then the $x$ is false. Notice that if the path were attempted $A \rightarrow \neg X \rightarrow X$ that $X$ would be blocked and could not be flipped unless we go back through $\neg X$ which would flip $\neg X$ back to false. So this is a valid gadget that says "$X$ can only be true or false and the path from $A$ to $B$ will determine that value."

Next we need to construct a clause gadget. My idea for this would be to essentially have a similar setup to the example above where every instance of $X$ can be "set" to true at the same time by flipping its turnstile OR every instance of $\neg X$ can be "set" to true at the same time by flipping its turnstile but NOT both.

We need to construct this clause gadget in such a way that the literal and its negation cannot be both true at the same time. My idea was the following.

Let's say we have a SAT formula: $(x \lor \ldots) \land (\neg x \lor \ldots)$. We could construct a clause like:

turns4

If we had $x$ in multiple clauses like: $(x \lor \ldots) \land (\neg x \lor \ldots) \land (x \lor \ldots)$. We could have the following:

turns5

The important thing to note here is that you can't flip the $x$ turnstiles while also flipping the $\neg x$ turnstiles.

Then if we have multiple variables like: $(x \lor y \ldots) \land (\neg x \lor y \ldots) \land (x \lor \neg y \ldots)$. We would first route the path through $x$ then through $y$:

turns6

Again note that if we tried to choose $x$, the $x$ and $\neg x$ paths reconnect when routing to $y$. However, going "back" one path you would still not be able to "set" the other turnstiles because they are blocking a backward entrance due to their positioning, so the only route forward after $x$ is determine is to continue on to $y$ if you want to make it from start to finish.

For example, a valid solution to our 3SAT formula would be $x$ is true and $y$ is true. This would correspond to the following path from start ($x$) to finish (red). The path is shown in green:

turns7


The last thing we would need to do is verify that all clauses have at least one turnstile "switched" on. You can see in my example we could also get a path from start to finish with $x$ is false and $y$ is false even though this does not satisfy the 3SAT formula.

In the Super Mario example, the clauses are verified by "unlocking" a super star which allows Mario to survive a flame walk to the end. We don't exactly have this luxury in our game. By flipping our turnstiles we can't "unlock" anything special, like a path to the end. You could attempt to accomplish this with waypoints, but the waypoints don't actually add much because a path could go to the waypoint, then go exactly back to start and continue on as normal and it has effectively "visited" the waypoint without having to change its solve path.

One idea I had for "unlocking" something by completing a clause was the following:

turns8

If $x$, $y$ or $z$ are "set" then they can (exactly one at a time) go into the bottom chamber and flip the turnstile blocking upward entry from A. The idea would be that if you put a waypoint below A for each clause and you hook up the end of the variable chain to the right most A then you hook up B to the A of the clause to the left and chain them together like that. Then the B of the leftmost clause would be the end. The issue is what I just mentioned, we could just go to the way points then go all the way back to the start, then just set a literal in the first clause an exit.

So these would be my main ideas for constructing a reduction, however its clearly incomplete. If we added in "one-way" blocks or waypoints that only allowed the path to go in one direction but not back then I think this may work because you could trap a regular waypoint behind a one-way block.


The other big issue I did not mention but you would realize if you watched the Super Mario reduction is that the graph I have been showing is non-planar whereas the game is played on a planar graph. We would also need someway to establish crossovers which I think is nontrivial. One idea would be to do something like this:

turns9

This is clearly an issue however because if the green path was the "exit" of setting $x$ and the red path was the "entry" of setting $\neg x$ in a clause then you could exit setting $x$ and turn right to effectively also set $\neg x$. This is not allowed.

So you would need to resolve these crossovers as well.

Hopefully someone can take some of these ideas and run with them. It has the vibes of an NP-hard problem since you can essentially encode the turnstiles as bits and almost encode a 3SAT equation into them, but I'm not convinced yet.

$\endgroup$
4
  • 2
    $\begingroup$ This is a very interesting set of ideas. However I already know that a simple Dijkstra can find a path if it exists because shortest path don't have cycles (I'll edit my question on that). Which means that your Clause device cannot work and that we cannot implement a crossover. However, maybe by asking for a path length < $L$ we can force it to solve a 3SAT. $\endgroup$
    – Celelibi
    Jun 9, 2021 at 13:25
  • $\begingroup$ Yeah, if you added an additional door or something to resolve crossovers and clause verification you could probably get it to work, but yeah it won't work as it stands due to the aforementioned issues. $\endgroup$
    – ryan
    Jun 9, 2021 at 14:14
  • $\begingroup$ Note that I am not actively trying to make it NP-Hard. I'm genuinely wondering where this problem falls. I might learn something whether it is NP-Hard or not. $\endgroup$
    – Celelibi
    Jun 10, 2021 at 20:13
  • $\begingroup$ Noted. I'm not sure where it lies either. I can't think of a polynomial time algorithm to solve it and I also can't think of a proper reduction from a known NP-hard problem. It's an interesting question. $\endgroup$
    – ryan
    Jun 10, 2021 at 20:16
0
$\begingroup$

To decide if there is a path in $O(N)$ for a $N$ cells maze , you can simply run a BFS from start (As ryan already said, here, one should not talk of Dijkstra meaning priority queue...). So if you can reach both, the waypoint and the exit, it exists a solution.

Proof

You already proved that on a simple path, there is no need to consider the re-orientation of turnstiles. Indeed, you already reached this cell.

Another point is that you can always go back your path as turnstiles always get open to the leaving direction. So any cell reachable from start is reachable from any other reached cell, and in particular, the waypoint.

This of course does not guarantee you find the shortest path, your exemple shows it perfectly. But gives you an upper bound.

$\endgroup$
1
  • $\begingroup$ Yep, that's the logical consequence. And that's one of the reasons why we need to have the 3 requirement: looking for a short path, with an unbounded number of turnstiles, and a waypoint. Relax/remove any of them and you have a polynomial solution. $\endgroup$
    – Celelibi
    Jun 11, 2021 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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