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
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.
No comments:
Post a Comment