Best Answer plasmid, 10 July 2014 - 05:21 AM

Looks like you've mostly solved your own puzzle

And no one tried to argue that it's impossible because there are only 6*6*4*4 = 576 ways to orient the dice, while there are 6! = 720 ways to arrange the prisoners, so the dice can't encode all possible arrangements of prisoners.

Represent the orientation of the dice with four numbers as follows. The first number (from one to six) is the number facing the lion on the die that's on the side with the “D”, the second number (also from one to six) is the number facing the lion on the die that's on the side with the “E”. The third number (from one to four) is derived by considering the die on the side with the “D”, looking at the number facing the “DNE” and seeing where that is among the four numbers that do not face toward or away from the lion. For example, if face 2 were toward the lion and face 5 were away from the lion, then if face 4 is pointing toward the DME then 4 is the third number among {1, 3, 4, 6} that don't face toward or away from the lion, and represents a 3 as the third digit in the code. The fourth digit is obtained similarly by considering the die on the side with the “E”.

The first prisoner to get the dice will consider his cell number, call it A, and pass the dice to the next prisoner arranged with the code [A A 1 1]. The fact that the first two numbers are the same and the second two numbers are both 1 will let the prisoner who receives the dice know that he's the second prisoner to get them, and will tell him that the prisoner before him in the cycle is in cell A.

The second prisoner will consider his cell number to be B, and will pass the dice in the orientation [A A 1+int(B/3) 1+(Bmod3)]. The third prisoner to receive the dice will know that he's the third because the first two numbers are the same and the last two numbers are not both 1, and he will know the cell numbers of the two prisoners before him in the cycle.

The third prisoner will consider his cell number to be C. He will calculate X as the number that C would be if A and B were excluded – for example, if C=5 and A=2 and B=6, then C=5 would be the fourth number out of the numbers left if A and B are removed {1, 3, 4, 5}, so X would be 4. The third prisoner will pass the dice in the orientation [A B X X], which will let the fourth prisoner know that he's the fourth to get the dice because the first two numbers are different and the last two numbers are the same.

The fourth prisoner will similarly calculate Y based on his cell number using the same method that the third prisoner used to calculate X, and will pass the dice in the orientation [A B X Y]. The fact that the first and second numbers are different and the third and fourth numbers are different will let the next prisoner know that at least four other prisoners have seen the dice, and will tell him which cells each of the four prisoners preceding him are in, so knowing that in combination with knowing his own cell number will mean that the fifth prisoner will know everyone's cell number.

Since the fifth prisoner knows everyone's cell number, he can pass the dice on to the sixth player with the same [A B X Y] orientation that he would have used if he were the fourth prisoner. It doesn't really matter if the sixth prisoner knows that he's sixth and not fifth, as long as he gets enough information to know that he's somewhere after the fourth and can figure out everyone else's cell number.

The sixth prisoner then passes it back to the first prisoner, again using the orientation [A B X Y] that he would have used if he were the fourth prisoner.

Now the fifth, sixth, and first prisoners to get the dice know everyone's cell number, and they can each free themselves and the prisoner that is three steps ahead of them in the cycle that was agreed upon at the beginning.