S1mple

function board = solver(words, weights, n, penalty)

hn = zeros(1,n);
wl = zeros(1,length(words));
for i=1:length(words)
    wl(i) = length(words{i});
    hn(wl(i)) = hn(wl(i))+1;
end

board = zeros(n);

usd = zeros(1,n);
usd(2:2:end) = n;

for i=n:-1:min(n,20)
    if hn(i) > 2*i;
        b = cmplts(words(wl==i), weights(wl==i), i, penalty);
        if ~isempty(b)
            board(1:i,1:i) = b;
            usd(1:2:min(n,i+1)) = i+1;
            break;
        end
    end
end

wr = weights./(wl+1);
[wrs, wri] = sort(wr);
ii = length(wri);
minusd = min(usd);
while ii>0 && minusd<=n-2
    i = wri(ii);
    if wl(i) <= n-minusd
        for j=1:n
            if wl(i) <= n-usd(j)
                board(j,usd(j)+1:usd(j)+wl(i)) = words{i};
                usd(j) = usd(j) + wl(i) + 1;
                minusd = min(usd);
                break;
            end
        end
    end
    ii = ii-1;
end

function board = cmplts(words, weights, n, penalty)

board = [];

m = length(words);

c = zeros(m,n);
for i=1:m
    c(i,:) = words{i};
end

c2s = unique(65536*c(:,1) + c(:,2));

[ii,jj] = meshgrid(1:m,1:m);
ii = ii(:);
jj = jj(:);
si = ii~=jj;
ii = ii(si);
jj = jj(si);

k = 1;
while k<=n && ~isempty(ii)
  r = 65536*c(ii,k) + c(jj,k);
  si = ismember(r,c2s);
  ii = ii(si);
  jj = jj(si);
  if k>20 && length(ii) > 2000
      return
  end
  k = k+1;
end

if isempty(ii)
    return
end

csol = {};
for i=1:length(ii)-1
    i1 = ii(i);
    i2 = jj(i);
    for j=(i+1):length(ii)
        j1 = ii(j);
        j2 = jj(j);
        if ~(all(all(c([i1 i2],1:2) == c([j1 j2],1:2)')))
            continue;
        end
        cr = c;
        cr([i1 i2 j1 j2],:) = [];
        board = zeros(n,n);
        board(:,1) = c(i1,:)';
        board(:,2) = c(i2,:)';
        board(1,:) = c(j1,:)';
        board(2,:) = c(j2,:)';
        for ri = 3:n
            cdi = find(cr(:,1) == board(1,ri) & cr(:,2) == board(2,ri));
            wrk = false;
            for wi = 1:length(cdi)
                board(:,ri) = cr(cdi(wi),:)';
                if all(ismember(board(3:end,1:ri),cr(:,1:ri),'rows'));
                    wrk = true;
                    break;
                end
            end
            if ~wrk
                break
            end
        end
        if wrk
            csol{end+1} = board;
        end
    end
end

if isempty(csol)
    board = [];
    return
elseif length(csol)==1
    board = csol{1};
else
    scm = doscore(csol{1}, words, weights, penalty);
    board = csol{1};
    for i=2:length(csol);
        sc = doscore(csol{i}, words, weights, penalty);
        if sc>scm
            scm = sc;
            board = csol{i};
        end
    end
end

function score = doscore(board, words, weights, penalty)
   board = [board; board'];
   board = unique(board,'rows');
   score = penalty*(size(board,1)-2*size(board,2));
   for i=1:size(board,1)
       for j=1:length(words)
           if all(board(i,:) == words{j})
               score = score + weights(j);
           end
       end
   end