We discuss the Knights and Liars problem, which is the problem of maximizing the number of red vertices in a red-blue-coloring of the vertices on a square grid, such that for each red vertex, exactly half of its neighbors are red, and for each blue vertex, not exactly half of its neighbors are red. We discuss the generalization of the problem to arbitrary graphs and discuss three integer programming formulations, by which we give results for grid graphs, torus grid graphs, triangular grid graphs, and graphs corresponding to the transitive closure of the boolean lattice. We give a full combinatorial treatment for two-dimensional grid graphs whose shorter interval-size is less than seven. We further prove that the decision version of the generalized problem is NP-complete.