Correct solution: http://alonso-vidales.blogspot.com.es/2012/05/spotify-bilateral-projects-final-puzzle.html
The first time that you read this problem you think, hum, is really easy, I can't understand why is classified as the most complex problem. But the real problem is not solve the problem, the question is do it efficient.
The problem consist in a bipartitie graph:
The bipartitie graphs have some interesting features, the most important to solve the problem is:
In a bipartite graph the maximum cardinality of a matching and the minimum cardinality of a node cover are equal.
Then, we should to find the maximun cardinality and we will have min number of nodes, this reduce a lot the complexity of the problem, we can use the crazy Hopcroft-Karp algorithm:
Using this algorithm we will obtain the paths for the max cardinality, and at the ends of each path the possible nodes, then we can reduce a bit more the possibilities.
With the possible nodes, we should to iterate over all the permutations of this nodes with the max cardinality as number of nodes.
The solution is:
And I used this third part code for the Hopcroft-Karp algorithm: