How many clues are required to ensure Einstein's Puzzle is solvable?

Question

I used to play Einstein's puzzles a lot when I was younger, and very quickly learned to assess quite rapidly whether I thought a puzzle would be a quick solve or more time-consuming, but I never worked out the detail on how many clues are required.

Is there a mathematical description of the minimum number of clues required to guarantee a solve, beyond which all further clues are unneeded but make life easier?

Answer 1

I know this type of puzzle simply as a "Logic Puzzle" or sometimes "Logic Grid Puzzle" (see Wikipedia entry here).

It's impossible to come to a fixed number, because each clue may reveal a different amount of information. For example "The Englishman lives in the red house but doesn't own a dog" essentially has two clues.

Even if you break those down into separate pieces of information, there are different types of information:

• Straight truths, e.g. "The Englishman lives in the red house". This is more than one piece of information, since you also exclude multiple possibilities (i.e. No one else lives in the red house).
• Negatives, e.g. "The Swede doesn't live in the green house". Here you only gain one piece of information.
• Spatial or relative clues, e.g. "The Dane's house is somewhere to the right of the Norwegian's". These can get more complex depending on the specific puzzle (e.g. "Adam arrived at least 10 minutes later than Betty"). It's impossible to determine how much information you extract from a clue here.

However, I do believe there is one metric that is required to ensure a puzzle is solvable: all but one of each 'entity' must be mentioned in the puzzle. In other words, if you have 5 house colors then the clues must make reference to 4 of them (presuming all the colors are listed in the introduction or accompanying logic grid). If two colors are not mentioned, there is no way to determine what goes with each.

Answer 2

Say you have a $5 \times 5 \times 5$ puzzle, that is you have five things that each have three attributes out of a list of five. You are asked to identify the attributes of each thing. The first thing can have $5^3=125$ possibilities. The second can have $4^3=64$ and so on giving $(5!)^3=1728000$ lists, but we can permute the list in $5!=120$ ways, so there are $5!^2=14400$ solutions to such a puzzle. A clue like "the A (one attibute) is B (another) reduces the number of acceptable solutions by a factor $5$. You need enough clues to reduce $14400$ to $1$, but a second clue may not give as much of a reduction as if it were first

Answer 3

I tried looking at this problem by restricting the definition of what a 'rule' is. In my analysis, I consider the case where house order does not matter, and the only rules that are allowed are rules that can be expressed as 2-tuples. For example, rules like (Brit, Red), (Swede, Dogs), (Dane, Tea) or (Green, Coffee) are allowed, while compound rules involving relative positions are not allowed.

For a general puzzle size with $n$ people and $m$ attributes, call the minimum number of clues required to guarantee a unique solution $f(n,m)$. I show that $f(n,m) = nm - g(n,m)$, where $g(n,m)$ is the solution to the following extremal combinatorics problem:

What is the size $g(n,m)$ of the largest multiset of non-empty subsets of $[m] = \{1,\ldots,m\}$, say $\mathcal{F} = \{C_1,\ldots,C_k\}$ such that there exists a unique partition $\mathcal{P} = \{A_1,\ldots,A_n\}$ of $[k]$ with the property that $\sqcup_{j \in A_i} C_j = [m]$ is a partition of $[m]$ for all $i=1,\ldots,n$?

I was able to determine the exact value of $g(n,m)$ for very large $n$, and some relatively tight bounds for smaller $n$. If you're interested, here is the arXiv paper for additional details!