faster brute force plus

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

% Sample solver

% Copyright 2011 The MathWorks, Inc.

board = zeros(n);

% complexity check
% t = mtree('solver.m','-file');
% length(t.nodesize)
% mlint -cyc solver.m

Lengths = cellfun('length',words);
if std(Lengths) == 0 && Lengths(1) == n
    % disp('vertical or dot')
    [dummy,index] = sort(weights,'descend');
    if penalty == 0
        for i = 1:n
            board(i,:) = words{index(i)};
        end
    else
        for i = 1:floor(n/2)
            board(i*2,:) = words{index(i)};
        end
    end
elseif std(weights) == 0
    % disp('horizontal')
    % try to fit several in a line (greedy)
    [SortedL,index] = sort(Lengths);
    SortedWords = words(index);
    [board,SortedWords] = build_lines(SortedWords,SortedL);
    board = fit_vertical(board,SortedWords);
else
    % disp('other')
    % try to fit several in a line (greedy)
    [SortedW,index] = sort(weights,'descend');
    SortedWords = words(index);
    SortedL = Lengths(index);
    [board,SortedWords] = build_lines(SortedWords,SortedL);
    board = fit_vertical(board,SortedWords);
end

    function [board,SortedWords,SortedL] = build_lines(SortedWords,SortedL)
        board = zeros(n);
        WordsLeft = numel(words);
        k = 1;
        while WordsLeft > 0 && k <= n
            L = cumsum(SortedL + 1);
            L(1) = L(1) - 1;
            OnOneLine = find(L<=n);
            WordsLeft = WordsLeft - numel(OnOneLine);
            LineWords = [];
            for j = 1:numel(OnOneLine)
                LineWords = [LineWords, SortedWords{j} 0];
            end

            board(k,1:numel(LineWords)) = LineWords;

            SortedWords = SortedWords(OnOneLine(end)+1:end);
            SortedL = SortedL(OnOneLine(end)+1:end);

            if penalty == 0
                k = k + 1;
            else
                k = k + 2;
            end
        end
    end

    function board = fit_vertical(board,SortedWords)
        for j = 1:20 %numel(SortedWords)
            w = SortedWords{j}';
            nw = length(w);
            match_found = false;
            k = 1;
            while k <= n % check each column for a possible place
                t = board(:,k);
                incolumn = 1;
                while incolumn+nw-1 <= n && ~match_found
                    candidate = t(incolumn:incolumn+nw-1);
                    match_index = candidate > 0;
                    if all(candidate(match_index) == w(match_index))
                        comp1 = false;
                        if incolumn == 1, comp1 = true;
                        elseif t(incolumn-1) == 0, comp1 = true;
                        end
                        comp2 = false;
                        if incolumn+nw-1 == n, comp2 = true;
                        elseif t(incolumn+nw) == 0, comp2 = true;
                        end
                        comp3 = false;
                        if k == 1, comp3 = true;
                        else
                            left_neighbours = board...
                                (incolumn:incolumn+nw-1,k-1);
                            if left_neighbours(~match_index) == 0
                                comp3 = true;
                            end
                        end
                        comp4 = false;
                        if k == n, comp4 = true;
                        else
                            right_neighbours = board...
                                (incolumn:incolumn+nw-1,k+1);
                            if right_neighbours(~match_index) == 0
                                comp4 = true;
                            end
                        end

                        if comp1 && comp2 && comp3 && comp4
                            match_found = true;
                            board(incolumn:incolumn+nw-1,k) = w;
                        end
                    end
                    incolumn = incolumn + 1;

                end
                k = k + 2;
            end
        end
    end
end