The puzzle has a well know simpler version:
One god always tells the truth, the other always lies. Ask one question and determine the way to the castle.
There is a "classical" answer which I have known as long as I can remember:
Point to a path and ask one of the gods "Would the other god tell me that this is the way to the castle?". If he says "no" then it is the way to the castle. If he says "yes", then the other path is the way to the castle.
The question about the castle is arbitrary. Let's just replace it with a generic question "φ".
Notice that "If I asked the other god φ, would he say yes?" asked to either the truth teller or the liar always results in the answer that would be incorrect for the question "φ".
Can we adapt the two god solution to a three god solution? Not immediately. Specifically the two god solution is phrased in terms of asking about the other god, but now there's no single other god to ask about. (At this point we might wonder why the "classical" two god solution is phrased in terms of "the other god". Perhaps because it has been popularised by the film Labyrinth). Nonetheless, we notice that the following solution is equivalent in practice, and more elegant:
Point to a path, and ask one of the gods "Would you tell me that this is the way to the castle?". If he says "yes" then that is the way to the castle. If he says "no", the other path is the way to the castle.
Notice that "If I asked you φ, would you say yes?" asked to either the truth teller or the liar always results in the answer that would be correct for the question "φ".
That is, without reference to other gods we have transformed liars into truth tellers, whilst truth tellers remain truth tellers. We can't do anything about a randomer.
Before we continue with three gods, let's solve the problem with one liar and one truth teller who speak languages from L, possibly different.
Firstly note that another name for English is "Yesisyesnoisno", and that
and vice versa. Likewise,
and vice versa.
So adding extra languagues doesn't actually make the problem any harder! We can treat both non-English-speaking gods as "Daisyesjaisno" speakers (say), with the proviso that now we don't know if there are two, one or no liars among the pair. That's no problem, since we already know how to convert liars to truth tellers. So instead of asking
If I asked you φ would you say "yes"?
we ask
If I asked you φ would you say "da"?
If they reply "da" then φ is true. If they reply "ja" then φ is false.
With the above observation, the three non-English-speaking gods problem is equivalent to the three English-speaking gods problem, with two truth tellers, and one random.
With our first question we might like to try to find random, so we can eliminate him from our futher questioning. It's no use asking a god whether or not they themselves are random, because random could always reply "no", like the other two would – so pick two gods, point to the Second and ask the First "Is he random?". We'll either get a "yes" or a "no" in response, and there are four possible cases to consider:
Let's consider the other gods in these cases:
So whenever First says "yes", Third is not random. Whenever First says "no", Second is not random. Therefore with one question we have determined a truth teller. With a second question we can determine whether φ is true.
In The Hardest Logic Puzzle Ever there was a distinction between truth tellers and liars that we have made arbitrary. However to completely classify the three gods we would have to tell our two new "transformed truth tellers" apart. You should check that we can do this simply and with two further questions.
We have transformed the 2N+1 gods puzzle to
Amongst 2N+1 English speaking gods there are at least N+1 truth tellers, and the others are randomers. In 2N questions determine whether φ is true.
We can solve this by finding a truth teller in 2N-1 questions, which is a great puzzle in it's own right. Richard Smith calls it the "CPUs in space" puzzle.
The answer to the "CPUs in space" puzzle is currently left as an exercise!
Jon Pretty notes that you cannot hope to find a a truth teller in fewer than N questions, because the first N gods you speak to might all be randomers. However, is there a solution to the CPUs puzzle that requires fewer than 2N-1 questions? Can we exploit the omniscience of the gods to solve this special case of the CPUs puzzle in fewer than 2N questions?
Aaron Hauptmann has proposed a solution to the CPUs problem which takes at most 2N-1 - bits(2N-1) questions, where bits(k) is the number of 1 bits in the binary representation of k. After initial inspection it appears to be valid.
Basically, choose a maximal subset A of size a power of 2. After |A|-1 questions you either find a good CPU or discover you can discard A whilst maintaining the invariant that more than half the CPUs are good.