Books, Hallways and Social Butterflies

Imagine a crowded potluck party. Some people have met one another beforehand, others are complete strangers. You would like to know what’s the best layout for your party so that people can move around freely and engage with anyone. But people who don’t already know each other don’t really want to talk to one another and can’t swap places or get past one another. However, you also have “social butterflies” who are friends with anyone at the party and can swap places with people freely. How would you, as the host, position your friends in your apartment to make sure no one is awkwardly stuck and everyone gets to talk to whoever they want to, even if that requires your more popular friends to intervene? This question is somehow equivalent to understanding generalisations of the famous 15 puzzle. Together with Matt Kwan, we solved this problem! (Unbeknownst to us, this question had already been answered under a different name 30 years ago).