Naive no-crossing

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

pf = 0.95;   % Packing factor

board = zeros(n);

len  = zeros(1,length(words));
for ii=1:length(words)
  len(ii)=length(words{ii});
end;
score = weights./(len+1);      % Score per letter placed for each word

% Estimated minimum number of letters that can be placed horizontally

lest = round(pf*floor((n+1)/2)*n);

% Sort all of the words by score per letter (highest first)

[score,idx]=sort(score,'descend');
len=len(idx); maxi=0; tmp=0;
for ii=1:length(words)
  newword{ii}=words{idx(ii)};
  tmp=tmp+len(ii)+1; if (tmp < lest), maxi=ii; end;
end;

used = zeros(1,length(words));
x=1; y=1;
while (maxi > 1) && (y < n)
  [x,y,board,used]=addbestword(x,y,board,newword,used,maxi,len);
  while (maxi > 0) && (used(maxi)==1), maxi=maxi-1; end;
end;

return;

function [x,y,board,used] = addbestword(x,y,board,newword,used,maxi,len)

  n=size(board,1);

  flag=0;
  for ii=maxi:-1:1
    if (used(ii)==0) && (len(ii) <= n-x)
      board(y,x:x+len(ii)-1)=newword{ii};
      used(ii)=1; 
      
      x = x+len(ii)+1; if (x>n-1), x=1; y=y+2; end;
      flag=1;
      break;
    end;
  end;

  if (flag==0), x=1; y=y+2; end;
return;