On the BBC4 quiz show “Only Connect”, there’s a round where 16 have to be sorted into 4 connected groups, 4 in each group. Once the connections are figured out it can still be hard as many items double as red herrings for other groups. However, there is in each iteration only one possible way to solve the wall. Is there good summary of what combinations are valid given there must be one unique solution? Obviously if 2 items both belong to criteria A and B but not C or D, then the solution must put them in the same group otherwise they could be interchanged. Is there any simple summary to see what combinations of items that could fit into 2, 3 or 4 groups can mutually exist?
I reckon that if you draw a graph consisting of four vertices a, b, c, d, representing the categories, sixteen vertices representing the items, and edges connecting each item to every category that it could be in, then at least one of the vertices a, b, c, d must be of degree four only. Removing the edges incident to that vertex will reveal another category vertex of degree four, and so on, allowing you to resolve the solution.
If every category vertex has degree greater than four then there’s no unique solution.
Or rather “remove the item vertices connected to that category.”
I would be interested in seeing a clear statement of the problem before hazarding a guess as to what graph problem it corresponds to. For example, Vertex Cover.
Note that a lot of these types of problems are NP-Complete and so fast solutions are not likely. OTOH, 16 is a fairly low number that brute force isn’t too bad.
Sixteen items are listed. On inspection, you notice that the items fall into certain categories. For example, some of them may be famous military officers, while some of them may be U.S. state capitals.
Often, an item will fall into more than one category. For example, Montgomery is both a state capital and a famous military officer.
The object of the game is to identify the categories and place each item into one of them, so that there are four items in each category. There is only one valid solution. (Except when the quiz setters mess it up, which I think has happened at least once!)
As Mr Shine says, they throw in lots of red herrings, and occasionally even have categories that play no part in the solution.
Assuming it’s not geographically restricted, you can play along here, including the puzzles from the actual show. (Warning: plays music on opening.)