Finish 2011-04-20 12:00:00 UTC

Faster - no ram_li_czech_2

by Ram-Li-Czech

Status: Passed
Results: 6807200 (cyc: 35, node: 9285)
CPU Time: 117.481
Score: 17312.5
Submitted at: 2011-04-20 15:44:33 UTC
Scored at: 2011-04-20 18:11:00 UTC

Current Rank: 805th (Highest: 741st )
Based on: MorningAgain1 (diff)

Comments
Ram-Li-Czech
20 Apr 2011
Makes me feel good that I have the lowest score (not all the final submissions in the queue went through, though).

Problem: slow, high node

Three new solvers:

ram_li_czech: modification of james_1, forming 2x3 blocks rather than 2x2

ram_li_czech_3 : pretty proud of this one, it uses only the grid (1:2:end,1:2:end) for placement, zero bogus, nice patterns! Often creates nonsense though :)

ram_li_czech_2: My favourite. Starts placing 2x3 blocks ala ram_li_czech. Once exhausted, starts placing from the most important pieces. No bogus, and the result looks pretty dense. Give it a try! Too bad it is slow...

Have a nice day!

Ram-Li-Czech
20 Apr 2011
One more comment:

This solution has the following performance on the 100 provided training scenarios (on my PC):

results: 5940021.00
time: 41.68
Nicholas Howe
21 Apr 2011
Just noticed this entry. Nice results! I'm lucky it wasn't any faster...
Please login or create a profile.
Code
function out = solver(words, weights, N, penalty)
% -------------------------------------------------------------------------
% Originally based on: MorningAgain1 by Alan Chalker
% Further improved by adding some other solvers, and by my solvers
% -------------------------------------------------------------------------

[out,sux] = solver_volkan(words, weights, N);
if sux
%     board_idx = 13;
    return;
end

lengths                 = cellfun('length',words);
nws                     = numel(words);

