14
$\begingroup$

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?

| improve this question | | | | |
$\endgroup$
  • $\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$ – Ross Millikan Jun 2 '15 at 2:40
  • $\begingroup$ Have a look at: pdfs.semanticscholar.org/e357/… $\endgroup$ – Philip Mar 17 '19 at 21:15
11
$\begingroup$

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.

| improve this answer | | | | |
$\endgroup$
  • $\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 '14 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$ – DisgruntledGoat May 15 '14 at 15:39
2
$\begingroup$

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

| improve this answer | | | | |
$\endgroup$

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.