4
$\begingroup$

I'm working with something that can modeled as the following type of (multi-)graph $G = (V,E)$, which I've been calling an "unlockable" graph. (There may be existing terminology for this.)

Let $G$ be a graph with the following additional structure. There is a set $K$ of keys, and edges may be "unlocked" or they may be "locked" by decorating them with the name of some $k \in K$. Multiple edges can be locked by the same $k$. Each vertex in the graph $v_i$ has a (possibly empty) ordered list $L_i$ of locations, which may be empty or contain a key. One of the vertices of the graph is marked as the start vertex.

The graph can be completely unlocked if every vertex can be visited from the start vertex. A locked edge can only be traversed if a vertex containing the key for that edge is first visited. Traversals are allowed to repeat edges and vertices.

Such a graph is valid if a) all keys are placed in exactly one location and b) the graph can be completely unlocked.

I'd like to uniformly randomly select a valid key placement on a fixed underlying graph. (That is, a map from $K$ into the locations $L = \cup_i L_i$ of the graph.)


The analogy (and essentially the context) is as follows: The graph represents a dungeon composed of rooms, and the edges are doors, which can be locked or unlocked by various keys. These keys are scattered around the dungeon in treasure chests. An adventurer enters the dungeon and explores it, and wins if they can enter every single room (to loot it, I suppose). How can the keys be distributed so that the adventurer always wins, and cannot have an unfair advantage by assuming that one valid configuration is more likely than others?


Here's a naive algorithm that produces a random valid key placement:

current_keys = {}
placed_keys = {}
current_rooms = {}
while not all rooms are in current_rooms:
    current_rooms = largest connected component of start_room via unlocked doors
    for key not in current_keys and key not in placed_keys:
        if key has door connected to room in current_rooms:
            add key to current_keys
    randomly select new_key in current_keys
    place new_key in random unused location in room in current_rooms
    remove new_key from current_keys
    add new_key to placed_keys
    unlock all doors that can be opened using new_key

However, this algorithm does not randomly select a valid key placement uniformly.

For instance, imagine a dungeon consisting of three rooms: a start room and two side rooms connected to it. The door to one side room needs key $a$ and the door to the other needs key $b$. Each side room has one chest, and the starting room has two. I'll draw this dungeon as [_|__|_], with the start room in the middle, the $a$ side room on the left, and the $b$ side room on the right.

There are six distinct valid configurations:

[_|ab|_], [_|ba|_], [b|a_|_], [b|_a|_], [_|b_|a], [_|_b|a]

However, the naive algorithm over-weights the first two choices, selecting them 1/4 of the time each and the remaining choices only 1/8 of the time. This is because earlier areas are unlocked for longer, so they have a higher chance to have a key placed in them.

Also notice that [_|ab|_] and [_|ba|_] are distinct configurations, since the elements of $L_i$ are distinguishable from each other. It is not the same as specifying that $v_i$ can hold at most $|L_i|$ keys.

I thought about something like a dynamic programming-type algorithm, but the issue is that a valid configuration can be produced from an invalid configuration. For example, if we always placed $a$ before $b$ in the above example, then the configurations [_|b_|a] and [_|_b|a] could never be reached because [_|__|a] is not a valid partial configuration.


It's pretty clear that there are roughly at most $|L|^{|K|}$-many key placements, although for a generic graph, a good portion of these will not be valid.

In my particular problem, I have about 40 rooms with about 100 treasure chests spread around among them and about 20 keys. Enumerating all possible valid locations and then uniformly choosing a random one seems like it would be quite slow, especially if I want to use this for a larger scenario, where I have about 50 rooms with 1000 chests and 40 keys.

This question is pretty specific and I couldn't find any information about this type of graph, but I also don't really know what to search for it as.

I did find some information about generating such graphs where you can also choose which doors are unlocked with which keys -- in the context of surprise, surprise, dungeon generation for a game -- but here that information is fixed in advance and only the keys can be freely placed.

(I'm also interested in a harder problem where some of the doors are one-way (so the graph is a digraph) and we don't want the adventurer to ever get stuck in a room with no way out, but I suspect the above problem is hard enough to start.)

$\endgroup$
  • 1
    $\begingroup$ I assume that, in your intended application, the graph is planar? That could make a big difference, since you're essentially dealing with cutsets. (If the set of edges locked by some key doesn't disconnect the graph, then the level could be completed without using that key.) $\endgroup$ – David Richerby Nov 12 '17 at 20:39
  • $\begingroup$ Yes, in the current application the graph is planar, but does have cycles. So there's definitely arrangements where a key turns out to be useless. In my actual full application, some of the edges are directional, where even if you have the key you can only traverse them in a single direction, so that makes things more complicated. $\endgroup$ – HPR Nov 12 '17 at 21:20
  • $\begingroup$ Are the decorations on the edges (indicating which keys are on which edges) are given, along with the graph, so we just want to sample the place of keys in locations? $\endgroup$ – D.W. Nov 13 '17 at 8:23
  • $\begingroup$ Yes, that's correct. Which keys open which doors are fixed and cannot be changed. $\endgroup$ – HPR Nov 13 '17 at 12:39
  • $\begingroup$ Are the number of locations per vertex fixed and given, too? $\endgroup$ – D.W. Nov 13 '17 at 16:24
1
$\begingroup$

