But the constraints in an Einstein or Zebra puzzle have an additional quality of order!

like: "John lives in the house right of the blacksmith."

or

"The Blend smoker has a neighbour who keeps cats."

update

For instance, I can't encode this last one in a hyper-cube, if there are 2 neighbours!