title: How to unlock all the chests in the treasure trove?
body: <p>Heard the following problem in Google Code Jam. The competition has ended now, so it's okay to talk about it <a href="https://code.google.com/codejam/contest/2270488/dashboard#s=p3">https://code.google.com/codejam/contest/2270488/dashboard#s=p3</a> </p>
  
  <blockquote>
    <p>Following an old map, you have stumbled upon the Dread Pirate Larry's secret treasure trove!</p>
    
    <p>The treasure trove consists of N locked chests, each of which can only be opened by a key of a specific type. Furthermore, once a key is used to open a chest, it can never be used again. Inside every chest, you will of course find lots of treasure, and you might also find one or more keys that you can use to open other chests. A chest may contain multiple keys of the same type, and you may hold any number of keys.</p>
    
    <p>You already have at least one key and your map says what other keys can be found inside the various chests. With all this information, can you figure out how to unlock all the chests?</p>
    
    <p>If there are multiple ways of opening all the chests, choose the "lexicographically smallest" way.</p>
  </blockquote>
  
  <p>For the competition there were two datasets, a small dataset with troves of at most 20 chests, and a large dataset with troves as big as 200 chests.</p>
  
  <p><a href="https://github.com/matt-hickford/codejam/blob/master/2013/qualification/treasure/treasure.py">My backtracking branch-and-bound algorithm</a> was only fast enough to solve the small dataset. What's a faster algorithm?</p>