There is an old puzzle, which I believe I learned from Nob Yoshigahara, that asks for all configurations of four (distinct) points in the plane such that the six pairwise distances assume only two distinct values. (In other words, there exist two distinct positive reals $a$ and $b$ such that the distance between any two of the four points is either $a$ or $b$.) Two configurations are considered equivalent if one can be obtained from the other by a dilation followed by a rigid motion. What makes this a good puzzle is that there are only finitely many solutions. MO readers may enjoy finding all solutions.
My question is, given $n$, $d$, and $k$, is there an efficient algorithm to determine whether there are only finitely many configurations of $n$ distinct points in $\mathbb{R}^d$ such that the $\binom{n}{2}$ distances between them assume only $k$ distinct values? Of course, I'm using the same notion of equivalence as stated above.
EDIT: Peter Winkler's book Mathematical Mind-Benders provides the following information about the origin of the aforementioned puzzle: ‘[It] appeared as Problem 3a (submitted by S. J. Einhown and I. J. Schoenberg) in the “Puzzle Section” of the Pi Mu Epsilon Journal in 1985. Later it showed up on page 1 of Nob Yoshigahara's Puzzles 101, where it was attributed to Dick Hess.’