My daughter Jenn bough a puzzle book, and showed me a cute puzzle. There are 13 words as follows: BUOY, CAVE, CELT, FLUB, FORK, HEMP, JUDY, JUNK, LIMN, QUIP, SWAG, VISA, WISH.
There are 24 different letters that appear in the 13 words. The question is: can one assign the 24 letters to 4 different cubes so that the four letters of each word appears on different cubes. (There is one letter from each word on each cube.) It might be fun for you to try it. I’ll give a small hint at the end of this post. The puzzle was created by Humphrey Dudley.
This problem is also a graph coloring problem. There are 24 vertices, one for each letter. Two vertices are adjacent if there is a word containing the two letters. The puzzle is equivalent to assigning one of four colors to each letter so that adjacent vertices have different colors.
It can also be expressed as an integer program with variables x(i, j) for i = 1 to 24 and j = 1 to 4. If anyone wants to write an Excel spreadsheet and solve it via integer programming, please let me know. I’d be happy to post the Excel spreadsheet if you send it to me, or link to it if you post it and send me the URL. My e-mail address is jorlin at mit dot edu.
Here is the small hint. five of the words contain a “U”. The way I solved the puzzle was to focus first on the cube containing the U. Once that cube is determined, the second cube is much easier. And once the second cube is determined, the last two cubes are very straightforward. Determining the last two cubes reduces to recognizing the two parts of a bipartite graph.
By the way, we didn’t time it, but I think Jenn solved it faster than I did, and she used a different approach.