A Systematic Algebraic Method for the Hardest Logic Puzzle Ever and a Generalization

Knights and Knaves puzzles ask for a question whose answer reveals the identity of characters who either always tell the truth or always lie. I introduce a compact method based on addition modulo 2 over Z_2, in which every agent, statement and answer is represented by a single bit. A few composable rules reduce the search for a working question to solving a linear equation for the unknown statement, whose solution is then mechanically translated into natural language. I illustrate the method by deriving solutions to the Two Guards Two Doors Problem and to George Boolos's Hardest Logic Puzzle Ever, with Random defined as in Boolos's original formulation. The same questions and strategy also solve, without any change, a variant of the puzzle in which only two of the three gods are present. Finally, I generalize the construction to a team of n gods belonging to m families. The solution found for this variant, specialized to the classical version of the puzzle, gives a second, non-adaptive solution in which the three questions are all addressed to the same god, whatever his identity, and independent of the previous answers.