SHsolver6

function puzzle = solver(puzzle,list)
% SOLUTION = SOLVER(PUZZLE,LIST) Sudoku solver 

if isempty(list)
	solution=puzzle;
end

bp=puzzle==0;
nq=sum(bp(:));

meanExtra=mean(list);

meanTot=(sum(puzzle(~bp))+nq*meanExtra)/9;

h = reshape(1:9,3,3);
g = ceil((1:9)/3);
h1=reshape(1:81,9,9);
h = (h(g,g)-1)*9 + repmat(h,3);
iX=[h h1 h1'];

global CURgraf
igraf=1&CURgraf;
if igraf
	xlabel(sprintf('expected meanTot : %g (meanExtra : %g)\n',meanTot,meanExtra))
	D=get(gcf,'userdata');
	T=D.T;
end
test=zeros(9,9);
itest=0;

while nq
	X=puzzle(iX);
	bX=X==0;
	
	nb=sum(bX);
		
	nb1=nb;
	nb1(nb1==0)=10;	% don't choose an already full set
	[nmn,imn]=min(nb1);	% !!!!!eerste minimum gebruikt
	imn=find(nb1==nmn);
	bPref=0;
	if length(imn)>1
		I=zeros(nmn,length(imn));
		k=0;
		for i=imn
			k=k+1;
			I(:,k)=iX(bX(:,i),i);
		end
		J=I;
		I=I(:)';
		[nn,ii]=hist(I,unique(I));
		[mx,imx]=max(nn);
		mx=1;	% testtest
		if any(nn<mx)
			ii(nn<mx)=[];
			imn=imn(find(sum(J==ii(1))));	% !!eerste
		end
		if mx>1
			bPref=1;
			iPref=ii;
		end
		sX=sum(X(:,imn))+(9-nmn)*meanExtra;	% ??of huidig gemiddelde??
		[mx,imx]=max(abs(sX-meanTot));
		imn=imn(imx);
	end

	ind=iX(bX(:,imn),imn);
	if bPref
		ind1=intersect(ind,iPref);
		if ~isempty(ind1)
			ind=ind1;
		else
			warning('!!!')
		end
	end
	ind=ind(1);	%!!!!!!!!!!gewoon eerste element gevuld
	target=(meanTot-sum(X(:,imn)))/nmn;
	[mn,kmn]=min(abs(list-target));
	
	[iii,jjj]=ind2sub([9 27],ind);
	%fprintf('element %2d (%8.2g) in %2d (%1d,%1d) (%2d)\n',kmn,list(kmn),ind,jjj,iii,imn)
	if igraf
		set(T(ind),'String',num2str(list(kmn)))
	end
	itest=itest+1;
	test(ind)=itest;

	puzzle(ind)=list(kmn);
	list(kmn)=[];
	nq=nq-1;
end
X=puzzle(iX);

%disp(test)
sX=sum(X);
mX=mean(sX);
dX=sX-mX;

% improving 1
if ~isempty(list)
	iList=find(bp)';
	for iRepeat=1:10
		bVerb=0;
		for i=iList
			x=puzzle(i);
			s=mX-mean(sX(sum(iX==i)>0));
			if s>0
				j=find(list>x&list<=x+s/3);
				% (!!mX zal ook vergroten!!)
				if ~isempty(j)
					[mx,k]=max(list(j));
					testT=struct('p',puzzle,'X',X,'sX',sX,'mX',mX,'list',list);
					j=j(k);
					puzzle(i)=list(j);
					X(iX==i)=list(j);
					list(j)=x;
					test=mean(abs(sX-mX));
					sX=sum(X);
					mX=mean(sX);
					%fprintf('%2d<->%2d %10g ---> %10g (%10g)\n',i,j,test,mean(abs(sX-mX)),test-mean(abs(sX-mX)))
					if test<mean(abs(sX-mX))
						%warning('!!!verslechterd!!!')
						puzzle=testT.p;
						X=testT.X;
						sX=testT.sX;
						mX=testT.mX;
						list=testT.list;
					else
						bVerb=1;
					end
				end
			else	% s<0
				j=find(list<x&list>=x+s/3);
				% (!!mX zal ook vergroten!!)
				if ~isempty(j)
					[mx,k]=min(list(j));
					testT=struct('p',puzzle,'X',X,'sX',sX,'mX',mX,'list',list);
					j=j(k);
					puzzle(i)=list(j);
					X(iX==i)=list(j);
					list(j)=x;
					test=mean(abs(sX-mX));
					sX=sum(X);
					mX=mean(sX);
					%fprintf('%2d<->%2d %10g ---> %10g (%10g)\n',i,j,test,mean(abs(sX-mX)),test-mean(abs(sX-mX)))
					if test<mean(abs(sX-mX))
						%warning('!!!verslechterd!!!')
						puzzle=testT.p;
						X=testT.X;
						sX=testT.sX;
						mX=testT.mX;
						list=testT.list;
					else
						bVerb=1;
					end
				end
			end
		end
		if ~bVerb
			break;
		end
	end
end