The following decision variant of your problem is NP-hard in general:

Given a graph,determine whether the graph has any valid placement of keys to make it unlockable.

In particular, there's a straightforward reduction from 3SAT, shown below in the appendix.

As a consequence, in the general case your problem is NP-hard too: take the graph, try to sample a valid placement of keys, and if the procedure returns a valid placement, then you know the graph is unlockable; if it gives up, the graph is not unlockable. However, this might not be terribly relevant in practice.

It does suggest a possible approach to your problem. We could construct a formula $\psi$ where every satisfying assignment corresponds to a valid placement of keys that makes the graph unlockable, and then ask to randomly sample from the satisfying assignments of $\psi$. It should be straightforward to construct such a formula; then see Using SMT solvers to generate random solutions to given predicate for one method for doing the latter. This approach will be exponential-time in the worst case, but it's possible that if your problem has enough structure, maybe it will be effective in practice.


Appendix: The reduction

Suppose we have a 3CNF formula $\phi$ with $n$ variables $x_1,\dots,x_n$ and $m$ clauses. We'll have $2n$ keys (one for each $x_i$ and one for its negation, $\neg x_i$). The graph is a sequence of $n$ diamonds, one for each variable, followed by a sequence of $m$ vertices, one for each clause, like this:

Basic graph

I haven't shown the edge decorations or locations yet. Let's start with the $i$th diamond (corresponding to the $i$th variable, $x_i$):

The edge $A_i \to B_i$ is decorated with the key $x_i$, and the edge $A_i \to C_i$ is decorated with the key $\neg x_i$. There is one location associated with $A_i$; $B_i$ and $C_i$ have no locations. Notice how this forces any valid placement to put either $x_i$ or $\neg x_i$ into the location at $A_i$, and in particular, we can either place the key $x_i$ somewhere or place the key $\neg x_i$ somewhere.

Next, let's look at one of the pieces of the right half of the graph, corresponding to the $j$th clause.:

I've shown the decorations we'd get if the clause is $(x_3 \lor \neg x_5 \lor \neg x_7)$.

Finally, we add $n$ more isolated vertices $D_1,\dots,D_n$ (not shown above), each with a single location. The idea is that the keys that aren't placed into $A_1,\dots,A_n$ will be placed in $D_1,\dots,D_n$, so each key can be placed in exactly one location.

Note that $V_m$ will be reachable if and only if there exists an assignment that satisfies the formula $x_i$.

$\endgroup$
  • 1
    $\begingroup$ Ah, this is what I was expecting to have happen. I figured there was a way to encode some hard problem in this. One minor fix: the way the question is posed is that the original graph is assumed to be connected, and that once you can unlock everything, you can reach every room. So you can't have isolated vertices $D_i$, since you can't reach them from $A_1$. But that's easy to fix, since you just make $V_m$ have n locations, so the extra keys will go there. Is there a good way to go about finding the $\psi$ you mentioned? $\endgroup$ – HPR Nov 14 '17 at 0:51
  • $\begingroup$ @HPR, thanks for fixing up my reduction. Hmm. Now that you mention it, the only constructions I have for $\psi$ are ugly and involve many temporary variables. We add boolean variables $r_{i,v}$ (which if true indicates that after $i$ steps of the path, we are at vertex $v$) and $u_{i,k}$ (which if true indicates that key $k$ has been unlocked somewhere in the first $i$ steps of the path), with clauses to enforce the obvious relationships between them. The resulting $\psi$ will be large, so I don't know if you'll be able to sample satisfying assignments easily using SAT solvers. $\endgroup$ – D.W. Nov 14 '17 at 2:31
  • $\begingroup$ Hm. This seems so large as to be prohibitive for anything more than a basic example. Perhaps not surprising, but I don't think the $\psi$ for my small case will be solvable easily by a SAT solver, let alone the one for my bigger case. I haven't actually tried it yet, but since it essentially involves enumerating all possible walks through the graph, it seems too large to be effective in a reasonable amount of time. $\endgroup$ – HPR Nov 14 '17 at 16:57
  • $\begingroup$ This reduction implies that the OP's original algorithm actually won't always find a solution. But on the bright side, being able to tightly restrict the available locations seems crucial to the reduction (to enable "$\neg(x \land \neg x$)" to be expressed), so if locations are "plentiful", then probably the OP's algorithm (and other simple algorithms) will always work (in the sense of finding a solution, not a uniformly random solution). $\endgroup$ – j_random_hacker Mar 14 '18 at 14:07
0
$\begingroup$

One approach is to use rejection sampling. In other words:

  1. Randomly sample a placement of keys in locations (without regard to whether that placement allows the graph to be completely unlocked).

  2. Test whether the resulting graph can be completely unlocked. If not, repeat (go back to step 1, and keep repeating until you find one that can be unlocked).

This does have a uniform random distribution on the set of valid graphs. The running time depends on what fraction of random placements allow the graph to be completely unlocked; I don't know what that fraction is.

There may be better algorithms.

$\endgroup$
  • $\begingroup$ I had thought about this; perhaps I should have mentioned it in my post. I think the fraction of valid placements is just too small in most cases. For my particular case, I don't know the true fraction, though, so I can't say for sure. But I would guess that it is quite small. $\endgroup$ – HPR Nov 13 '17 at 15:56

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.