vertical 2

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

board = zeros(n);
Used  = false(n+2);

NbWords = length(words);
for w = NbWords:-1:1
    WordsLength(w) = length(words{w});
end

RelativeWeights = weights ./ (WordsLength + 1);
[~,ind] = sort(RelativeWeights,'descend');

for w = 1:NbWords
    Word_Length = WordsLength(ind(w));
    
    % vertical placement :
    Zone = false(n+2);
    Zone(2:2+n-Word_Length , 2:end-1) = true;
    PossiblePosition = Zone & ~Used;
    [ROW,COL] = find(PossiblePosition); % start at (2,2)
    for pos = 1:length(ROW)
        row = ROW(pos);
        col = COL(pos);
            if      all(~Used(row + ( 0:Word_Length-1) , col))
                board(row-1 + (0:Word_Length-1), col-1) = words{ind(w)};
                Used (row   + (0:Word_Length-1), col + (-1:1) ) = true; % left-center-right
                Used (row   + Word_Length      , col  ) = true;         % below
                if row>2 && Used(row-2, col+1)
                    Used(row-1, col+1) = true;                          % top-right
                end
                break
            end
    end
end

end