Conceptually, I love this. Logic! Minimalism! Fantastic.
Practically, I'm a little confused. Take the second interview: if I'm reading it right, the square is saying that the circle is the murderer, and the circle is saying that the square is telling the truth. OK, so...if the circle is telling the truth, then the circle is the murderer. But if it's lying, then the square is also lying, so the square is the murderer. So...without an additional piece of information, like "at least one of them is telling the truth", or "the murderer is always lying", or something like that, how can you deduce anything at all?