Colored letters, labeled dice: a logic puzzle

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.

Advertisements

3 Responses to “Colored letters, labeled dice: a logic puzzle”

  1. JN Says:

    Jim,

    My solution based on your MIP formulation suggestion:
    http://joao.natali.googlepages.com/wordcubes

    Regards,
    JN

  2. Kerstin-Alfons Says:

    I cannot believe this will work!

  3. Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more « UBUNTU DE CLAIR Says:

    […] In Colored letters, labeled dice: a logic puzzle Jim Orlin stated a logic puzzle: 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. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: