<h1>It gets stuck</h1>

<h2>Stuck at the seat level</h2>

<blockquote>
  <p>I am not sure if this will always finish or if it can get stuck even if there is a valid assignment.</p>
</blockquote>

<p>It may get stuck. Assume <em>k</em> = 4 tables, <em>N</em> = 16 players, 4 clans, 4 people in each clan. Let <em>A1</em> thrugh <em>A4</em> be the players in clan <em>A</em> and similarly for the other clans. Then the following is an example of a hand-crafted situation which could potentially arise from your algorithm:</p>

<pre><code>Round 1:
 Table 1: A1, B1, C1, D1
 Table 2: A2, B2, C2, D2
 Table 3: A3, B3, C3, D3
 Table 4: A4, B4, C4, D4

Round 2:
 Table 1: A1, B2, C3, D4
 Table 2: A2, B3, C1 !!!
</code></pre>

<h2>Stuck at the round level?</h2>

<p>An interesting question that still remains is the following: if a valid assignment for all three rounds is possible, can you find valid assignments for two rounds that preclude all valid assignments for the third round? If this were the case, you could get stuck at the round level, so when doing some backtracking algorithm, you might have to sometimes undo complete rounds in order to obtain a valid solution. I have no example where this does happen, and no strong gut feeling either way.</p>

<h1>Better ways</h1>

<blockquote>
  <p>is there a better way to do it</p>
</blockquote>

<p>I guess that with enough effort, one could squeeze this into the framework of some standard graph algorithm. Most likely, that graph problem would be NP hard, so there won't be polynomial time algorithms available for that either.</p>

<p>Donald Knuth wrote a nice paper about <a href="http://arxiv.org/abs/cs/0011047" rel="nofollow">dancing links</a> and their application to solving the <a href="http://en.wikipedia.org/wiki/Exact_cover" rel="nofollow">exact cover problem</a>. It still uses back-tracking and exponential time in the worst case, but it keeps data structures small for those parts of the search tree where most work is done, thus speeding up the search. Maybe some of these ideas can be applied to your situation as well. Just guessing, though, don't have a particular implementation in mind yet.</p>

<p>Another idea: perhaps you can adopt the concept of <em>augmenting paths,</em> as it is used when computing matchings. The idea goes something like this: if there is no unseated person available, pick an arbitrary person from some other player. If that person is compatible with the current table, move it to that table. By doing so, that other table would be short one player, and you could try to fill that gap using some unseated player. If that doesn't work, you re-seat an existing player again. You probably shouldn't start moving players right away. Instead, you should first try to find a full augmenting path, starting at a vacant seat and ending at an unseated person. Only after you have verified that such a chain exists, you can start moving people according to it.</p>
Distributing players to tables
<p>Consider <code>N = 4k</code> players, <code>k</code> tables and a number of clans such that each member can belong to one clan. A clan can contain at most <code>k</code> players.</p>

<p>We want to organize 3 rounds of a game such that, for each table that seats exactly 4 players, no 2 players sitting there are part of the same clan, and, for the later rounds, no 2 players sitting there have sat at the same table before. All players play all rounds.</p>

<p>How can we do this efficiently if <code>N</code> can be about <code>~80</code> large?</p>

<p>I thought of this:</p>

<pre><code>for each table T:
  repeat until 4 players have been seated at T:
    pick a random player X that is not currently seated anywhere
    if X has not sat at the same table as anyone currently at T AND
       X is not from the same clan as anyone currently at T
       seat X at T
       break
</code></pre>

<p>I am not sure if this will always finish or if it can get stuck even if there is a valid assignment. Even if this works, is there a better way to do it?</p>