N in a row (or column)!
Python 2, 270 bytes

from random import*
e=lambda s,n:all(sum(map(ord,l))!=n*65for l in s)
R,C,d=randint,choice,[-1,1]
def w(a):
 print a;n=len(a);
 while e(a,n)and e(zip(*a),n):
    if n==2:x,y,w,z=0,0,0,1
    else:x,y=R(1,n-2),R(1,n-2);w,z=x+C(d),y+C(d)
    a[y][x],a[z][w]=a[z][w],a[y][x]
 print a

Always chooses A as character to complete a row/col. Performs random swaps until goal is reached.
Accepts the matrix as list of lists, usage for testing:
A=&quot;&quot;&quot;ADCD
BBBA
DACC
ACDB&quot;&quot;&quot;
a=[[c for c in l] for l in A.split('\n')]
w(a)