First try with special case

function board = solver(words, weights, n, penalty)
board = zeros(n);
nwords = length(words);
len = zeros(1, nwords); perf = len;
for i=1:nwords
   len(i) = length(words{i});
   perf(i) = weights(i)/len(i);
end
for i=2:n
    w = find(len==i);
    nlen(i) = length(w);
    [dum,pos] = sort(weights(w));
    wlen{i} = w(pos);
    if nlen(i)>0
       plen(i) = weights(wlen{i}(nlen(i)));
    else
       plen(i) = 0;
    end
end
if penalty > 0
for r=1:2:n
    left = n;
    while left >= 2
       possib = plen(2:left)./[3:left left];  % Prendre le plus gros ou le plus performant ?
       if any(possib > 0)
          sel = find(possib == max(possib)); sel=sel(1)+1;
          board(r, n-left+(1:sel)) = words{wlen{sel}(nlen(sel))};
          nlen(sel) = nlen(sel) - 1;
          if nlen(sel)>0
             plen(sel) = weights(wlen{sel}(nlen(sel)));
          else
             plen(sel) = 0;
          end
          left = left - (sel+1);
       else
          break;
       end
    end
end

   for i=n:-1:1 % trop couteux de trouver le plus grand maxcontig globalement -> col par col
      while 1
         flag = board == 0;
         flag = flag & [ones(1,n) ; flag(1:n-1,:)] & [flag(2:n,:) ; ones(1,n)] & [ones(n,1) flag(:,1:n-1)] & [flag(:,2:n) ones(n,1)];
         [mx,pos] = maxcontig(flag(:,i));
         if mx >= 2
            possib = plen(2:mx)./[3:mx mx];  % Prendre le plus gros ou le plus performant ?
            if any(possib > 0)
               sel = find(possib == max(possib)); sel=sel(1)+1;
               board(pos-1+(1:sel),i) = words{wlen{sel}(nlen(sel))};
               nlen(sel) = nlen(sel) - 1;
               if nlen(sel)>0
                  plen(sel) = weights(wlen{sel}(nlen(sel)));
               else
                  plen(sel) = 0;
               end
               continue;
            end
         end   
         break;
      end
   end

else
   
   for r=1:n
    left = n;
    while left >= 2
       possib = plen(2:left)./[3:left left];  % Prendre le plus gros ou le plus performant ?
       if any(possib > 0)
          sel = find(possib == max(possib)); sel=sel(1)+1;
          board(r, n-left+(1:sel)) = words{wlen{sel}(nlen(sel))};
          nlen(sel) = nlen(sel) - 1;
          if nlen(sel)>0
             plen(sel) = weights(wlen{sel}(nlen(sel)));
          else
             plen(sel) = 0;
          end
          left = left - (sel+1);
       else
          break;
       end
    end
end

   for i=n:-1:1 % trop couteux de trouver le plus grand maxcontig globalement -> col par col
      while 1
         flag = board == 0;
         flag = flag & [ones(1,n) ; flag(1:n-1,:)] & [flag(2:n,:) ; ones(1,n)] & [ones(n,1) flag(:,1:n-1)] & [flag(:,2:n) ones(n,1)];
         [mx,pos] = maxcontig(flag(:,i));
         if mx >= 2
            possib = plen(2:mx)./[2:mx];  % Prendre le plus gros ou le plus performant ?
            if any(possib > 0)
               sel = find(possib == max(possib)); sel=sel(1)+1;
               board(pos-1+(1:sel),i) = words{wlen{sel}(nlen(sel))};
               nlen(sel) = nlen(sel) - 1;
               if nlen(sel)>0
                  plen(sel) = weights(wlen{sel}(nlen(sel)));
               else
                  plen(sel) = 0;
               end
               continue;
            end
         end   
         break;
      end
   end
   
end
   function [len, pos] = maxcontig(v)
% too slow
%       len = v(end)>0; pos = length(v);
%       curlen = len; curpos = pos-1;
%       while curpos > 0
%          if (curlen > 0) && all(v([curpos curpos+1])>0)
%             curlen = curlen+1;
%             if curlen > len
%                len = curlen;
%                pos = curpos;
%             end
%          else
%             curlen = v(curpos) > 0;
%          end
%          curpos = curpos - 1;
%       end
%       return;
     
      
      if all(v==0)
         len = 0; pos = []; return;
      else
         len = 1;
      end
      while 1
         w = v(1:end-1) & v(2:end);
         if all(w==0)
            pos = find(v); pos=pos(1); return;
         else
            len = len+1;
            v = w;
         end
      end
   end


end