vertical 4 (staggering)

function board = solver(words, weights, n, ~)
% solver vertical 4 (staggering)
board = zeros(n);
Free  = true(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 :
    if mod(w,2) % alternance to favorize staggering
        [ROW,COL] = find(Free(2 : 2+n-Word_Length , 2 : 2 : end-1));
        COL = 2 * COL - 1;
    else
        [ROW,COL] = find(Free(2 : 2+n-Word_Length , 3 : 2 : end-1));
        COL = 2 * COL;
    end
    for pos = 1:length(ROW)
        row = ROW(pos)+1; % start at (2,2)
        col = COL(pos)+1;
            if all(Free(row + ( 0:Word_Length-1) , col))
                board(row-1 + (0:Word_Length-1), col-1) = words{ind(w)};
                Free (row   + (0:Word_Length-1), col + (-1:1) ) = false; % left-center-right
                Free (row   + Word_Length      , col  ) = false;         % below
                if row>2 && ~Free(row-2, col+1)
                    Free(row-1, col+1) = false;                          % top-right
                end
                %Done = true;
                break
            end
    end
    %if Done, continue, end
    
    % horizontal placement
end

end