words = words(end:-1:1); 
weights = weights(end:-1:1); 
lengths = lengths(end:-1:1) ;
[~,idx]                 = sortrows([weights'./lengths'  weights'],[-1 -2]);
words                   = words(idx);
weights                 = weights(idx);
lengths                 = lengths(idx);
board                   = zeros(N,'single');
SCORE = Inf * ones(1,25);
BOARD = cell(1,25);

if min(lengths) == N
    [BOARD{1}, SCORE(1)] = solver_nick_1(board, words, weights, N, penalty, lengths, nws);
    if SCORE(1)==0, board=BOARD{1};  out=double(board); board_idx = 1; return; end
end

sumw = sum(weights);
if penalty<50 || isinf(SCORE(1))
    [BOARD{3}, SCORE(3)]  = solver_nick_2  (board, words, weights, N, penalty, lengths, nws, sumw);
else
    SCORE(3) = SCORE(1)*5;
end
if SCORE(3)<2*SCORE(1) || isinf(SCORE(1))

    if N<101
        if mean(weights)/penalty<0.5
            [BOARD{5}, SCORE(5)]  = solver_nick_4  (board, words, weights, N, penalty, lengths, nws, sumw);
        end
        [BOARD{6}, SCORE(6)]  = solver_james1  (board, words, weights, N, penalty, lengths, nws, sumw);
        [BOARD{7}, SCORE(7)]  = solver_james2  (board, words, weights, N, penalty, lengths, nws);
    end

    [BOARD{8}, SCORE(8)]  = solver_victoria(board, words, weights, N, penalty, lengths, nws);
    if min(lengths) ~= N && N<101
        [BOARD{9}, SCORE(9)]  = solver_ram_li_czech(board, words, weights, N, penalty, lengths, nws, sumw);
        [BOARD{10},SCORE(10)] = solver_jirachai(words, weights, N, penalty);
        if length(weights)<1000
            [BOARD{11}, SCORE(11)]  = solver_ram_li_czech_3(board, words, weights, N, penalty, lengths, nws, sumw);
        end
    end
end

rand('state',666);
mywords=cell(1,5);
myweights=cell(1,5);
mylengths=cell(1,5);
for j=1:5
    idx1=randperm(nws);
    words1                   = words(idx1);
    weights1                 = weights(idx1);
    lengths1                 = lengths(idx1);
    [w1,idx]                  = sortrows([weights1'./lengths1'  weights1'],[-1 -2]);
    mywords{j}               = words1(idx);
    myweights{j}             = w1(:,2)';
    mylengths{j}             = lengths1(idx);
end

for j=1:5
    [BOARD{14+j}, SCORE(14+j)]    = solver_james1  (board, mywords{j}, myweights{j}, N, penalty, mylengths{j}, nws, sumw);
end

% % if N<101 && penalty<200
% %     [BOARD{21}, SCORE(21)]  = solver_ram_li_czech_2 (board, words, weights, N, penalty, lengths, nws, sumw);
% % end
% [BOARD{9}, SCORE(9)]    = solver_james1  (board, wordsflip, weights, N, penalty, lengths, nws, sumw);

[~, board_idx]          = min(SCORE);
board                   = BOARD{board_idx};
out = double(board);

end

function [board, result]               = solver_james1(board, words, weights, n, penalty, wordlengths, nwords, total)

[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
last2letterword = find(B(:,1)>2,1)-1;
%words2 = words(index(1:last2letterword));
w2l = index(1:last2letterword)'; % should be row vector for for

isUnplayed = true(1,nwords);
hopeless   = false(1,nwords);

[C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC
%wFromC=w2l(alphaix); % gives index in original words

points = 0;
c=1;
r=1;
L = 2; % dim of sq
while r+L-1 <= n,
    % try excluding words with letter frequencies of 1
    % ordering words by first and second letter would help
    sq = zeros(2);
    if ~isempty(w2l)
        C1 = C(:,1);
        [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq);
    end
    
    if ~sq,
        break; % no more 2x2s
    end
    board(r+(0:L-1),c+(0:L-1)) = sq;
    c=c+L+1;
    if c > n-(L-1),
        r =r+L+1;
        c=1;
    end
end
points = points + sum(weights(~isUnplayed));

% eliminate words that have already been played
[B,index]   = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words       = words(isUnplayed);
nwords      = numel(words);
isUnplayed2 = true(1,nwords);
k=1;
% play remaining unused 2 letter words here?


% index of last word to play in current row
stop_index  = min(nwords, n*k-c+1); % check that we haven't run out of words
start_index = 1;

while (r+B(stop_index,1)-1) <= n, % if the new row fits
    
    words_left          = stop_index - start_index + 1;                                 % num words to play in this row
    current_row_points  = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols
    
    if current_row_points > 0,
        for cc = c:min(n,words_left+c-1),
            wi = start_index-c+cc; % word index
            board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
            isUnplayed2(index(wi))    = false;
            
        end
        
        % the row is unplayed I think it will simply be blank
    end
    
    c=1;
    points = points + current_row_points;
    r=r+B(stop_index,1)+1; % increment row location
    
    k=k+1; % increment row number
    start_index=stop_index+1;
    stop_index = min(nwords, stop_index+n);
    
end

result = total - points;

wordlengths2 = wordlengths(isUnplayed);
weights2     = weights(isUnplayed);

[board,result] = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,result,n);

end
function [sq, isUnplayed, hopeless]    = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq)

ii_valid = w2l(isUnplayed(w2l) & ~hopeless(w2l));

for ii = ii_valid, % w2l must be a row vector here
    
    
    sq(1,:) = words{ii};
    isUnplayed(ii) = false;
    
    % only iterate over reasonable letters
    conda = C1 == sq(1,1);
    a1 = find(conda,1);
    a2 = find(conda,1,'last');
    w21jj  = w2l(sort(alphaix(a1:a2)));
    
    condb = C1 == sq(1,2);
    b1=find(condb,1);
    b2=find(condb,1,'last');
    
    w21kk  = w2l(sort(alphaix(b1:b2)));
    
    for jj = w21jj
        
        % eval order? also checks could be elim
        if isUnplayed(jj) && ~hopeless(jj)
            
            sq(2,1) = words{jj}(2);
            isUnplayed(jj) = false;
            
            condc = C1 == sq(2,1);
            
            c1=find(condc,1);
            c2=find(condc,1,'last');
            w21ll = w2l(sort(alphaix(c1:c2)));
            
            for kk = w21kk
                
                if isUnplayed(kk)
                    
                    sq(2,2)         = words{kk}(2);
                    isUnplayed(kk)  = false;
                    
                    for ll =  w21ll
                        
                        if isUnplayed(ll) && all(sq(2,:) == words{ll})
                            
                            isUnplayed(ll) = false;
                            
                            return; % press completed!
                        end
                    end
                    isUnplayed(kk) = true;
                end
            end
            isUnplayed(jj) = true;
        end
    end
    isUnplayed(ii) = true;
    
    % should mark words that didn't work out to avoid retrying them
    hopeless(ii) = true; % hopeless in positions 1 or 2
    
end

sq = zeros(2);


end
function [board, result]               = solver_james2(board, words, weights, n, penalty, wordlengths, nwords)
result=sum(weights);
[B,index] = sortrows([wordlengths' weights'],[1 -2]);

k=1;
c=1;
isUnplayed         = true(nwords,1);
current_stop_index = min(nwords, n*k); % check that we haven't run out of words

while (c+B(current_stop_index,1)-1) <= n,
    current_col_points = sum(B(((k-1)*n)+1:current_stop_index,2)) - penalty*B(k*n-1,1); % use length of next to last word to get number of penalty cols
    if current_col_points > 0,
        words_left = current_stop_index - n*(k-1);
        for r = 1:min(n,words_left),
            board(c:(c+B(r+(k-1)*n,1)-1),r) = words{index(r+(k-1)*n)};
            isUnplayed(index(r+(k-1)*n))    = false;
        end
    end
    result = result - current_col_points;
    c=c+B(current_stop_index,1)+1;
    
    k=k+1;
    current_stop_index = min(nwords, n*k);
end

[board,result] = james_sub_solver(board,wordlengths,weights,isUnplayed,words,result,n);

end
function [board,result]                = james_sub_solver(board, wordlengths,weights,isUnplayed,words,result,n)

wordlengths2 = wordlengths(isUnplayed);
weights2     = weights(isUnplayed);
words        = words(isUnplayed);
[~,idx_sort] = sort(wordlengths2 - weights2/max(weights2) );

tres_ceros   = board(3:end,1)==0 & board(2:end-1,2)==0 & board(1:end-2,1)==0;
r_ini        = find(tres_ceros) + 1;

if board(n,1)==0 && board(n-1,1)==0
    r_ini = [r_ini; n];
end

k = 1;
for p = 1:length(r_ini)
    
    r = r_ini(p);
    if board(r-1,1)==0
        
        c = 1;
        while c < n && board(r-1,c)==0
            word_n = words{idx_sort(k)};
            c2     = c + numel(word_n);
            if c2-1 <= n && board(r-1,c2-1)==0
                board(r,c:c2-1) = word_n;
                k = k + 1;
                result = result - weights2(idx_sort(k));
            end
            c = c2 + 1;
        end
    end
end

end
function [board, score]                = solver_victoria(board, words, weights, N, penalty, L, QWords)
% Victoria's solver
score           = 0;
PThresh         = 0.195;
WordsInUse      = false(1,QWords);
%SpecificWeights = weights./L;
%[~,IndWS]       = sort(SpecificWeights,'descend');
IndWS=1:length(weights);
SpecLCum        = cumsum(L(IndWS) + 1);
MaxQ            = numel(find(SpecLCum <= N.*(N+1)));
GoodWeight      = sum(weights(IndWS(1:MaxQ)));
BadGoodCoef     = N.*penalty./GoodWeight;
P               = BadGoodCoef > PThresh;
L_slots         = P*ceil(N/2) + (1-P)*N; % innovation filter :P
MaxQ            = P*numel(find(SpecLCum <= (N+1).^2/2)) + (1-P)*MaxQ;
slots           = ones(1, L_slots);

LoL             = min(L(IndWS(1:MaxQ)));
HiL             = max(L(IndWS(1:MaxQ)));
IndL            = zeros(MaxQ,1);
l               = 1;
for n = HiL:-1:LoL
    idx_long       = find(L(IndWS(1:MaxQ))==n);
    l2             = l + numel(idx_long);
    IndL(l:l2-1)   = idx_long;
    l              = l2;
end
IndWS(1:MaxQ)      = IndWS(IndL);

n       = 1;
seguir  = (min(slots) < N)*(n <= QWords);

while seguir
    
    Space                       = N - L(IndWS(n)) + 1 - slots;
    SlotIndex                   = find(~Space,1);
    
    if isempty(SlotIndex)
        [Espacio,SlotIndex]     = max(Space);
    else
        Espacio                 = 1;
    end
    
    if Espacio > 0
        
        idx_f                   = (1+P)*SlotIndex-P;
        idx_c                   = slots(SlotIndex):slots(SlotIndex) + L(IndWS(n)) - 1;
        board(idx_f,idx_c)      = words{IndWS(n)};
        slots(SlotIndex)        = slots(SlotIndex) + L(IndWS(n)) + 1;
        score                   = score + weights(IndWS(n));
        WordsInUse(IndWS(n))    = true;
        
    end
    
    n       = n + 1;
    seguir  = (min(slots) < N)*(n <= QWords);
    
end

QWords = QWords*(P>0);

for n = 1:QWords
    
    CurInd  = IndWS(n);
    CurL    = L(CurInd);
    word_c  = words{CurInd};
    
    entrar  = (~WordsInUse(CurInd))*(CurL/2 ~= round(CurL/2));
    
    if entrar
        
        [I,J] = find(board(1:N - CurL + 1,:) == word_c(1));
        
        if ~isempty(I)
            
            k = 1;
            seguir = (~WordsInUse(CurInd))*(k <= numel(I));
            while seguir
                
                if all(word_c(1:2:end) == board(I(k):2:I(k) + CurL - 1,J(k))')
                    
                    board(I(k):I(k) + CurL - 1,J(k)) = word_c';
                    
                    score = score + weights(IndWS(n));
                    
                    WordsInUse(IndWS(n)) = true;
                    
                end
                
                k = k + 1;
                seguir = (~WordsInUse(CurInd))*(k <= numel(I));
            end
        end
    end
end

[board, score] = victoria_sub_solver(board,words,L,weights,WordsInUse,N,score);

%--
pboard  = [board;zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1) + 1;
score   = sum(weights(:)) - score + penalty*ntrans;

end
function [board, score]                = victoria_sub_solver(board, words,L,weights,WordsInUse,N,score)

L2           = L(~WordsInUse);
weights2     = weights(~WordsInUse);
words        = words(~WordsInUse);
[~,idx_sort] = sort(L2 - weights2/max(weights2) );

tres_ceros   = board(1,3:end)==0 & board(1,2:end-1)==0 & board(1,1:end-2)==0;
r_ini        = find(tres_ceros) + 1;

if board(1,N)==0 && board(1,N-1)==0
    r_ini = [r_ini; N];
end
k = 1;

for p = 1:length(r_ini)
    
    r = r_ini(p);
    
    if board(1,r-1)==0
        
        c = 1;
        
        while c < N && board(c,r-1)==0
            word_n = words{idx_sort(k)};
            c2     = c + numel(word_n);
            if c2-1 <= N && all(board(c:c2-1,r)==0)
                board(c:c2-1,r) = word_n;
                k = k + 1;
                score = score + weights2(idx_sort(k));
            end
            c = c2 + 1;
            % figure(4), imagesc(board)
        end
    end
end

end
function [board0, s0]                  = solver_nick_1(board, words, weights, N, penalty, wlen, nword)

% Nicks's solver
maxnwo = 800 ;
if numel(words)>maxnwo
rand();
ridx = randperm(numel(words));
ridx = ridx(1:maxnwo) ;
words=words(ridx);
wlen = wlen(ridx);
weights = weights(ridx);
nword = maxnwo ;
end

wmat        = cat(1,words{:});
m           = cell(N);

for n = 1:N
    m{n,1} = double(sparse(bsxfun(@eq,wmat(:,n),wmat(:,1)')));
    m{3,n} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,n)')));
end

rwords = zeros(1,N);
cwords = zeros(1,N);

n       = 1;
pm      = ones(nword);
m13     = m{n,1}*m{3,n};
ppm     = pm & m13;

seguir  = (n + 2 < N)*any(ppm(:));
while seguir
    pm      = ppm;
    m13     = m{n,1}*m{3,n};
    ppm     = pm & m13;
    n       = n + 2;
    seguir  = (n<N)*any(ppm(:));
end

icross              = n;
open                = true(1,nword);
[i1,i3]             = find(pm);
i1                  = i1(1);
i3                  = i3(1);
open(i1)            = false;
open(i3)            = false;
board(1,:) = words{i1};
board(3,:) = words{i3};
rwords(1)           = i1;
rwords(3)           = i3;

for n = 1:2:icross
    
    iword = find((m{n,1}(i1,:).*m{3,n}(:,i3)') & open);
    
    if ~isempty(iword)
        iword                   = iword(1);
        cwords(n)               = iword;
        board(1:wlen(iword),n)  = words{iword}';
        open(iword)             = false;
    end
end

% fill in remaining crosses, if possible.
%fcwords     = cwords(cwords>0);
height      = N ;
open        = open';
votes       = zeros(N);

for n = 5:height
    cols            = find(board(n,:)~=0);
    matches         = bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0);
    [~,bm]          = max(open.*sum(matches,2));
    votes(n,cols)   = 2*matches(bm,:)-1;
end
bad                     = sum(votes)<0;
badword                 = cwords(bad(1:icross));
open(nonzeros(badword)) = true;
board([2 4:end],bad)    = 0;
cwords(bad)             = 0;

n = 5;
while (n <= height)
    cols    = find(board(n,:)~=0);
    row     = find(open & all(bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0),2),1);
    if ~isempty(row)
        open(row)               = false;
        board(n,1:wlen(row))    = words{row};
        rwords(n)               = row;
        n                       = n + 2;
    else
        n                       = n + 1;
    end
end
% s0      = sum(weights(open));
% board0  = board;
S         = zeros(2,1);
S(1)      = sum(weights(open));
BOARD{1}  = board;

% now try full fill
[board, s1] = solver_nick_1p5(rwords,cwords,N,board,wmat,open,words,weights,wlen,penalty);

S(2)        = s1;
BOARD{2}    = board;

[s0,b_idx] = min(S);
board0     = BOARD{b_idx};

end
function [board, s1]                   = solver_nick_1p5(rwords,cwords,N,board,wmat,open,words,weights,wlen,penalty)

openr   = rwords==0;
openc   = cwords==0;
goodc   = ~openc;
votes   = zeros(N);

for c = find(openc)
    rows            = find(board(:,c)~=0);
    matches         = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
    [~,bm]          = max(open.*sum(matches,2));
    votes(rows,c)   = 2*matches(bm,:)-1;
end

bad                         = sum(votes,2) <= -sum(goodc);
badwords                    = rwords(bad);
open(nonzeros(badwords))    = true;
board(openr,bad)            = 0;

for c = find(openc)
    rows        = find(board(:,c)~=0);
    matches     = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
    wi          = find(open & all(matches,2),1);
    if ~isempty(wi)
        open(wi)            = false;
        board(1:wlen(wi),c) = words{wi};
        cwords(c)           = wi;
    end
end

openr = rwords==0;
openc = cwords==0;
goodr = ~openr;
votes = zeros(N);

for r = find(openr)
    cols            = find(board(r,:)~=0);
    matches         = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
    [~,bm]          = max(open.*sum(matches,2));
    votes(r,cols)   = 2*matches(bm,:)-1;
end

bad                         = sum(votes,2)<= -sum(goodr);
badwords                    = cwords(bad);
open(nonzeros(badwords))    = true;
board(bad,openc)            = 0;

for r = find(openr)
    cols        = find(board(r,:)~=0);
    matches     = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
    wi          = find(open & all(matches,2),1);
    if ~isempty(wi)
        open(wi)            = false;
        board(r,1:wlen(wi)) = words{wi};
        rwords(r)           = wi;
    end
end

board(board==0) = 1;
s1              = sum(weights(open)) + penalty*(sum(rwords==0) + sum(cwords==0));

end
function [board , s]                   = solver_nick_2(board, words, weights, N, penalty, wlen, nws, sumw)
w       = 0;
open    = true(1,nws);

for n = [1:2:N,2:2:N]
    l = 0;
    k = find(open & (wlen<=N-l),1);
    while ~isempty(k)
        open(k)                = false;
        word                   = words{k};
        L_word                 = numel(word);
        board(n,l+1:l+L_word)  = word;
        l                      = l + L_word + 1;
        w                      = w + weights(k);
        k                      = find(open & (wlen <= N-l),1);
    end
end

pboard  = [board;zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1);
w       = w - penalty*ntrans;
s       = sumw - w;

end
function [board2, s]                   = solver_nick_4(board2, words, weights, N, penalty, wlen, nword, sumw)

w2              = 0;
open            = true(1,numel(words));
filled          = zeros(1,N);
filled(2:2:end) = 1;
brk             = false;

while (filled(1)<N)
    
    wlen2           = wlen.*open;
    wlen2(~open)    = 1;
    nlen            = accumarray(wlen2(:),ones(nword,1));
    k               = find(open & (wlen <= N-filled(1) -1) & (nlen(wlen)' >=N),1);
    if isempty(k)
        brk         = true;
        break
    end
    targ                                 = wlen(k);
    board2(1,filled(1)+1:filled(1)+targ) = words{k};
    open(k)                              = false;
    w2                                   = w2 + weights(k);
    wlen_eq_targ                         = wlen==targ;
    for n = 2:N
        k                                    = find(open & wlen_eq_targ,1); % DFM SPEED
        board2(n,filled(n)+1:filled(n)+targ) = words{k};
        open(k)                              = false;
        w2                                   = w2 + weights(k);
    end
    filled = filled + targ + 1;
    
end

if brk
    % try two half-sets
    [brk,board2,open,w2,filled] = nick_two_halves(board2,words,weights,wlen,nword,filled,open,N,w2);
end

if brk
    % try two half-sets off by 2
    [brk,board2,open,w2,filled] = nick_two_halves_off(board2,words,weights,wlen,nword,filled,open,N,w2);
    
end

if brk && any(board2(:))
    % finish filling board normally
    for n = 1:N
        k = find(open & (wlen<=N-filled(n)),1);
        while ~isempty(k)
            open(k)                                     = false;
            word                                        = words{k};
            board2(n,filled(n)+1:filled(n)+numel(word)) = word;
            filled(n)                                   = filled(n) + numel(word) + 1;
            w2                                          = w2 + weights(k);
            k                                           = find(open & (wlen<=N-filled(n)),1);
        end
    end
end
pboard  = [board2; zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1);
w2      = w2 - penalty*ntrans;
s       = sumw - w2;

end
function [brk,board2,open,w2,filled]   = nick_two_halves(board2,words,weights,wlen,nword,filled,open,N,w2)

brk = false;
while filled(1) < N
    wlen2           = wlen.*open;
    wlen2(~open)    = 1;
    nlen            = accumarray(wlen2(:),ones(nword,1));
    ldir            = 2*(filled(1) > filled(2)) - 1;
    nlen(1)         = 0;
    k               = find(open & (wlen <= N-filled(1) - 1) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+ldir)'>=ceil(N/2)),1);
    if isempty(k)
        brk         = true;
        break
    end
    targ                                 = wlen(k);
    board2(1,filled(1)+1:filled(1)+targ) = words{k};
    open(k)                              = false;
    w2                                   = w2 + weights(k);
    for n = 2:N
        idir                                      = ldir*(mod(n,2)==0);
        k                                         = find(open&(wlen==targ+idir),1);
        board2(n,filled(n)+1:filled(n)+targ+idir) = words{k};
        open(k)                                   = false;
        w2                                        = w2 + weights(k);
    end;
    filled = filled + targ + 1;
end

end
function [brk,board2,open,w2,filled]   = nick_two_halves_off(board2,words,weights,wlen,nword,filled,open,N,w2)

% try two half-sets off by 2
brk = false;
while filled(1) < N
    wlen2           = wlen.*open;
    wlen2(~open)    = 1;
    nlen            = accumarray(wlen2(:),ones(nword,1));
    nlen(1)         = 0;
    nlen(end+2)     = 0;
    k0              = find(open&(wlen<=N-filled(1)-2) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+2)'>=ceil(N/2)),1);
    if isempty(k0)
        brk = true;
        break
    end
    if filled(1)>filled(2)
        targ            = ones(1,N)*wlen(k0);
        targ(2:2:end)   = wlen(k0)+2;
    else
        targ            = ones(1,N)*(wlen(k0)+2);
        targ(2:2:end)   = wlen(k0);
    end
    for n = 1:N
        k                                       = find(open&(wlen==targ(n)),1);
        board2(n,filled(n)+1:filled(n)+targ(n)) = words{k};
        open(k)                                 = false;
        w2                                      = w2 + weights(k);
    end
    filled = filled + targ + 1;
end


end
function [board, result] = solver_ram_li_czech(board, words, weights, n, penalty, wordlengths, nwords, total)
% based on james1 solver

[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
isUnplayed = true(1,nwords);

wordlengths = wordlengths(index);
words       = words(index);
weights     = weights(index);

points = 0;


% RAM-LI-CZECH : rectangles 2xN
r = 1; c = 1;
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 n],board,points,r,c,B,isUnplayed,words,n);
[board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 3],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 2],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 4],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 5],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 4],board,points,r,c,B,isUnplayed,words,n);

points = points + sum(weights(~isUnplayed));

% last2letterword = find(B(:,1)>2,1)-1;
%words2 = words(index(1:last2letterword));
% w2l = index(1:last2letterword)'; % should be row vector for for

% [C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC
%wFromC=w2l(alphaix); % gives index in original words

% eliminate words that have already been played
[B,index]   = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words       = words(isUnplayed);
nwords      = numel(words);
isUnplayed2 = true(1,nwords);
k=1;
% play remaining unused 2 letter words here?

% index of last word to play in current row
stop_index  = min(nwords, n*k-c+1); % check that we haven't run out of words
start_index = 1;

while (r+B(stop_index,1)-1) <= n, % if the new row fits
    
    words_left          = stop_index - start_index + 1;                                 % num words to play in this row
    current_row_points  = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols
    
    if current_row_points > 0,
        for cc = c:min(n,words_left+c-1),
            wi = start_index-c+cc; % word index
            board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
            isUnplayed2(index(wi))    = false;
            
        end
        
        % the row is unplayed I think it will simply be blank
    end
    
    c=1;
    points = points + current_row_points;
    r=r+B(stop_index,1)+1; % increment row location
    
    k=k+1; % increment row number
    start_index=stop_index+1;
    stop_index = min(nwords, stop_index+n);
    
end

result = total - points;

wordlengths2 = wordlengths(isUnplayed);
weights2     = weights(isUnplayed);

[board,result] = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,result,n);

end
function [board, result] = solver_ram_li_czech_2(board, words, weights, n, penalty, wordlengths, nwords, total)
% based on james1 solver

[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
isUnplayed = true(1,nwords);

% wordlengths = wordlengths(index);
words       = words(index);
weights     = weights(index);

points = 0;


% RAM-LI-CZECH : rectangles 2xN
r = 1; c = 1;
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 n],board,points,r,c,B,isUnplayed,words,n);
[board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 3],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 2],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 4],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 5],board,points,r,c,B,isUnplayed,words,n);
% [board,points,r,c,isUnplayed] = ram_li_czech_subsolver([2 4],board,points,r,c,B,isUnplayed,words,n);
% points = points + sum(weights(~isUnplayed));

