L^4

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

L = zeros(1,length(words));
for i = 1:length(L)
    L(i) = length(words{i});
end

s = sum(weights);

idx = find(L <= n & weights > 0);

board = zeros(n);

if ~isempty(idx)
    [hi_wt, temp] = sort((n-L(idx)).^4.*weights(idx),2,'descend');
    idx = idx(temp);
    
    for i = 1:2:n
        row = words{idx(1)};
        s = s - weights(idx(1));
        idx = idx(2:end);
        while (length(row) + min(L(idx))) < n
            w = find(L(idx) < (n - length(row)),1,'first');
            if ~isempty(w)
                row = [row 0 words{idx(w)}];
                s = s - weights(idx(w));
               idx = [idx(1:w-1) idx(w+1:end)];
            end
        end
        board(i,1:length(row)) = row;
    end
    
    old_s = s;
    old_board = board;
    
    for i = 2:2:n
        row = words{idx(1)};
        s = s - weights(idx(1));
        idx = idx(2:end);
        while (length(row) + min(L(idx))) < n
            w = find(L(idx) < (n - length(row)),1,'first');
            if ~isempty(w)
                row = [row 0 words{idx(w)}];
                s = s - weights(idx(w));
               idx = [idx(1:w-1) idx(w+1:end)];
            end
        end
        board(i,1:length(row)) = row;
    end

    p = 0;
    for i = 1:n
        temp = sum(board(2:end-1,i) == 0);
        p = p + temp + 1;
    end
    
    if (s + p*penalty) > old_s
        board = old_board;
        
    end
end

end