Randomizing a circular linked list with adjacency rules

Let's say you have a big round table of arbitrary size, and you want to seat all your guests at the table mostly randomly, but with some rules about adjacency.

Example: Alice, Bob, Charlie, Dan, Eve, Frank, Gerry, and Heidi are coming to dinner. Create a random seating arrangement such that Alice isn't next to Gerry and Charlie isn't next to Frank.

So far, because I'm lazy and it works, I've been doing this by shuffling the list and then just reshuffling if the result violates any of the adjacency restrictions. I've been lucky, though, that my "guest list" is large and my restrictions are few, so failure cases are rare.

I'm guessing the better solution involves:

• Using tail recursion so that I only back up as far as necessary to resolve conflicts instead of reshuffling the whole list and hoping for the best.
• Sorting the initial list by each entry's number of exclusions, so that "fussier" items are resolved first, while there are more options remaining in the tail.

While I'm working on it, though, I find myself wondering if there's a way to detect up front whether a certain list's adjacency exclusions are impossible to meet. Maybe by building a tree of "legal" options and seeing if its depth is < the length of the list?