V8

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

board = zeros(n);

ersteFreieSpalte = 1;
for k = 1:size(words,2)
    s(k) = size(words{k},2);
end

wps = weights ./ s;

restSpalten = n;

while restSpalten > 2
    blockWorth = [];
    blockNum = [];
    ersteFreieSpalte = n - restSpalten + 1;
    
    %FindeBestenBlock
    for i = 2:min(restSpalten,max(s))
        
        nw = wps;
        
        ix = s == i;
        ix = ~ix;
        nw(ix) = 0;
        [A wordIx] = sort(nw, 'descend');
        
        if A(n) > 0
            blockWorth = [blockWorth (sum(wps(wordIx(1:n))) - penalty * i )/ ((i+1) * n)] ; % *(i+1) ??
            blockNum = [blockNum i];
        else
            blockWorth = [blockWorth 0];
            blockNum = [blockNum i];
        end
    end
    
    % SchreibeBlock
    is = blockWorth == max(blockWorth);
    if sum(blockWorth) > 0
        compy = blockNum(is);
        compy = compy(1);
        
        nw = wps;
        ix = s == compy;
        ix = ~ix;
        nw(ix) = 0;
        [A wordIx] = sort(nw, 'descend');
        
        %Schreibe
        for i = 1:n
            board(i,ersteFreieSpalte:ersteFreieSpalte+compy-1) = words{wordIx(i)};
        end
    else
        % Kein Block gefunden
        break
    end
    
    %     ReduziereWortliste/Gewichte
    killList = wordIx(1:n);
    words(killList) = [];
    wps(killList) = [];
    s(killList) = [];
    
    %     ReduziereRestSpalten
    restSpalten = restSpalten - blockNum(is) - 1 ;
end

% FillItUp

curLen = 2;
nw = wps;
ix = s == curLen;
ix = ~ix;
nw(ix) = 0;
[A wordIx] = sort(nw, 'descend');

killList = [];

ersteFreieSpalte = n - restSpalten + 1;

spalte = ersteFreieSpalte;
zeile = 1;
while spalte + curLen <= n
    while zeile <= n
        i = wordIx(1);
        if s(i) == curLen
            if spalte + curLen <= n
                board(zeile,spalte:spalte+s(i)-1) = words{i};
                killList = [killList i];
            else
                break;
            end
            zeile = zeile + 1;
            
            if length(wordIx) > 1
                wordIx = wordIx(2:end);
            end
        else
            curLen = curLen + 1;
            nw = wps;
            ix = s == curLen;
            ix = ~ix;
            nw(ix) = 0;
            [A wordIx] = sort(nw, 'descend');
            i = wordIx(1);
        end
    end
    spalte = spalte + curLen + 1;
    zeile = 1;
end

words(killList) = [];
wps(killList) = [];
s(killList) = [];

ersteFreieSpalte = spalte;

ersteFreieSpalte = ersteFreieSpalte;

%V2 filler for empty Boards
if max(board) == 0

    board = zeros(n);

    for k = 1:size(words,2)
        s(k) = size(words{k},2);
    end
    newWeights = weights ./ s;
    [A wordIx] = sort(newWeights, 'descend');
    zeile = 1;
    spalte = 1;

    while zeile <= n
        while spalte < n
            i = wordIx(1);
            if s(i) <= n-spalte+1
                board(zeile,spalte:spalte+s(i)-1) = words{i};
                spalte = spalte + s(i) + 1;

                if length(wordIx) > 1
                    wordIx = wordIx(2:end);
                else
                    spalte = n;
                    zeile = n;
                end
            else
                spalte = n;
            end
        end
        spalte = 1;
        zeile = zeile + 2;
    end
end


board = board';


[A wordIx] = sort(wps, 'descend');
zeile = ersteFreieSpalte;
spalte = 1;

while zeile <= n
    while spalte < n
        i = wordIx(1);
        if s(i) <= n-spalte+1
            board(zeile,spalte:spalte+s(i)-1) = words{i};
            spalte = spalte + s(i) + 1;
            
            if length(wordIx) > 1
                wordIx = wordIx(2:end);
            else
                spalte = n;
                zeile = n;
            end
        else
            spalte = n;
        end
    end
    spalte = 1;
    zeile = zeile + 2;
end

board = board';




end