% eliminate words that have already been played
% [B,index]   = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words       = words(isUnplayed);
weights     = weights(isUnplayed);
nwords      = numel(words);
isUnplayed2 = true(1,nwords);
% k=1;

words = words(end:-1:1);
weights = weights(end:-1:1);

% RAM-LI-CZECH SUPER POWER PHASE

dist_global = abs(repmat((1:n),n,1)-n/2);
dist_global = dist_global+dist_global';
dist_global = max(dist_global(:)) - dist_global;

hv = -1*(board~=0); % to store whether at board(i,j) is hor(-1) or ver(+1) word
hvt = conv2(double(hv~=0),[1 1 1],'valid')==3;
hvtl = [hvt zeros(n,2)];
hvtr = [zeros(n,2) hvt];
hv(hvtl~=0)=-2;
hv(hvtr~=0)=-3;
errors = 0;
mi=nwords;

while mi>=1

    % horizontal placement
    word = words{mi};
    
    if mod(mi,2)~=0, board = board'; hv = -hv'; end
    
    % horizontal placement
    lw = length(word);
    
    % init
    possible = true(n);
    possible(:,n-lw+2:end) = 0;
    
    % check for actual possible positions
    
    price = zeros(n);
    for i=1:lw
        XX = (board(:,i:end-lw+i)==word(i));
        price(:,1:n-lw+1) = price(:,1:n-lw+1) + XX;
        possible(:,1:n-lw+1) = possible(:,1:n-lw+1) & ((board(:,i:end-lw+i)==0) | XX);
    end
    
    % check for space before
    possible(:,2:n-lw+1) = possible(:,2:n-lw+1) & (hv(:,1:n-lw)==0);
    % check for space after
    possible(:,1:n-lw) = possible(:,1:n-lw) & (hv(:,lw+1:end)==0);
    % check for space above
    for i=1:lw
        possible(2:end,1:end-lw+1) = possible(2:end,1:end-lw+1) & (hv(1:end-1,i:end-lw+i)>=0) & (hv(1:end-1,i:end-lw+i)~=3);
    end
    % check for space below
    for i=1:lw
        possible(1:end-1,1:end-lw+1) = possible(1:end-1,1:end-lw+1) & (hv(2:end,i:end-lw+i)>=0) & (hv(2:end,i:end-lw+i)~=2);
    end
    % remove any other horizontal word
    possible = possible & hv>=0;
    
    % place to the most top left possible position
    dist = dist_global - 3*n*price;
    dist(~possible) = 3*n;
    m = min(min(dist));
    [x,y] = find(dist == m);
    
    if ~isempty(x) && m<3*n
        placed = 1;
        r = ceil(rand()*length(x));
        board(x(r),y(r):y(r)+lw-1) = word;
        hv(x(r),y(r)) = -2; % starting point of the word
        hv(x(r),y(r)+1:y(r)+lw-2) = -1;
        hv(x(r),y(r)+lw-1) = -3; % end point of the word

        isUnplayed2(mi) = 0;
    else
        placed = 0;
    end
    
    if mod(mi,2)~=0, board = board'; hv = -hv'; end

    
    errors = errors + (placed==0);
    if errors == 20
        result = sum(weights(isUnplayed2));        
        return;
    end
    mi = mi-1;
