Suppose you have $n$ people, numbered $0$ to $n-1$. We might as well suppose person $0$ stays put, and the others move around. So a "configuration" corresponds to a permutation of $1$ to $n-1$. Let $a_{i,j,c} = 1$ if $i$ and $j$ are seated next to each other in configuration $c$, $0$ if not. You can think of your problem as an integer linear programming problem:
$$\eqalign{\text{minimize } & \sum_c x_c\cr
\text{subject to } & \sum_c a_{i,j,c} x_c \ge 1 \ \text{for all } 0 \le i
The trouble is that there are a huge number of configurations ($9! = 362880$ in your example).
I tried a different approach: tabu search. In the cases I've tried it didn't take long to come up with an optimal solution. Here's my Maple program:
n:= 10; # number of guests
m:= ceil((n-1)/2); # minimal number of rounds required
scorer:= proc(L)
# count number of introductions for an m-tuple of configurations
nops(map(op,{seq([seq({L[i,j],L[i,j+1]},j=1..n-2),
{0,L[i,1]},{0,L[i,n-1]}],i=1..m)}))
end proc;
move:= proc(i,j,k,L)
# switch j'th and k'th positions in configuration i of m-tuple L
local M;
M:= L;
M[i,j]:= L[i,k]; M[i,k]:= L[i,j];
M
end proc;
target:= n*(n-1)/2; # necessary number of introductions
current:= [[$1..(n-1)],seq(combinat[randperm](n-1),i=2..m)];
tabu:= [seq([2,i],i=1..7)]; # these items temporarily can't be switched
currentscore:= scorer(current);
bestyet:= current; bestscore:= scorer(bestyet);
for iter from 1 to 1000 while bestscore < target do
bestnewscore:= 0;
for i from 2 to m do
for j from 1 to n-2 do
if member([i,j],tabu) then next fi;
for k from j+1 to n-1 do
if member([i,k],tabu) then next fi;
newtry:= move(i,j,k,current);
newscore:= scorer(newtry);
if newscore > bestnewscore then
bestnew:= newtry; bestnewscore:= newscore;
ij:= [i,j]; ik:= [i,k];
fi
od od od:
if bestnewscore > bestscore then
bestyet:= bestnew; bestscore:= bestnewscore;
printf("Best yet at iteration %d: %d\n",iter, bestscore);
fi;
current:= bestnew;
tabu:= [op(tabu[3..7]),ij,ik];
if iter mod 20 = 0 then
printf("iteration %d, score %d\n",iter, bestnewscore)
fi;
od:
if bestnewscore = target then printf("Optimal configuration ")
else printf("Best configuration so far ")
fi;
printf("with score %d out of %d:\n",bestscore,target);
print(bestyet);
For example, with $n=15$ it took 312 iterations to come up with an optimal solution:
[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],
[5, 10, 3, 11, 13, 7, 9, 6, 14, 4, 12, 1, 8, 2],
[11, 7, 10, 1, 5, 13, 2, 4, 8, 14, 9, 12, 3, 6],
[10, 14, 3, 7, 4, 11, 2, 6, 8, 12, 5, 9, 1, 13],
[3, 5, 7, 2, 14, 12, 6, 10, 8, 13, 4, 1, 11, 9],
[8, 11, 14, 5, 2, 12, 10, 13, 3, 9, 4, 6, 1, 7],
[4, 10, 2, 9, 13, 6, 11, 5, 8, 3, 1, 14, 7, 12]]
That is, there are 7 rounds; each row above lists the seating arrangement around the table starting to the right of person 0.