Picture-Hanging Puzzles
Written by Mike James   
Tuesday, 20 March 2012

Here's a puzzle that is just asking to be turned into a popular browser-based game. Is it the next twist on Cut the Rope?

 

Computer scientists, mathematicians and programmers often share a love of puzzles and delight in inventing new ones. A recent research paper by a bunch of well known people including Erik and Martin Demaine and Ronald Rivest explores the not so well known Picture-Hanging Puzzle and a few of its variants. Given the current interest in games such as Cut the Rope, this could be source of more than one new computer game.

The basic puzzle is easy to state - all you have to do is hang a picture using n nails and wrap the string round the nails so that the picture falls when any k nails are removed. 

The original version of the puzzle was posed in 1997 by A Spivak and involved just two nails. Remove either nail and the picture falls. You can see the solution below as illustrated in the paper:

picturehangingtwonail

The idea is obvious to see - make loops around the nails  so that removing one of the nails unloops the string.

The most general version of the puzzle asks that the picture falls when particular subsets of nails are removed. The new research shows that this generalized puzzle always has a solution. The only problem is that the proof involves an exponentially increasing number of twists around the nails. However, if we restrict our attention to the k out of n version of the puzzle, then the twists only grow at a polynomial rate as the number of nails increases.

The theory is related to generalizations of the well-known Borromean rings which are linked together but fall apart when one ring is removed:

 

brings

The three ring arrangement above provides the solution to the two nail problem. Generalizations provide solutions to the k=1 n nail problem. You can see the three nail solution below

 

threenail

 

The research makes connections between the picture hanging puzzle and group theory and monotone Boolean functions - so there probably is a serious application in there somewhere. And as you have probably guessed, there is something about complexity theory in there as well. In particular, we have the result:

For a given picture hanging on n nails trying to decide if there are k nails that whose removal makes the picture fall is NP-Complete.

The paper is fun to read and there are ten picture-hanging puzzles for you to try with solutions. There are also some open theoretical questions if you really want to dig deeper.

So can you convert this fun mathematics into a playable game?

I can already hear the sound of falling pictures.

More Information

Picture-Hanging Puzzles

Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu arXiv:1203.3602v1

Related Articles

NP-Complete - Why So Hard?

No 16-Clue Sudoku!

Pancake flipping is hard - NP hard

Generalized Towers of Hanoi - Optimal Algorithm

 

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.

Banner


jQuery Adopts Semantic Versioning
30/10/2014

Semantic versioning is a great idea and the ever-logical jQuery has decided that from now on this is what it is going to do. However, at the next upgrade you might be wondering where your jQuery has g [ ... ]



Imitation Game Opens London Film Festival
12/10/2014

The film about Alan Turing, starring Benedict Cumberbatch as the mathematician who used his genius as a code-breaker during World War II, had a red carpet premiere in London this week.


More News

 

Last Updated ( Tuesday, 20 March 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.