function [s,scr] = solver(puzzle,list)
% SOLUTION = SOLVER(PUZZLE,LIST) Sudoku solver
nrep=16;
rand('state',[0.77601114592464
0.75671015085135
0.13891423188916
0.01121136931657
0.01071178505077
0.54990256096398
0.28554818268869
0.19573981773983
0.72122568175755
0.00408195846844
0.14325970815144
0.13257651501863
0.15647472753324
0.24319656548571
0.38106982191052
0.24137390022582
0.47847267572092
0.62826273604322
0.15256204379493
0.08203456359208
0.08757954755789
0.40937295577739
0.57452680131173
0.15606386764175
0.98264384066366
0.70131571424744
0.92319106863181
0.56761799092455
0.70369897330244
0.03290489147088
0.42634041959398
0.76517064509240
0
0
0.00000000004730]+1e-14*[-0.08881784197001
0.14432899320127
0.04163336342344
0.12958384365547
0.14155343563971
-0.23314683517128
0.23314683517128
-0.03885780586188
-0.33306690738755
-0.03825065264529
0.42743586448069
0.38857805861880
-0.45519144009631
-0.09992007221626
0.11657341758564
0.27200464103316
-0.04440892098501
0.27755575615629
-0.04440892098501
0.39412917374193
-0.14571677198205
0.07216449660064
-0.23314683517128
-0.34972025275692
-0.24424906541753
0.38857805861880
0.07771561172376
0.07771561172376
-0.25535129566379
0.37123082385904
0.31641356201817
0.33306690738755
0
0
-0.09464372895317]);
s=puzzle;
[l j]=sort(rand(size(list)));
l=list(j);
jm=find(~puzzle);
s(jm)=l(1:numel(jm));
l=l((numel(jm)+1):end);
lu=s(jm);
[ix jx]=ind2sub([9 9],jm);
h = reshape(1:9,3,3);
g = ceil((1:9)/3);
h = (h(g,g)-1)*9 + repmat(h,3);
sr=sum(s');
sc=sum(s);
su=sum(s(h));
ju=floor((jx-1)/3)*3+ceil(ix/3);
target=sum(s(:))/9;
jrep=0;flg=1;oscr=inf;
for jrep=1:nrep
flg=0;
for j=1:numel(jm)
er=abs(sr(ix(j))-target)+abs(sc(jx(j))-target)+abs(su(ju(j))-target);
u=l-s(ix(j),jx(j));
[ern jj]=min(abs(sr(ix(j))+8*u/9-target)+abs(sc(jx(j))+8*u/9-target)+abs(su(ju(j))+8*u/9-target));
uu=lu-s(ix(j),jx(j));
eru=abs(sr(ix(j))+uu.*(ix~=ix(j))-target)+abs(sc(jx(j))+uu.*(jx~=jx(j))-target)+abs(su(ju(j))+uu.*(ju~=ju(j))-target)-er;
eru=eru+abs(sr(ix)'-uu.*(ix~=ix(j))-target)+abs(sc(jx)'-uu.*(jx~=jx(j))-target)+abs(su(ju)'-uu.*(ju~=ju(j))-target);
eru=eru-abs(sr(ix)'-target)-abs(sc(jx)'-target)-abs(su(ju)'-target);
[eru jju]=min(eru);
if (ern-er)<eru
if ern<er
flg=1;
dlt=u(jj);
sr(ix(j))=sr(ix(j))+dlt;
sc(jx(j))=sc(jx(j))+dlt;
su(ju(j))=su(ju(j))+dlt;
target=target+dlt/9;
u=l(jj);
l(jj)=s(ix(j),jx(j));
s(ix(j),jx(j))=u;
lu(j)=u;
end
else
if eru<0
flg=1;
dlt=uu(jju);
sr(ix(j))=sr(ix(j))+dlt;
sc(jx(j))=sc(jx(j))+dlt;
su(ju(j))=su(ju(j))+dlt;
sr(ix(jju))=sr(ix(jju))-dlt;
sc(jx(jju))=sc(jx(jju))-dlt;
su(ju(jju))=su(ju(jju))-dlt;
u=lu(jju);
lu(jju)=s(ix(j),jx(j));
s(ix(jju),jx(jju))=s(ix(j),jx(j));
s(ix(j),jx(j))=u;
lu(j)=u;
end
end
end
if ~flg
scr=sum(sum(abs([sr' sc' su']-target)));
if scr<oscr
oscr=scr;
os=s;
end
[eru jq]=max(abs(su-target));
[erc jc]=max(abs(sc-target));%((1:3)+floor(jq/3))-target));
[err jr]=max(abs(sr-target));%(rem(jq,3)*3+(1:3))-target));
j=find(ju==jq);
s(jm(j))=flipud(s(jm(j)));
j=find(jx==jc);
s(jm(j))=flipud(s(jm(j)));
j=find(ix==jr);
s(jm(j))=flipud(s(jm(j)));
lu=s(jm);
sr=sum(s');
sc=sum(s);
su=sum(s(h));
end
end
scr=sum(sum(abs([sr' sc' su']-target)));
if oscr<scr
s=os;
end
|
