Suppose it got even worse: not only do we not have exit signs, we don't even know quite where the exits are - sort of like platform 9 3/4 at King's Cross. However mercifully (or sadistically, depending on your point of view), someone supplied us with distances between pairs of exits. Formally, we are given numbers x1, x2, ...x(N * (N-1)/2) and must determine the exits P1, P2, .... PN that yield these inter-exit distances.
Reconstructing the locations of the exits is called The Turnpike Problem. A Google search yields lots of information on this topic: in fact the first link is:
Oh well, never mind....
At any rate, this problem is surprisingly nasty. It occupies the limbo zone between NP-Complete and P, in the company of Graph Isomorphism and Factoring (they used to have a bridge foursome before Primes departed for P-land). It can be reduced to factoring an appropriately chosen polynomial, and so proving it NP-hard would be extremely interesting.
Turnpike reconstruction also comes up in X-ray crystallography and DNA reconstruction. Skiena, Smith and Lemke discuss this problem in some detail and present a backtracking method for solving it.
A Variant: I just saw this on comp.theory:
Suppose that instead of providing the difference between pairs of exits, we were given the sums. Does the problem change significantly ?