How to generate an einstein puzzle?

Question

Mathematics

Many probably know in one form or another Einstein's riddle, about the street, on which there are houses of six different colors, where residents of six different nationalities live, drinking different drinks, etc. The question arose - how to generate such a task, in the variant when it is necessary to restore all the fields? That is, to make a set of hints sufficient to describe the entire state of the field, and close to the minimum. At least from what area of ​​mathematics to start smoking?

Answer 1

Combinatorics together with graph theory. And a bit of mathematical logic.

Answer 2

Mathematics is not needed here, programming is enough.
Look at the Sherlock toy: www.kaser.com/sherwin.html
There, the solution algorithm is completely open: there is a three-dimensional bit array "can feature B have value C in house A", and at each moment of the decision there is a hint that excludes one of the options. So you first need to generate any set of hints that leads to a solution using this algorithm ("if you reach a dead end, add another hint"), and then exclude from the resulting set those hints without which the problem can be solved (eliminate one at a time and try to solve ). Keep in mind that hints have different strengths, and in order not to get a huge set of "A is not B's neighbor", you need to strike a balance by adding (better, first,
It is better to generate a hundred or two sets in advance, and then apply them, mixing features and values ​​​​in random order.