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?

  • $\begingroup$ I believe that what makes a good puzzle of this type is that is it not obvious how much information is in some clue(s). If it is obvious, you can just fill in the grid. $\endgroup$ Jun 2, 2015 at 2:40
  • 1
    $\begingroup$ Have a look at: pdfs.semanticscholar.org/e357/… $\endgroup$
    – Philip
    Mar 17, 2019 at 21:15

3 Answers 3


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.

  • $\begingroup$ If I clarify that clues means what you have said in your second sentence: each piece of information, I feel there should be a way to measure this, perhaps by weighting definites, negatives and relatives. I'll do some more research. $\endgroup$
    – Rory Alsop
    May 15, 2014 at 15:00
  • $\begingroup$ I don't think it can be possible for 'relative' clues because in my example above you need to already know where the Norweigan's house is to know how much you can exclude. Also you need different types of clues - if all the clues relate solely to the house color (e.g. A lives in X color house; Y color house has pet B) you will need more than if you mix types. $\endgroup$ May 15, 2014 at 15:39

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


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.