Soln was this.....

There were actually two solutions to this problem. I found it really interesting. I got the second solution (the recursive one).


Naturally, we'll process the words one at a time, independently. For a given word, create a vertex in a graph for each letter in the word. Then, for each cube, we create another vertex in the graph. Finally, we draw edges from each vertex corresponding to a cube to each vertex corresponding to a letter where that letter is on the cube. This gives us a bipartite graph where one part is the vertices corresponding to the letters in the word, and the other half is the vertices corresponding to the cubes. Then just run bipartite matching, and if the size of the matching is equal to the length of the word, the word can be formed. That's one way to solve the problem anyway...

Most coders, however, opted for the simpler solution.In this solution, a brute force recursive function is written. It takes a word, a position in the word, and an array of booleans stating which cubes have already been used. We need to find a cube that contains the letter at the given position in the word, so we just check every cube:

boolean recurse(word, position, used)
if(position == word.length) return true
for i = 0 to num_cubes
if(!used[i] && cube[i].containsLetter(word[position])
used[i] = true
if(recurse(word,position+1,used)return true
used[i] = false
return false