I am writing a text adventure where I want to track how many guardians you need to dispel to open everything up. (edited to add) That's easy to add with a static graph, but I wanted to see what happened if someone got rid of a few guardians.

I've had to use a lot of test cases to get what I want, and I'm worried about mistakes, or if there is an easier way.

The map is below. In the game, the player must dispel the 2-3 guardian as well as 3-6, to help a person at 3 escape. Guardians guard passages between x and x+3, as well as x and x+1 if x mod 3 != 0.

| | *
| | |

The player starts at 7, and they need to gain access to 1, 3, 5 and 9 in any order.

Is there a formula or method to figure things out, or do I need to use brute force? My current solution is:

  • if you haven't tackled any guardians, the answer is 5. Otherwise, start with a total of 0.
  • if 5 is not visited, add 1 to the total.
  • if 1 is not visitable, add 1 to the total.
    • Also, if 2 and 4 are not visitable, and 6 is, add another 1.
  • if 9 is not visitable, add 1 to the total.
    • Also, if 6 and 8 are not visible, and 2 is, add another 1. (these "add another one" cases are for if you go, say, 7-4-5-2. A 5-2 or 5-6 may do double duty in some cases.)
  • if 2 and 6 are not visitable, add another 1.

This seems to work in a lot of cases. However, I can't be sure I've got them all. The player also doesn't need to access both 2 and 6, or both 4 and 8 for that matter. You can see that by letting the player destroy the guardians 1-2 2-3 2-5 5-8 7-8 8-9 (in an I) or rotate that 90 degrees. So it seems there are special cases, and I'm wondering if there's a non-hairy way to tackle this.


I am not sure that I have understood what are you asking for. I can say the following about a minimal number of segments (we call them edges) needed to open everything up and their pattern. The required subgraph $G$ should contain distinguished vertices $1$, $3$, $5$, $7$, and $9$, which constitute an independent set (that is, no two of them are adjacent). So in order to make $G$ connected we have to choose for each of distinguished vertices at least one incident edge (and both edges incident to the vertex $3$ to help a person at $3$ escape). Thus we have already used six edges. But this is still not enough to make $G$ connected. Indeed, $G$ may not contain at most one of vertices $4$ and $8$ (and already contains all other vertices). Thus $G$ has at most eight vertices, so in need to have at least seven edges to be connected. An instance of seven edges, solving the problem, is

| | *
| | *
  • $\begingroup$ I wasn't perfectly clear. I should have added that I want the game to recalculate the number of guardians you need to dispel (e.g. segments/edges you need to add) so that 1/3/5/7/9 are all connected, each time you draw in an edge. So I could rephrase that. $\endgroup$ – aschultz Aug 8 '16 at 11:20

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.