Winner the cyclist (CT 1)

Finish 2005-11-09 09:00:00 UTC

trying_my_luck

by Juan

Status: Passed
Results: 2668.0649
CPU Time: 37.4703
Score: 267.23
Submitted at: 2005-11-09 16:51:30 UTC
Scored at: 2005-11-09 20:33:17 UTC

Current Rank: 1532nd
Based on: just2try_tweak3_diffrnt (diff)

Comments
Juan
09 Nov 2005
(sort of) optimized random seed
Please login or create a profile.
Code
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