fcol_a_05

function finalAnswer = solver(numPegs,numColors,guessLimit,puzzleID)

if guessLimit==1 | numColors==1
	finalAnswer=ones(1,numPegs);
	return
end

if (numColors^numPegs < 5e4) % a sieve for small puzzles
    boards = make(numPegs, numColors);
    nb = size(boards,2);
    nguess = 0;
    sg = 0;
    while (nb > 1) & (nguess <= guessLimit)
        guess = boards(:,ceil(rand * nb));
        [black,white,nguess]=scoreme(guess',puzzleID);
        boards = prune(black, white, guess, boards, numColors);   
        nb = size(boards,2);
    end
    finalAnswer = boards(:,ceil(rand * nb))';
    return
end % ifsmall

[cs,numCallsMade,fr,finalAnswer,lsr]  =  findcols(numPegs,numColors,guessLimit,puzzleID);

if lsr>= numPegs | numCallsMade>= guessLimit | isempty(cs)
    return; 
end

[rows,cols] = size(cs); % to cancel consequentive calls to size().

% for i = 1:size(cs,1)
 for i = 1:rows
    [ind,numCallsMade]  =  ffc(finalAnswer,fr,cs(i,2),cs(i,1),lsr,guessLimit,puzzleID); 
    finalAnswer(fr(ind)) = cs(i,1); 
    fr(ind) = [];
    if numCallsMade >=  guessLimit, 
        for j = i+1:rows
            finalAnswer(fr(1:cs(j,2))) = cs(j,1); 
            fr = fr(cs(j,2)+1:end); 
        end; 
        return; 
    end;
    lsr = lsr + cs(i,2); 
    if lsr >= numPegs, 
        return; 
    end; 
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [ind,numCallsMade] = ffc(gs,x,n,col,b0,gsLim,puzzleID)
if length(x) == n, 
    ind = 1:n; 
    numCallsMade = 0; 
    return; 
end;
if (length(x)<14) & (n~= 1)
    [ind,numCallsMade]  =  ffclp(gs,x,n,col,b0,gsLim,puzzleID);
    return;
end
i = floor(length(x)/2); 
g = gs; 
g(x(1:i)) = col; 
[black,white,numCallsMade]  =  scoreme(g,puzzleID);
nv = n-black+b0;
if black>b0, 
    if numCallsMade>= gsLim, 
        ind = [1:black-b0,(i+1:i+nv)]; 
        return; 
    end;
    [i1,numCallsMade] = ffc(gs,x(1:i),black-b0,col,b0,gsLim,puzzleID);
    if numCallsMade>= gsLim, 
        ind = [i1,(i+1:i+nv)]; 
        return; 
    end
elseif numCallsMade>= gsLim, 
    ind = i+1:i+nv; 
    return;
else
    i1 = [];
end
if nv, 
    [i2,numCallsMade] = ffc(gs,x(i+1:end),nv,col,b0,gsLim,puzzleID); 
    i2 = i2+i;
else
    i2 = []; 
end;

ind = [i1 i2];

function boards = prune(black, white, guess, boards, nc)
nb = size(boards,2); 
boards(:, sum(repmat(guess,1,nb) == boards) ~= black) = [];
nb = size(boards,2);
if nb > 0
    w = sum(min(repmat(histc(guess, 1:nc),1,nb), histc(boards, 1:nc))) ~= (black+white);
    boards(:, w) = [];
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [cols,ng,free,answ,lsure]=findcols(np,ncol,guessLim,ID)
free=1:np;
cols=zeros(ncol,1);
answ=ones(1,np);
tot=0;
k=1;
lsure=0;
l=0;
nulcol=0;
for i=1:ncol-1
	answ(free)=i;
	if l
		answ(free(k))=l;
		[b,w,ng]=scoreme(answ,ID);
		b=b+w-1-lsure;
		if w
			if w>1
				answ(free(k))=i;
				free(k)=[];
				lsure=lsure+1;
				b=b-1;
				tot=tot+1;
			else
				k=k+1;
			end
		else
			free(k)=[];
			cols(l)=cols(l)-1;
			lsure=lsure+1;
		end
		if length(free)<cols(l)+k
			answ(free(k:end))=l;
			lsure=lsure+cols(l);
			cols(l)=0;
			free=free(1:k-1);
		end
		if cols(l)==0
			nulcol=l;
			if any(cols)
				[xx,l]=max(cols);
			else
				l=0;
			end
			k=1;
		end
	else
		[b,w,ng]=scoreme(answ,ID);
		b=b-lsure;
	end
	cols(i)=b;
	tot=tot+b;
	if b
		if l==0
			l=i;
		end
	else
		nulcol=i;
	end
	if ng>=guessLim | tot>=np
		break;
	end
end	% for
cols(ncol)=np-tot;

[i,j,cols]=find(cols);
if isempty(cols)
	lsure=np;	%necessary?
	return
elseif length(cols)==1
	answ(free)=cols;
	lsure=np;
	return
end
cols=[i cols];

if ng>=guessLim
	j=1;
	for i=1:size(cols,1)
		answ(free(j:j+cols(i,2)-1))=cols(i,1);
		j=j+cols(i,2);
	end
	lsure=np;
	return;
end
if nulcol
	answ(free)=nulcol;
else
	[i,r1]=max(cols(2:end,2));
	cols=cols([1 r1+1 2:r1 r1+2:end],:);
	n1=cols(1,2);
	n2=cols(2,2);
	c1=cols(1,1);
	c2=cols(2,1);
	answ(free)=c1;
	while n1&n2
		answ(free(k))=c2;
		[b,w,ng]=scoreme(answ,ID);
		if w
			answ(free(k))=c1;
			if w>1
				free(k)=[];
				n1=n1-1;
				lsure=lsure+1;
			else
				k=k+1;
			end
		else
			free(k)=[];
			n2=n2-1;
			lsure=lsure+1;
		end	% no w
		if ng>=guessLim
			j=n1+n2;
			answ(free(n1+1:n1+n2))=c2;
			for i=3:size(cols,1)
				answ(free(j+1:j+cols(i,2)))=cols(i,1);
				j=j+cols(i,2);
			end
			lsure=np;
			return
		end
	end	% while n1
	if n1
		cols(1,2)=n1;
		cols=cols([1 3:end],:);
		answ(free)=c2;
	elseif n2
		cols=cols(2:end,:);
		cols(1,2)=n2;
	else
		cols=cols(3:end,:);
	end
	if size(cols,1)==1
		answ(free)=cols(1,1);
		lsure=np;
		return
	end
end
[i,j]=sort(-cols(:,2));
cols=cols(j,:);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [ind,numCallsMade] = ffclp(gs,index,n,cl,b0,guessLimit,puzzleID)
persistent guessesCache
numCallsMade = 0;
l = length(index);
oneToL=1:l;
if isempty(guessesCache) | length(guessesCache) < l | isempty(guessesCache{l})
   twoexp = 1;
   guesses = zeros(1, 0);
   for i = oneToL
      guesses = [guesses zeros(twoexp, 1);guesses ones(twoexp, 1)];
      twoexp = twoexp * 2;
   end;
   guessesCache{l} = guesses; 
else
   guesses = guessesCache{l};
end
answers = guesses(sum(guesses,2) == n,:)';
count = 0;
while (size(answers,2)~= 1) & (numCallsMade<guessLimit)
    count = count+1;
    if count == 1
        bestguess = (oneToL)>l/2;
    elseif count == 2
        bestguess = (oneToL <= l/4)+(oneToL > l*0.75);
    else
        [m,bestguessn] = min(sum(histc(guesses*answers,0:n,2).^2,2));
        bestguess = guesses(bestguessn,:);
    end
    g = gs; g(index(find(bestguess))) = cl;
    [black,white,numCallsMade] = scoreme(g,puzzleID);
    answers = answers(:,find(bestguess*answers == black-b0));
end
ind = find(answers(:,1+floor(rand(1)*size(answers,2))))';

function boards = make(np, nc)
if (np <= 1), boards = 1:nc;
else boards = [repmat(make(np-1, nc), 1, nc); reshape(repmat(1:nc, nc^(np-1),1), 1, nc^np)];
end