SHsolver3

function moves = solver(board,nMoves)
%SOLVER Solve the Blockbuster Contest problem
%
% MOVES = SOLVER(BOARD,NMOVES) BlockBuster solver.
%
% MOVES -> [row,column,action]
% action -> 0 busts, 1 swap up, 2 swap right, 3 swap down, 4 swap left

[M,N]=size(board);
M2=M+2;
D=[-1 M2 1 M2];
Di=[3 4 1 2];
A=[zeros(1,N+2);zeros(M,1) board zeros(M,1);zeros(1,N+2)];
iEl=find(A);
b=unique(board(:));
nb=b;
for i=1:length(b)
	nb(i)=sum(board(:)==b(i));
end
nb1=nb==1;
nb(nb1)=[];
if isempty(nb)
	% probably not necessary
	moves=zeros(0,3);
	return
end
b(nb1)=[];
moves=zeros(nMoves,3);
iMoves=0;
bLoop=0;
nblok=zeros(1,max(nb));
iblok=nblok;
MN=numel(A);

if nMoves>2
	single=A(iEl)~=A(iEl+1)&A(iEl)~=A(iEl-1)&A(iEl)~=A(iEl+M2)&A(iEl)~=A(iEl-M2);
	mOK=zeros(MN,5);
	m1OK=false;
	for i=1:length(iEl)
		if single(i)
			mOK1=false;
			l1=iEl(i);
			mOK(l1,5)=-1;
			a=A(l1);
			if A(l1-1)
				if A(l1-1-M2)==a|A(l1-1+M2)==a
					mOK(l1,1)=1;
					mOK1=true;
				end
			end
			if A(l1+M2)
				if A(l1-1+M2)==a|A(l1+1+M2)==a
					mOK(l1,2)=1;
					mOK1=true;
				end
			end
			if A(l1+1)
				if A(l1+1-M2)==a|A(l1+1+M2)==a
					mOK(l1,3)=1;
					mOK1=true;
				end
			end
			if A(l1-M2)
				if A(l1-1-M2)==a|A(l1+1+M2)==a
					mOK(l1,4)=1;
					mOK1=true;
				end
			end
			if mOK1
				m1OK=mOK1;
			else
				single(i)=false;
			end
		end
	end
	if m1OK
		for i=1:length(iEl)
			if single(i)
				l1=iEl(i);
				for j=1:4
					if mOK(l1,j)
						l2=l1+D(j);
						if mOK(l2,5)
							if mOK(l1,Di(j))
								mOK(l1,j)=5;
							else
								mOK(l1,j)=2;	% ??
							end
						% else ...
						end	% single l2
					end % mOK
				end % for j
			end % if single
		end % for
		% ???hoe meerdere combineren
		[mx,imx]=max(mOK(:));
		iMoves=iMoves+1;
		l1=rem(imx,MN);
		c=floor(l1/M2);
		d=ceil(imx/MN);
		moves(iMoves,1)=l1-c*M2-1;
		moves(iMoves,2)=c;
		moves(iMoves,3)=d;
		a=A(l1);
		A(l1)=A(l1+D(d));
		A(l1+D(d))=a;
	end	% no useful single
end

while iMoves<nMoves
	[mx,ib]=max(nb);
	if mx<2
		if bLoop
			bLoop=0;
			mx=0;
			for i=1:length(b)
				nb(i)=sum(board(:)==b(i));
				if mx<nb(i)
					mx=nb(i);
					ib=i;
				end
			end
		else
			break
		end
	end
	%i=find(nb==mx);
	%ib=i(end);
	%ib=i(ceil(rand(1)*length(i)));
	b1=b(ib);
	lijst=find(A==b1);
	ibl=1;
	nbl=0;
	i0=1;
	mx=1;
	while i0<length(lijst)
		[lijst,nI]=contblock(lijst,A,i0,M2);
		nbl=nbl+1;
		n1=nI-i0;
		iblok(nbl)=i0;
		nblok(nbl)=n1;
		i0=nI;
		if n1>mx
			mx=n1;
			i=nbl;
		end
	end
	
	if mx>1
		bLoop=1;
		iMoves=iMoves+1;
		i1=iblok(i);
		i0=lijst(i1);
		c=floor(i0/M2);
		moves(iMoves,1)=i0-c*M2-1;
		moves(iMoves,2)=c;
		moves(iMoves,3)=0;
		A=popblock(A,lijst(i1:i1+mx-1));
		nb(ib)=nb(ib)-mx;
		if nb(ib)<2
			b(ib)=[];
			nb(ib)=[];
		end
	else
		nb(ib)=0;
	end
end
moves = moves(1:iMoves,:);

function [lijst,n]=contblock(lijst,A,i0,M)
n=i0+1;
l1=lijst(i0);
a=A(l1);
A(l1)=0;
N=length(lijst);
while i0<n
	if A(l1+1)==a
		ii=ff(lijst,n,l1+1);
		if ii>n
			lijst(ii)=lijst(n);
			lijst(n)=l1+1;
		end
		A(l1+1)=0;
		n=n+1;
		if n>N
			break;
		end
	end
	if A(l1-1)==a
		ii=ff(lijst,n,l1-1);
		if ii>n
			lijst(ii)=lijst(n);
			lijst(n)=l1-1;
		end
		A(l1-1)=0;
		n=n+1;
		if n>N
			break;
		end
	end
	if A(l1+M)==a
		ii=ff(lijst,n,l1+M);
		if ii>n
			lijst(ii)=lijst(n);
			lijst(n)=l1+M;
		end
		A(l1+M)=0;
		n=n+1;
		if n>N
			break;
		end
	end
	if A(l1-M)==a
		ii=ff(lijst,n,l1-M);
		if ii>n
			lijst(ii)=lijst(n);
			lijst(n)=l1-M;
		end
		A(l1-M)=0;
		n=n+1;
		if n>N
			break;
		end
	end
	i0=i0+1;
	l1=lijst(i0);
end

function A=popblock(A,I)
A(I)=0;
N=size(A,1);
c=unique(ceil(I/N))';
jj=N-1:-1:2;
for ic=c
	i=N;
	for j=jj
		if A(j,ic)
			i=i-1;
			A(i,ic)=A(j,ic);
		end
	end
	while i>1
		i=i-1;
		A(i,ic)=0;
	end
end

function i=ff(L,i,a)
while L(i)~=a
	i=i+1;
end