function [board, orientation] = solver(tiles, boardSize)
ntiles = size(tiles,1);
nrow = boardSize(1);
ncol = boardSize(2);
nElem = nrow*ncol;
board = zeros(boardSize);
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
played = tiles;
numUnplayed = ntiles-nElem;
if numUnplayed>0
sums = sum(tiles,2);
[~,si] = sort(sums);
played(si(1:numUnplayed),:) = Inf(numUnplayed,4);
ntiles=nElem;
height=nrow;
else
height=max(min(ceil(sqrt(ntiles)), nrow),ceil(ntiles/ncol));
end
[y,x]=ind2sub([height,ncol],1:ntiles);
ind = sub2ind(boardSize,y,x);
board(ind) = -1;
last = [y(end),x(end)];
b =cat(3,board,board,board,board,board,board,board, board, board);
o = ones(size(tiles,1), 9);
[b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,played,o(:,1),ntiles, cs,nrow,ncol);
[b(:,:,1),o(:,1),list] = place(height:-1:1,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles, cs,nrow,ncol);
newList(:,:,1) = list;
[b(:,:,5),o(:,5),list] = place(height:-1:1,last(2),b(:,:,5),played,played,o(:,5),ntiles, cs,nrow,ncol);
[b(:,:,5),o(:,5),list] = place(height,1:last(2),b(:,:,5),played,list,o(:,5),ntiles, cs,nrow,ncol);
[b(:,:,5),o(:,5),list] = place(1:height-1,1,b(:,:,5),played,list,o(:,5),ntiles, cs,nrow,ncol);
[b(:,:,5),o(:,5),list] = place(1,2:last(2),b(:,:,5),played,list,o(:,5),ntiles, cs,nrow,ncol);
newList(:,:,2) = list;
for i=[4 0]
[b(:,:,i+2),o(:,i+2),~] = place(2:height-1,2:ncol-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles, cs,nrow,ncol);
[b(:,:,i+3),o(:,i+3),~] = place(height-1:-1:2,2:ncol-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles, cs,nrow,ncol);
[b(:,:,i+4),o(:,i+4),~] = place(2:height-1,ncol-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles, cs,nrow,ncol);
[b(:,:,i+1),o(:,i+1),~] = place(height-1:-1:2,ncol-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles , cs,nrow,ncol);
end
S = 8;
if nElem < 1000
[b(:,:,9),o(:,9)] = MichaelC(height,last(2), tiles, played, o(:,9), ntiles, cs,nrow,ncol);
S = S + 1;
[b(:,:,10 ), o(:,10 )] = picky(tiles, boardSize,nrow,ncol,cs);
[b(:,:,11), o(:,11)] = calibrating_pure(tiles, boardSize,nrow,ncol);
S = S + 2;
if nElem < 200
[b(:,:,12), o(:,12)] = werner(tiles, boardSize,nrow,ncol);
S = S + 1;
end
end
overall = zeros(S,1);
parfor i=1:S
overall(i) = overallScore(b(:,:,i),nrow,ncol,o(:,i),tiles, cs);
end
[~,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);
%disp([' Mejor SOLUCION SOLVER_' num2str(mo) ])
end
function [score] = overallScore(board,nrow,ncol, orientation, tiles, cs)
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)=tiles(board(y,x),cs(orientation(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;
end
function [board, ort, lst] = MichaelC(height, width, tiles, list, orientation, ntiles, cs,nrow,ncol)
all_indices = reshape(1:(height*width),height,width);
center_x = width/2 + 0.5;
center_y = height/2 + 0.5;
cols = ceil(all_indices/height);
rows = mod(all_indices-1,height)+1;
dist_center = sqrt((cols - center_x).^2 + (rows - center_y).^2);
[~, sort_index] = sort(dist_center(:));
loop_order = flipud(sort_index)';
tile_sums = sum(tiles,2);
board = zeros(nrow,ncol);
brd = zeros(height,width)-1;
if ntiles < height*width
loop_order(~ismember(loop_order,1:ntiles)) = [];
brd(ntiles+1:end) = 0;
end
ort = orientation;
lst = list;
L = size(lst,1);
for ii = loop_order
y = rows(ii);
x = cols(ii);
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,height,width);
grid = ones(L,1)*[n e s w];
for i=4:-1:1
score(:,i) = sum(int32(abs(lst(:,cs(:,i))-grid)),2);
end
[ms, t] = min(score);
ms_i = find(ms == min(ms));
if length(ms_i) > 1
rand_i = ceil(rand(1)*length(ms_i));
o = ms_i(rand_i);
else
[~ , o] = min(ms);
end
t = t(o);
ort(t) = o;
brd(y,x)=t;
lst(t,:)=inf(1,4);
end
end
board(1:height,1:width) = brd;
end
function [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles, cs,nrow,ncol)
k = 1;
brd = board;
ort = orientation;
lst = list;
L = size(lst,1);
tile_sums = sum(tiles,2);
for y=rowRange
for x=colRange
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,nrow,ncol);
% [t, o] = findBestTile(lst, L, n, e, s, w, cs);
%
grid = ones(L,1)*[n e s w];
for i=4:-1:1
score(:,i) = sum(int32(abs(lst(:,cs(:,i))-grid)),2);
end
[ms, t] = min(score);
[~ , o] = min(ms);
t = t(o);
ort(t) = o;
brd(y,x)=t;
lst(t,:)=inf(1,4);
k = k + 1;
if (k > ntiles)
return;
end
end
end
end
end
function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col, cs,nrow,ncol)
north = boundary(board, tiles, orientation, row-1,col ,3, cs,nrow,ncol );
south = boundary(board, tiles, orientation, row+1,col ,1, cs,nrow,ncol );
west = boundary(board, tiles, orientation, row ,col-1,2, cs,nrow,ncol );
east = boundary(board, tiles, orientation, row ,col+1,4, cs,nrow,ncol );
end
function value = boundary(board, tiles, orientation, row,col,id, cs,nrow,ncol )
if row<1 || col<1 || row>nrow || col>ncol
value = 0;
else
if board(row,col) == -1
value = nan;
elseif board(row,col) == 0
value = 0;
else
value = tiles(board(row,col),cs(orientation(board(row,col)),id));
end
end
end
function [board, orientation] = picky(tiles, boardSize,nrow,ncol,cs )
nt = size(tiles,1);
board = zeros(boardSize);
nb = nrow*ncol;
orientation = ones(nt,1);
unused = true(1,nt);
rt = zeros(size(tiles,1),4,4);
for i=1:4
rt(:,:,i) = tiles(:,cs(:,i));
end
goalN = nan(boardSize);
goalN(1,:) = 0;
goalS = nan(boardSize);
goalS(end,:) = 0;
goalE = nan(boardSize);
goalE(:,end) = 0;
goalW = nan(boardSize);
goalW(:,1) = 0;
tsum = sum(tiles,2);
% adjust goals
% greedily pick tiles
for i = 1:min(nb,nt)
goal = [goalN(i),goalE(i),goalS(i),goalW(i)];
for j = 4:-1:1
hd = bsxfun(@minus,rt(unused,:,j),goal);
hd(isnan(hd)) = 0;
hs{j} = sum(abs(hd),2);
end;
hsm = cat(2,hs{:});
hsm(hsm~=min(hsm(:))) = inf;
%hsm(hsm~=min(min(hsm))) = inf;
hsm = bsxfun(@minus,hsm,tsum(unused));
%[~,pick] = min(hsm(:));
%[pick,ori] = ind2sub([nt-i+1,4],pick);
[pick,ori] = find(hsm==min(min(hsm)),1,'first');
pick = find(unused,pick);
pick = pick(end);
board(i) = pick;
orientation(pick) = ori;
unused(pick) = false;
% update goals
if (i+nrow <= nb)
goalW(i+nrow) = rt(pick,2,ori);
end;
if (mod(i,nrow) ~= 0)
goalN(i+1) = rt(pick,3,ori);
end;
end;
end
function [board, orientation] = calibrating_pure(tiles, boardSize,nrows,ncols)
board = zeros(boardSize);
orientation = ones(size(tiles,1), 1);
boarde = board;
ntiles = size(tiles, 1);
% [~, tilesperm] = sort(sum(tiles, 2), 'descend');
% tiles = tiles(tilesperm, :);
% Kudos to Martin F. for quadrupling tiles
tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];
tilestaken = false(4*ntiles, 1);
% place initial tile
boarde(nrows,1) = 4;
f = nextfield();
while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,false);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
function ret = nextfield()
[v, ix] = max(boarde(:));
if v; ret = [mod(ix-1,nrows)+1, ceil(ix/nrows)];
% fprintf(' %d %d\n', ret(1), ret(2));
else ret = [];
end
% assert(isempty(ret) || (ret(1) > 0 && ret(1) <= nrows && ret(2) > 0 && ret(2) <= ncols));
end
function placetile(tileix, row, col)
board(row, col) = tileix;
boarde(row, col) = 0;
method4a(tileix, row, col);method4b( row, col);method4c( row, col);
poptile(tileix);
function method4a(tileix, row, col)
% pricy stones + diagonal bonus
if row > 1 && ~board(row-1,col ); boarde(row-1, col ) = boarde(row-1, col ) + tiles(tileix, 1); end;
if row < nrows && ~board(row+1,col ); boarde(row+1, col ) = boarde(row+1, col ) + tiles(tileix, 3); end;
if col > 1 && ~board(row ,col-1); boarde(row , col-1) = boarde(row , col-1) + tiles(tileix, 4); end;
if col < ncols && ~board(row ,col+1); boarde(row , col+1) = boarde(row , col+1) + tiles(tileix, 2); end;
end
function method4b( row, col)
if row > 1 && col > 1 && ~board(row-1,col-1); boarde(row-1, col-1) = boarde(row-1, col-1) + 0.1; end;
if row > 1 && col < ncols && ~board(row-1,col+1); boarde(row-1, col+1) = boarde(row-1, col+1) + 0.1; end;
end
function method4c( row, col)
if row < nrows && col > 1 && ~board(row+1,col-1); boarde(row+1, col-1) = boarde(row+1, col-1) + 0.1; end;
if row < nrows && col < ncols && ~board(row+1,col+1); boarde(row+1, col+1) = boarde(row+1, col+1) + 0.1; end;
end
function poptile(tileix )
ix = mod(tileix-1, ntiles)+1;
o = ceil(tileix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
end
boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
end
function m = mynansum(m, d)
m(isnan(m)) = 0;
m = sum(m, d);
end
function [board orientation] = werner(tiles, boardSize,nrows,ncols)
board = zeros(boardSize);
orientation = ones(size(tiles,1), 1);
ntiles = size(tiles, 1);
tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];
tilestaken = false(4*ntiles, 1);
boarde = board;
boarde(1,1) = 4;
f = nextfield();
while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,true);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
function ret = nextfield()
[v, ix] = max(boarde(:));
if v;ret = ixtorc(ix);else ret = [];end
end
function ret = ixtorc(ix)
ret = [mod(ix-1,nrows)+1, ceil(ix/nrows)];
end
function placetile(tileix, row, col)
board(row, col) = tileix;
boarde(row, col) = 0;
placetile1(tileix, row, col );
placetile2( row, col );
placetile3( row, col );
poptile(tileix );
function placetile1(tileix, row, col )
if row > 1 && ~board(row-1,col ); boarde(row-1, col ) = boarde(row-1, col ) + tiles(tileix, 1); end;
if row < nrows && ~board(row+1,col ); boarde(row+1, col ) = boarde(row+1, col ) + tiles(tileix, 3); end;
if col > 1 && ~board(row ,col-1); boarde(row , col-1) = boarde(row , col-1) + tiles(tileix, 4); end;
if col < ncols && ~board(row ,col+1); boarde(row , col+1) = boarde(row , col+1) + tiles(tileix, 2); end;
end
function placetile2( row, col)
if row > 1 && col > 1 && ~board(row-1,col-1); boarde(row-1, col-1) = boarde(row-1, col-1) + 0.1; end;
if row > 1 && col < ncols && ~board(row-1,col+1); boarde(row-1, col+1) = boarde(row-1, col+1) + 0.1; end;
end
function placetile3( row, col)
if row < nrows && col > 1 && ~board(row+1,col-1); boarde(row+1, col-1) = boarde(row+1, col-1) + 0.1; end;
if row < nrows && col < ncols && ~board(row+1,col+1); boarde(row+1, col+1) = boarde(row+1, col+1) + 0.1; end;
end
function poptile(tileix )
ix = mod(tileix-1, ntiles)+1;
orientation(ix) =ceil(tileix/ntiles);
tilestaken(ix+ntiles*(0:3), :) = true;
end
end
boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
end
function ret = findbesttilefor(r, c,tiles,board,nrows,ncols,tilestaken,flag)
if r > 1;
if board(r-1,c) > 0; nv = tiles(board(r-1,c), 3);
else nv = nan;
end
else nv = 0;
end
if r < nrows;
if board(r+1,c) > 0; sv = tiles(board(r+1,c), 1);
else sv = nan;
end
else sv = 0;
end
if c > 1;
if board(r,c-1) > 0; wv = tiles(board(r,c-1), 2);
else wv = nan;
end
else wv = 0;
end
if c < ncols;
if board(r,c+1) > 0; ev = tiles(board(r,c+1), 4);
else ev = nan;
end
else ev = 0;
end
v = [nv, ev, sv, wv];
if flag
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
tilecosts(tilestaken) = inf;
[~, ret] = min(tilecosts-sum(tiles,2).*1e-6);
else
tilecosts = bsxfun(@minus, tiles, v);
tilecosts = abs(tilecosts);
tilecosts = mynansum(tilecosts, 2);
tilecosts(tilestaken) = inf;
[~, ret] = min(tilecosts - 1e-10*sum(tiles(:, isnan(v)), 2));
end
end
|
