それぞれの人の強さがわかれば対戦表を埋めることは容易です。よって、この問題は次のように読み替えられます。

問題：「人 \(A_i\) は人 \(B_i\) より強い」という情報がいくつか与えられるので、人を強さの順に並べてください。

これはトポロジカルソートにほかなりません。より具体的には、\(N\) 人の人を頂点とし、「人 \(A_i\) は人 \(B_i\) より強い」という情報があるとき \(A_i\) から \(B_i\) への辺を張ったグラフのトポロジカルソートです。

トポロジカルソートは、「入次数 \(0\) の頂点とそれにつながる辺を削除する」という操作を繰り返すこと行えます。

入出力・データ変換がボトルネックとなり計算量は \(O(N^2)\) となります。

実装例(Python)

N=int(input())
S=[input() for _ in range(N)]
make=[s.count('x') for s in S]
ok=[i for i in range(N) if make[i]==0]  # 入次数 0 の頂点のリスト

order=[]  # 強い順

for i in ok:
  order.append(i)
  for j in range(N):
    if S[j][i]=='x':
      make[j]-=1
      if make[j]==0:
        ok.append(j)

# トポロジカルソートが最後まで行かなかった場合矛盾
if len(order)!=N:
  print("No")
  exit()

print("Yes")

rank=[-1]*N  # rank[i]=人iの強さ
for r,i in enumerate(order):
  rank[i]=r

for i in range(N):
  for j in range(N):
    if i==j:
      print("-", end="")
    elif rank[i]<rank[j]:
      print("o", end="")
    else:
      print("x", end="")
  print()