function [board orientation score] = solver(tiles, boardSize)
ntiles = size(tiles, 1);
nrows = boardSize(1);
ncols = boardSize(2);
nfields = nrows * ncols;
maxroute=min(ntiles,nfields);
%routes{1}=[];
%routesrc{1}=[];
cropable=false;
if ntiles<nfields
cropable=true;
rectangles=[repmat(1:nrows,1,ncols);repmat(1:ncols,1,nrows)];
rectangles_area = prod(rectangles);
rectangles_area(rectangles_area<ntiles)=inf;
[a b] = min(rectangles_area-ntiles+2*sum(rectangles));
cropsize=rectangles(:,b)';
cnrows=cropsize(1);
cncols=cropsize(2);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%snake:
route = nan(boardSize);
route(1:maxroute)=1:maxroute;
routes{1}=route;
routesname{1}='snake';
if cropable
route = nan(boardSize);
croproute = nan(cropsize);
croproute(1:maxroute)=1:maxroute;
route(1:cnrows,1:cncols)=croproute;
routes{end+1}=route;
routesname{end+1}='snake crop';
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%fill diag:
route = nan(boardSize);
helpmat = repmat(1:ncols,nrows,1)+repmat((1:nrows)',1,ncols);
[a b] =sort(helpmat(:));
route(b(1:maxroute))=1:maxroute;
routes{end+1}=route;
routesname{end+1}='diag';
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spiral 1 inner to outer:
route = spiralix(boardSize);
route(route>maxroute)=nan;
routes{end+1}=route;
routesname{end+1}='spiral 1 inner to outer';
%
%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spiral 2 inner to outer:
route = spiralix2(boardSize);
route(route>maxroute)=nan;
routes{end+1}=route;
routesname{end+1}='spiral 2 inner to outer';
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spiral 1 outer to inner:
route = spiralix(boardSize);
route = -route + nfields + 1;
route(route>maxroute)=nan;
routes{end+1}=route;
routesname{end+1}='spiral 1 outer to inner';
%
%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%spiral 2 outer to inner:
route = spiralix2(boardSize);
route = -route + nfields + 1;
route(route>maxroute)=nan;
routes{end+1}=route;
routesname{end+1}='spiral 2 outer to inner';
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%corner and edge:
if nrows > 1 & ncols > 1
for i=1:numel(routes)
route = routes{i};
edgelen=2*nrows+2*ncols-4;
route = route+edgelen;
helpmat = repmat(1:ncols,nrows,1)+repmat((1:nrows)',1,ncols);
helpmat(2:end-1,2:end-1)=nan;
[a b] =sort(helpmat(:));
route(b(1:edgelen))=(1:edgelen)+4;
route(1,1) = 1;
route(1,end)=2;
route(end,1)=3;
route(end,end)=4;
[a b] =sort(route(:));
route(b(1:maxroute))=1:maxroute;
routes{end+1}=route;
routesname{end+1}=[routesname{i} '+ edge'];
end
end
%route
%route(1:maxroute)=1:maxroute;
%routes{1}=route;
%end
%if cropable
% route = nan(boardSize);
% croproute = nan(cropsize);
% croproute(1:maxroute)=1:maxroute;
% route(1:cnrows,1:cncols)=croproute;
% routes{end+1}=route;
%end
for i=1:numel(routes)
route=routes{i};
[~,ind]=sort(route(:));
[r c] = ind2sub(boardSize,ind(1:maxroute));
routesrc{i}=[r c];
end
% visualizeroutes(routes)
%
% if ntiles<nrows*ncols
% rectangles=[repmat(1:nrows,1,ncols);repmat(1:ncols,1,nrows)];
% rectangles_area = prod(rectangles);
% rectangles_area(rectangles_area<ntiles)=inf;
% [a b] = min(rectangles_area-ntiles+2*sum(rectangles));
%
% cropsize=rectangles(:,b)';
% cnrows=cropsize(1);
% cncols=cropsize(2);
% end
%
%
% m_route=1;
%
%
% nfields = nrows * ncols;
% % tiles = [tiles; zeros(nfields-ntiles, 4)];
% rv = (1:boardSize(1))';
% cv = (1:boardSize(2))';
%
% switch m_route;
% case 1; % corners...edges...mid
% route = [1,1];
% if cnrows > 1; route = [route; nrows, 1]; end;
% if cncols > 1; route = [route; 1, ncols]; end;
% if cnrows > 1 && ncols > 1; route = [route; nrows, ncols]; end;
% if cncols > 2;
% route = [route; ones(cncols-2, 1), cv(2:end-1, 1)];
% if cnrows > 1; route = [route; nrows * ones(ncols-2, 1),cv(2:end-1, 1)]; end
% end
% if nrows > 2;
% route = [route; rv(2:end-1, 1), ones(nrows-2, 1)];
% if ncols > 1; route = [route; rv(2:end-1, 1), ncols * ones(nrows-2, 1)]; end
% end
% if nrows > 2 && ncols > 2;
% aidr = rv(2:end-1, ones(1, boardSize(2)-2));
%
% aidc = cv(2:end-1, ones(1, boardSize(1)-2))';
% route = [route; aidr(:), aidc(:)];
% end
% case 2; % column by column
% aidr = rv(:, ones(1, boardSize(2)));
% aidc = cv(:, ones(1, boardSize(1)))';
% route = [aidr(:), aidc(:)];
% case 3; % column by column
% aidr = rv(:, ones(1, boardSize(2)))';
% aidc = cv(:, ones(1, boardSize(1)));
% route = [aidr(:), aidc(:)];
% case 4;
% route = zeros(0,2);
% for i = 1:nrows+ncols-1;
% route = [route; (i:-1:1)', (1:i)'];
% end
% route = route(route(:,1) <= nrows & route(:,2) <= ncols, :);
%
% otherwise;
% assert(false, 'r0ldrlcpmwhib2gfmhuwz72tjfdt30zokmo33vh9');
% end
%
%
%
% route=route(1:min(ntiles,nrows*ncols),:);
nroutes = numel(routesrc);
for j = 1:4
for i=1:nroutes
[b o] = solver_quick(tiles, boardSize, routesrc{i});
s = overallScore(b,o,tiles);
bcell{i} = b;
ocell{i} = o;
svec(i) = s;
end
end
svec';
[trash,mo] = min(svec(:));
%board = b(:,:,mo);
%orientation = o(:,mo);
routesname{mo}
[board,orientation]=localopt(bcell{mo}, ocell{mo},tiles);
%board = bcell{mo};
%orientation = ocell{mo};
% [board orientation] = solver_quick(tiles, boardSize, routesrc{end});
% [board,orientation] = localopt(board, orientation,tiles);
end
function score = overallScore(board, orientation, tiles)
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
[nrow ncol] = size(board);
tile = zeros(nrow*4,ncol);
tmp = tiles.';
for y = 1:nrow
for x = 1:ncol
if board(y,x)
tile((y-1)*4+1:y*4,x)=tmp(cs(orientation(board(y,x)),:),board(y,x));
end
end
end
%internal = sum(sum(abs(tile(5:4:end,1:end)-tile(3:4:end-4,1:end))))+sum(sum(abs(tile(2:4:end,1:end-1)-tile(4:4:end,2:end))));
%external = sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+sum(tile(1,1:end));
out_tiles = 1:size(tiles,1);
in_tiles = board(board>0);
out_tiles(in_tiles) = [];
%notplayed = sum(sum(tiles(out_tiles,:)));
%score = internal + external + notplayed;
score = sum(sum(abs(tile(5:4:end,1:end)-tile(3:4:end-4,1:end))))+ ...
sum(sum(abs(tile(2:4:end,1:end-1)-tile(4:4:end,2:end))))+ ...
sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+ ...
sum(tile(1,1:end))+sum(sum(tiles(out_tiles,:)));
end
function [board orientation score] = solver_quick(tiles, boardSize, route)
board = zeros(boardSize);
orientation = ones(size(tiles,1), 1);
score = sum(tiles(:));
nrows = boardSize(1);
ncols = boardSize(2);
ntiles = size(tiles, 1);
tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];
tiles_sum = sum(tiles,2);
env = nan(nrows+2,ncols+2);
eev = nan(nrows+2,ncols+2);
esv = nan(nrows+2,ncols+2);
ewv = nan(nrows+2,ncols+2);
env(2,:) = 0;
eev(:,end-1) = 0;
esv(end-1,:) = 0;
ewv(:,2) = 0;
mask2=ntiles*(0:3);
for i=1:numel(route)/2
r=route(i,1);
c=route(i,2);
v=[env(r+1,c+1) eev(r+1,c+1) esv(r+1,c+1) ewv(r+1,c+1)];
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
[~, tileix] = min(tilecosts-(tiles_sum).*1e-6);
board(r,c) = tileix;
env(r+2,c+1) = tiles(tileix,3);
eev(r+1,c) = tiles(tileix,4);
esv(r,c+1) = tiles(tileix,1);
ewv(r+1,c+2) = tiles(tileix,2);
ix = mod(tileix-1, ntiles)+1;
o = ceil(tileix/ntiles);
orientation(ix) = o;
tiles(ix,:) = nan;
tiles(ix+mask2(2),:) = nan;
tiles(ix+mask2(3),:) = nan;
tiles(ix+mask2(4),:) = nan;
end
board(board ~= 0) = mod(board(board ~= 0)-1, ntiles)+1;
end
function [board,orientation,gain]=localopt(board, orientation,tiles)
gain=0;
cs = [1 2 3 4;2 3 4 1;3 4 1 2;4 1 2 3];
[r,c]=size(board);
n = size(tiles,1);
didx = [3;4;1;2];
uidx = [1;2;3;4];
lidx = [4;1;2;3];
ridx = [2;3;4;1];
bp = board>0;
bt = board(bp);
te = [zeros(1,4);tiles];
oe = [1;orientation];
ub = [zeros(1,c);board(1:end-1,:)];
db = [board(2:end,:);zeros(1,c)];
lb = [zeros(r,1) board(:,1:end-1)];
rb = [board(:,2:end) zeros(r,1)];
ut = ub(bp)+1;
dt = db(bp)+1;
lt = lb(bp)+1;
rt = rb(bp)+1;
uv = te(ut(:)+(didx(oe(ut))-1)*(n+1));
dv = te(dt(:)+(uidx(oe(dt))-1)*(n+1));
lv = te(lt(:)+(ridx(oe(lt))-1)*(n+1));
rv = te(rt(:)+(lidx(oe(rt))-1)*(n+1));
bt=bt(:);
bv = tiles(bt(:,ones(1,4))+(cs(orientation(bt),:)-1)*n);
% bv = tiles(bt,:);
nv = [uv rv dv lv];
pv = sum(abs(bv-nv),2);
[mpv,id]=max(pv);
while mpv
bid=bt(id);
bid1=bid+1;
pv(id)=0;
obid = orientation(bid);
bx = tiles(bid,:);
p0 = sum(abs(bx(cs)-nv(id+zeros(4,1),:)),2);
[pmin,ido]=min(p0);
gain=gain+(p0(obid)-pmin);
if p0(obid)>pmin
bv(id,:)=bx(cs(ido,:));
orientation(bid)=ido;
oe(bid1)=ido;
u1=ut==bid1;
d1=dt==bid1;
l1=lt==bid1;
r1=rt==bid1;
uv(u1)=tiles(bid,didx(ido));
nv(u1,1)=uv(u1);
dv(d1)=tiles(bid,uidx(ido));
nv(d1,3)=dv(d1);
lv(l1)=tiles(bid,ridx(ido));
nv(l1,4)=lv(l1);
rv(r1)=tiles(bid,lidx(ido));
nv(r1,2)=rv(r1);
L=u1|d1|l1|r1;
pv(L) = sum(abs(bv(L,:)-nv(L,:)),2);
end
[mpv,id]=max(pv);
end
pv = sum(abs(bv-nv),2);
[mpv,id]=max(pv);
N=numel(pv);
tv = tiles(bt,:);
k=0;
while mpv>0
bid = bt(id);
bid1=bid+1;
nvid = zeros(1,16);
nvid(:) = nv(id+zeros(4,1),:);
u1=ut==bid1;
d1=dt==bid1;
l1=lt==bid1;
r1=rt==bid1;
L=~(u1|d1|l1|r1);
L(id)=false;
qv = Inf(N,4);
qv(L,:) = reshape(sum(reshape(abs(tv(L,cs)-nvid(ones(sum(L),1),:)),[],4),2),[],4);
[iv,to] = min(qv(:));
jd = mod(to-1,N)+1;
bjd = bt(jd);
bjd1=bjd+1;
% objd = orientation(bjd);
jo = ceil(to/N);
nvjd = nv(jd+zeros(4,1),:);
bvid = zeros(4);
bvid(:) = tiles(bid,cs);
[jv,io]=min(sum(abs(bvid - nvjd),2));
jpv = sum(abs(bv(jd,:) - nv(jd,:)));
if iv+jv < mpv+jpv
bt(jd) = bid;
bt(id) = bjd;
orientation(bid) = io;
orientation(bjd) = jo;
board(bp)=bt;
bv(id,:) = tv(jd,cs(jo,:));
bv(jd,:) = tv(id,cs(io,:));
bx = tv(id,:);
tv(id,:) = tv(jd,:);
tv(jd,:) = bx;
uv(u1)=tiles(bjd,didx(jo));
nv(u1,1)=uv(u1);
dv(d1)=tiles(bjd,uidx(jo));
nv(d1,3)=dv(d1);
lv(l1)=tiles(bjd,ridx(jo));
nv(l1,4)=lv(l1);
rv(r1)=tiles(bjd,lidx(jo));
nv(r1,2)=rv(r1);
u2=ut==bjd1;
d2=dt==bjd1;
l2=lt==bjd1;
r2=rt==bjd1;
uv(u2)=tiles(bid,didx(io));
nv(u2,1)=uv(u2);
dv(d2)=tiles(bid,uidx(io));
nv(d2,3)=dv(d2);
lv(l2)=tiles(bid,ridx(io));
nv(l2,4)=lv(l2);
rv(r2)=tiles(bid,lidx(io));
nv(r2,2)=rv(r2);
L=u1|d1|l1|r1|u2|d2|l2|r2;
pv(L) = sum(abs(bv(L,:)-nv(L,:)),2);
uid = ut==bid1;
ujd = ut==bjd1;
ut(uid) = bjd1;
ut(ujd) = bid1;
did = dt==bid1;
djd = dt==bjd1;
dt(did) = bjd1;
dt(djd) = bid1;
lid = lt==bid1;
ljd = lt==bjd1;
lt(lid) = bjd1;
lt(ljd) = bid1;
rid = rt==bid1;
rjd = rt==bjd1;
rt(rid) = bjd1;
rt(rjd) = bid1;
k=k+1;
end
pv(id)=0;
pv(jd)=0;
[mpv,id]=max(pv);
end
end
function visualizeroutes(routes)
figure
for i=1:numel(routes)
imagesc(routes{i});
pause(3)
end
end
function ix = spiralix(boardsize)
ix = nan(boardsize);
dir = [1 0];
pos = [1 1];
x=prod(boardsize);
while sum(sum(isnan(ix)))>0
if any(pos<1) || any(boardsize-pos<0) || ~isnan(ix(pos(1),pos(2)))
pos=pos-dir;
dir=spiralnextdir(dir);
pos=pos+dir;
end
if ~any(pos<0) && ~any(boardsize-pos<0) && isnan(ix(pos(1),pos(2)))
ix(pos(1),pos(2))=x;
x=x-1;
pos=pos+dir;
end
end
end
function direction = spiralnextdir(direction)
if direction ==[1 0],direction=[0 1];return;end
if direction ==[0 1],direction=[-1 0];return;end
if direction ==[-1 0],direction=[0 -1];return;end
if direction ==[0 -1],direction=[1 0];return;end
end
function ix = spiralix2(boardsize)
bsr = boardsize(1);
bsc = boardsize(2);
maxbs = max(boardsize);
ix_big = spiralix([maxbs maxbs]);
ix1 = ix_big((1:bsr)+round((maxbs-bsr)./2),(1:bsc)+round((maxbs-bsc)./2));
[a b] = sort(ix1(:));
ix=ix1;
ix(b)=1:numel(b);
end
|