end
result = sum(weights(isUnplayed2));        

end
function [rectangle,triple_idx] = find_three_pairs(M,w2,nw2,w2_idx)
    D = size(M,2);
    S = cell(D,1);
    num = zeros(D,1);
    triple_idx = zeros(D,1);
    rectangle = [];
    if isempty(w2), return; end
    for k=1:D
%         S{k} = find(sum(conv2(double((w2-repmat(M(:,k)',nw2,1))==0),[1 1],'valid'),2)==2);
        % optimized:
        curr = M(:,k)';
        S{k} = find((w2(:,1) == curr(1)).*(w2(:,2)==curr(2)));
        num(k) = length(S{k});
        if num(k)==0,break;end
    end
    if sum(num>0)==D
        if D==3
            for a = 1:length(S{1})
                for b = 1:length(S{2})
                    for c = 1:length(S{3})
                            if length(unique([S{1}(a),S{2}(b),S{3}(c)]))==D
                                rectangle = M;
                                triple_idx(1) = w2_idx(S{1}(a));
                                triple_idx(2) = w2_idx(S{2}(b));
                                triple_idx(3) = w2_idx(S{3}(c));
                                return;
                            end

                    end
                end
            end
        elseif D==2
            for a = 1:length(S{1})
                for b = 1:length(S{2})
                    if length(unique([S{1}(a),S{2}(b)]))==D
                        rectangle = M;
                        triple_idx(1) = w2_idx(S{1}(a));
                        triple_idx(2) = w2_idx(S{2}(b));
                        return;
                    end
                end
            end
        elseif D==4
            for a = 1:length(S{1})
                for b = 1:length(S{2})
                    for c = 1:length(S{3})
                        for d = 1:length(S{4})
                            if length(unique([S{1}(a),S{2}(b),S{3}(c),S{4}(d)]))==D
                                rectangle = M;
                                triple_idx(1) = w2_idx(S{1}(a));
                                triple_idx(2) = w2_idx(S{2}(b));
                                triple_idx(3) = w2_idx(S{3}(c));
                                triple_idx(4) = w2_idx(S{4}(d));
                                return;
                            end
                        end

                    end
                end
            end
        elseif D==5
            for a = 1:length(S{1})
                for b = 1:length(S{2})
                    for c = 1:length(S{3})
                        for d = 1:length(S{4})
                            for e = 1:length(S{5})
                                if length(unique([S{1}(a),S{2}(b),S{3}(c),S{4}(d),S{5}(e)]))==D
                                    rectangle = M;
                                    triple_idx(1) = w2_idx(S{1}(a));
                                    triple_idx(2) = w2_idx(S{2}(b));
                                    triple_idx(3) = w2_idx(S{3}(c));
                                    triple_idx(4) = w2_idx(S{4}(d));
                                    triple_idx(5) = w2_idx(S{5}(e));
                                    return;
                                end
                            end
                        end
                    end
                end
            end
        elseif D==6
            for a = 1:length(S{1})
                for b = 1:length(S{2})
                    for c = 1:length(S{3})
                        for d = 1:length(S{4})
                            for e = 1:length(S{5})
                                for f = 1:length(S{6})
                                    if length(unique([S{1}(a),S{2}(b),S{3}(c),S{4}(d),S{5}(e),S{6}(f)]))==D
                                        rectangle = M;
                                        triple_idx(1) = w2_idx(S{1}(a));
                                        triple_idx(2) = w2_idx(S{2}(b));
                                        triple_idx(3) = w2_idx(S{3}(c));
                                        triple_idx(4) = w2_idx(S{4}(d));
                                        triple_idx(5) = w2_idx(S{5}(e));
                                        triple_idx(6) = w2_idx(S{6}(f));
                                        
                                        return;
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end
    end
end
function [board,x,y] = place_rectangles(rectangles,n,board,r,c)
    D = size(rectangles,2);
    R = 2;
    x = r; y = c;
    for i=1:2:size(rectangles,1)
        board(x:x+1,y:y+D-1) = rectangles(i:i+1,:);
        y = y + D + 1;
        if y+D-1>n
            x = x+R+1;
            y = 1;
        end
        if x+1>n
            return;
        end
    end
end
function w2graph = generateGraph(w2,dim,letters)
    w2graph = zeros(dim);
    for i=1:size(w2,1);
        w2graph(letters==w2(i,1),letters==w2(i,2)) = w2graph(letters==w2(i,1),letters==w2(i,2)) + 1;
    end
end
function bool = plausible(W,w2graph,letters)
    bool = false;
    for i=1:size(W,2)
        if w2graph(letters==W(1,i),letters==W(2,i))==0, return; end
    end
    bool = true;
end
function w2graph = updateGraph(W,w2graph,letters)
    for i=1:size(W,2)
        w2graph(letters==W(1,i),letters==W(2,i))=w2graph(letters==W(1,i),letters==W(2,i))-1;
    end
end
function [board,points,r,c,isUnplayed] = ram_li_czech_subsolver(DIM,board,points,r,c,B,isUnplayed,words,n)
rectangles = [];
w2_idx = find(B(:,1)==DIM(1)); nw2 = length(w2_idx);
w2 = cell2mat(words(w2_idx)');
letters = unique(w2(:));
w2graph = generateGraph(w2,length(letters),letters);
w3_idx = find(B(:,1)==DIM(2)); nw3 = length(w3_idx);
w3 = cell2mat(words(w3_idx)');
for i=1:nw3-1
    for j=i+1:nw3
        if isUnplayed(w3_idx(i)) && isUnplayed(w3_idx(j))
            w31 = w3(i,:);
            w32 = w3(j,:);
            rectangle = [];
            W = [w31;w32];
            if plausible(W,w2graph,letters)
                [rectangle,triple_idx] = find_three_pairs(W,w2,nw2,w2_idx);
            end
            W = [w32;w31];
            if plausible(W,w2graph,letters) && isempty(rectangle)
                [rectangle,triple_idx] = find_three_pairs(W,w2,nw2,w2_idx);
            end
            if ~isempty(rectangle)
                w2graph_backup = w2graph;
                w2graph = updateGraph(rectangle,w2graph,letters);
                if sum(w2graph(:)<0)==0
                    isUnplayed([triple_idx;w3_idx([i;j])]) = 0;
                    rectangles = [rectangles;rectangle];
                    % update unplayed pairs
                    w2_idx = find(logical(B(:,1)==2) & isUnplayed');
                    nw2 = length(w2_idx);
                    w2 = cell2mat(words(w2_idx)');
                else
                    w2graph = w2graph_backup;
                end
            end
        end
    end
end

% place rectangles
[board,r,c] = place_rectangles(rectangles,n,board,r,c);

end

function [board,s] = solver_jirachai(words, weights, n, penalty)

% 1st strategy: Fill-in-the-blanks

% Initialization
board = zeros(n);

num_words = length(weights);

indices = 1:num_words;

word_length = zeros(size(indices));
for i = 1:num_words
    word_length(i) = length(words{i});
end


% Criteria
[temp ind] = sort(word_length, 2, 'ascend'); % prefer short word

weights     = weights(ind);
indices     = indices(ind);
word_length = word_length(ind);


% Estimate the location of the last word to be used
num_rows = [n floor(n/2)];
possible_sum = n * num_rows(1  + (penalty > 0));

cumulate = 0;
count    = 1;
while( (cumulate < possible_sum) && (count <= num_words) )
    cumulate = cumulate + word_length(count) + 1;
    count    = count + 1;
end
count = count - 1;


% Rearrange according to weight in descending order for a given word length
I = find(word_length == word_length(count));
[temp ind] = sort(weights(I), 2, 'descend');

weights(I)     = weights(I(ind));
indices(I)     = indices(I(ind));
word_length(I) = word_length(I(ind));


% Make them fill in better
weights(1:count)     = weights(count:-1:1);
indices(1:count)     = indices(count:-1:1);
word_length(1:count) = word_length(count:-1:1);


% Pick and place
num_words_left = num_words;
inc = 1 + (penalty > 0);
for row = 1:inc:n
    col_i = 1;
    count = 1;
    while( (col_i < n) && (count <= num_words_left) )
        col_f = col_i + word_length(count) - 1;
        
        if col_f <= n
            board(row, col_i:col_f) = words{indices(count)};

            weights(count)     = -1;
            indices(count)     = -1;
            word_length(count) = -1;
            
            col_i = col_f + 2;
        end
        
        count = count + 1;
    end
    weights     = weights(weights > 0);
    indices     = indices(indices > 0);
    word_length = word_length(word_length > 0);
    
    num_words_left = length(weights);
end
s = sum(weights);
end

function [board, result] = solver_ram_li_czech_3(board, words, weights, n, penalty, wordlengths, nwords, total)
% based on james1 solver

[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
isUnplayed = true(1,nwords);

% wordlengths = wordlengths(index);
words       = words(index);
weights     = weights(index);
words       = words(isUnplayed);
weights     = weights(isUnplayed);
nwords      = numel(words);
isUnplayed2 = true(1,nwords);
% k=1;

words = words(end:-1:1);
weights = weights(end:-1:1);

% RAM-LI-CZECH SUPER POWER PHASE

dist_global = abs(repmat((1:n),n,1)-n/2);
dist_global = dist_global+dist_global';
dist_global = max(dist_global(:)) - dist_global;

hv = -1*(board~=0); % to store whether at board(i,j) is hor(-1) or ver(+1) word
hvt = conv2(double(hv~=0),[1 1 1],'valid')==3;
hvtl = [hvt zeros(n,2)];
hvtr = [zeros(n,2) hvt];
hv(hvtl~=0)=-2;
hv(hvtr~=0)=-3;
for run=1:2
errors = 0;
mi=nwords;
while mi>=1
    if ((run==1 && length(words{mi})>3) || (run==2 && length(words{mi})<4)) && isUnplayed2(mi)
        % horizontal placement
        word = words{mi};

        if mod(mi,2)~=0, board = board'; hv = -hv'; end

        % horizontal placement
        lw = length(word);

        % init
        possible = true(n);
        possible(:,n-lw+2:end) = 0;

        % check for actual possible positions

        price = zeros(n);
        for i=1:lw
            XX = (board(:,i:end-lw+i)==word(i));
            price(:,1:n-lw+1) = price(:,1:n-lw+1) + XX;
            possible(:,1:n-lw+1) = possible(:,1:n-lw+1) & ((board(:,i:end-lw+i)==0) | XX);
        end

        % check for space before
        possible(:,2:n-lw+1) = possible(:,2:n-lw+1) & (hv(:,1:n-lw)==0);
        % check for space after
        possible(:,1:n-lw) = possible(:,1:n-lw) & (hv(:,lw+1:end)==0);
        % check for space above
        for i=1:lw
            possible(2:end,1:end-lw+1) = possible(2:end,1:end-lw+1) & (hv(1:end-1,i:end-lw+i)>=0) & (hv(1:end-1,i:end-lw+i)~=3);
        end
        % check for space below
        for i=1:lw
            possible(1:end-1,1:end-lw+1) = possible(1:end-1,1:end-lw+1) & (hv(2:end,i:end-lw+i)>=0) & (hv(2:end,i:end-lw+i)~=2);
        end
        % remove any other horizontal word
        possible = possible & hv>=0;

        % place to the most top left possible position
        dist = dist_global - 3*n*price;
        dist(~possible) = 3*n;
        dist(2:2:end,:) = 3*n;
        m = min(min(dist));
        [x,y] = find(dist == m);

        if ~isempty(x) && m<3*n
            placed = 1;
            r = ceil(rand()*length(x));
            board(x(r),y(r):y(r)+lw-1) = word;
            hv(x(r),y(r)) = -2; % starting point of the word
            hv(x(r),y(r)+1:y(r)+lw-2) = -1;
            hv(x(r),y(r)+lw-1) = -3; % end point of the word

            isUnplayed2(mi) = 0;
        else
            placed = 0;
        end

        if mod(mi,2)~=0, board = board'; hv = -hv'; end


        errors = errors + (placed==0);
        if (errors == 20 && run==1)
            result = sum(weights(isUnplayed2));        
            break;
        end
    end
    mi = mi-1;
end
end
result = sum(weights(isUnplayed2));        

end



function [board,success] = solver_volkan(words, weights, n)
% BEWARE! This solver only tries to find a complete solution, and is a huge
% waste of CPU cycles if none exists
%
% HERE IS THE MAIN IDEA: Say a word contains five 'A's, it cannot be put on
% the first row of the crossword if we do not have five other words that
% begin with the letter 'A'. Expand this idea to all rows and the histogram
% of each word, you get yourself a reduced search space.

board=zeros(n);
success = false;

% look for completely solveable with enough words
solvable = all(cellfun('length',words) == n);

% give up while you can
if ~solvable;return;end
 
% remove duplicate words (who put them there anyway?)
w = cell2mat(words');
nw = length(w);
  
% reduce search space
template = sv_reduce();

% get the rows with the least candidates
t_pos = sum(template,1);
[~,id1] = sort(t_pos);

% exit while you can
if prod(t_pos(id1(1:2))) > 5000;return;end

% get two sets of candidates for two different rows
suit1 = find(template(:,id1(1)))';
suit2 = find(template(:,id1(2)))';

% do the work
success = sv_fill();

function template = sv_reduce()
    % returns a logical template which shows which word
    % can be placed on which row
    hist_pos = histc(w,65:90,1);
    template = false(nw,n);
    for ind = 1:nw
        hist_word = histc(w(ind,:),65:90,2)';
        hist_word = repmat(hist_word,[1,n]);
        locate = (hist_pos >= hist_word);
        template(ind,:) = all(locate);
    end
end

function done = sv_fill()
    % Loops through two sets of row candidates, keeps filling as long as
    % there is a single cross match, recursively finishes off if not.
    done = false;
    for line1 = suit1
        if done;break;end
        for line2 = suit2
            if line1 == line2;continue;end
            board(id1(1:2),:) = w([line1 line2],:);
            boardcpy = board;
            while (1)
                [filled,boardcpy] = sv_cross(boardcpy);
                if filled
                    boardcpy = boardcpy';
                    if all(boardcpy(:))
                        %check if valid
                        board = boardcpy;
                        done = true;
                        break
                    end
                else
                    done = false;
                    break;
                end    
            end
            if done;break
            else continue;end
        end
    end
    
    function [filled,outboard] = sv_cross(inboard)
        % Places crossovers if there is a single match, calls recursive
        % solver if not.
        outboard = inboard;
        filled = false;
        idx = all(outboard,2);
        idy = ~all(outboard,1);
        full = outboard(idx,idy);
        %Xfull = repmat(shiftdim(full,-1),[nw 1 1]);
        candi = w(:,idx);
        %Xcandi = repmat(candi,[1 1 sum(idy)]);
        match = bsxfun(@eq,shiftdim(full,-1),candi);
        if isempty(match)
            % nasty situation when the board is filled but we did not check
            % the last placement
            Xboard = repmat(shiftdim(outboard,-1),[nw 1 1]);
            Xword = repmat(w,[1 1 n]);
            match = Xboard == Xword;
            m = squeeze(all(match,2));
            mm = squeeze(any(m,1));
            mmm = all(mm);
            if mmm
                filled = true;
                return;
            else
                return;
            end
        end
        m = squeeze(all(match,2));
        mm = squeeze(any(m,1));
        mmm = all(mm);

        if mmm
            %find and anchor unique columns
            ms = sum(m,1);
            %unify duplicate words
            doubles = ms==2;
            if any(doubles);
                duin = m(:,doubles);
                in_doubles = find(doubles);
                [duinx,~] = find(duin);
                for in = 1:(numel(duinx)/2)
                    first = w(duinx(2*in-1),:);
                    second = w(duinx(2*in),:);
                    if all(first==second)
                        % remove one from template
                        m(duinx(2*in),in_doubles(in)) = 0;
                    end
                end
                ms = sum(m,1);
            end
            uin = ms==1;
            if any(uin) % we have unique columns
                muin = m(:,uin);
                [uinx,~] = find(muin);
                idy(idy) = uin;
                outboard(:,idy) = w(uinx,:)';
                filled = true;
            else
                % start diggin
                % expand m and ms
                tmp = inf(nw,n);
                tmp(:,idy) = m;
                m = tmp;
                ms = sum(m,1);
                [outboard,done] = sv_deeper(outboard);
                %disp('exited sv_deeper');
                filled = done;
            end
        end
        
        function [dboard,done] = sv_deeper(inboard)
            % Recursive solver used to finish off the crossword
            done = false;
            % get one high probability fit from ms
            [~,idm] = sort(ms);
            msin = m(:,idm(1));
            [usn,~] = find(msin);
            % loop candidate words
            % ignore duplicates
            aw = w(usn,:);
            aw = unique(aw,'rows');
            if size(aw,1) ~= size(usn,1)
                usn = usn(1:size(aw,1));
            end
            for i = usn'
                dboard = inboard;
                dboard(:,idm(1)) = w(i,:)';
                dboard = dboard';
                % see if any matching words appeared
                while (1)
                    [filled,dboard] = sv_cross(dboard);
                    if filled
                        dboard = dboard';
                        if all(dboard(:))
                            %check if valid
                            boardcpy = dboard;
                            done = true;
                            break
                        end
                    else
                        done = false;
                        break;
                    end    
                end
                % check and exit
                if done;break
                else continue;end
            end        
        end
    end
end
end