function [board, orientation] = solver(tiles, boardSize)
orientation = ones(size(tiles,1), 1);
ntiles = size(tiles,1);
nElem = boardSize(1)*boardSize(2);
board = zeros(boardSize);
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
played = discardUnplayed(ntiles-nElem, tiles);
if (ntiles-nElem<0)
height=min([ceil(sqrt(ntiles)) boardSize(1)]);
if (ntiles/boardSize(2))>height
height=ceil(ntiles/boardSize(2));
end
else
ntiles=nElem;
height=boardSize(1);
end
for k=1:ntiles
[y,x]=ind2sub([height,boardSize(2)],k);
board(y,x)=-1;
end
last = [y,x];
for i=8:-1:1
b(:,:,i) = board;
o(:,i) = orientation;
end
list = played;
[b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,list,o(:,1),ntiles,boardSize, cs);
[b(:,:,1),o(:,1),list] = place(height:-1:1,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles,boardSize, cs);
newList(:,:,1) = list;
list = played;
[b(:,:,5),o(:,5),list] = place(height:-1:1,last(2),b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(height,1:last(2),b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(1:height,1,b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(1,1:last(2),b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
newList(:,:,2) = list;
for i=[4 0]
[b(:,:,i+2),o(:,i+2),list] = place(2:height-1,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
[b(:,:,i+3),o(:,i+3),list] = place(height-1:-1:2,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
[b(:,:,i+4),o(:,i+4),list] = place(2:height-1,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
[b(:,:,i+1),o(:,i+1),list] = place(height-1:-1:2,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
end
S = 8;
if prod(boardSize) < 1000
[b(:,:,9 ), o(:,9 )] = picky(tiles, boardSize);
[b(:,:,10), o(:,10)] = calibrating_pure(tiles, boardSize);
[b(:,:,11), o(:,11)] = werner(tiles, boardSize);
S = S + 3;
end
overall = zeros(S,1);
for i=1:S
overall(i) = overallScore(b(:,:,i),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, orientation, tiles, cs)
boardSize=size(board);
tile = zeros(boardSize(1)*4,boardSize(2));
tmp = tiles.';
for y = 1:boardSize(1)
for x = 1:boardSize(2)
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 [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles, boardSize, cs)
k = 1;
brd = board;
ort = orientation;
lst = list;
L = size(lst,1);
for y=rowRange
for x=colRange
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, boardSize, cs);
[t, o] = findBestTile(lst, L, n, e, s, w, cs);
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 tiles = discardUnplayed(numUnplayed, tiles)
if numUnplayed>0
sums = sum(tiles,2);
for i = 1:numUnplayed
[~, m]=min(sums);
tiles(m,:)=inf(1,4);
sums(m)=inf;
end
end
end
function [tile, orientation] = findBestTile(list, L, north, east, south, west, cs)
score = int32(zeros(L,4));
grid = ones(L,1)*[north east south west];
for i=1:4
score(:,i) = sum(int32(abs(list(:,cs(:,i))-grid)),2);
end
[ms, t ] = min(score);
[~ , orientation] = min(ms);
tile = t(orientation);
end
function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col, boardSize, cs)
north = boundary(board,tiles,orientation,row-1,col ,3, boardSize, cs);
south = boundary(board,tiles,orientation,row+1,col ,1, boardSize, cs);
west = boundary(board,tiles,orientation,row ,col-1,2, boardSize, cs);
east = boundary(board,tiles,orientation,row ,col+1,4, boardSize, cs);
end
function value = boundary(board,tiles,orientation,row,col,id,boardSize,cs)
if row<1 || col<1 || row>boardSize(1) || col>boardSize(2)
value = 0;
else
if board(row,col) == -1
value = nan;
elseif board(row,col) == 0
value = 0;
else
tile = tiles(board(row,col),cs(orientation(board(row,col)),:));
value = tile(id);
end
end
end
function [board, orientation] = picky(tiles, boardSize)
nt = size(tiles,1);
board = zeros(boardSize);
nrow = boardSize(1);
ncol = boardSize(2);
nb = nrow*ncol;
orientation = ones(nt,1);
unused = true(1,nt);
rt{4} = circshift(tiles,[0 1]);
rt{3} = circshift(tiles,[0 2]);
rt{2} = circshift(tiles,[0 3]);
rt{1} = tiles;
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{j}(unused,:),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{ori}(pick,2);
end;
if (mod(i,nrow) ~= 0)
goalN(i+1) = rt{ori}(pick,3);
end;
end;
end
function [board, orientation] = solver(tiles, boardSize)
orientation = ones(size(tiles,1), 1);
ntiles = size(tiles,1);
nElem = boardSize(1)*boardSize(2);
board = zeros(boardSize);
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
played = discardUnplayed(ntiles-nElem, tiles);
if (ntiles-nElem<0)
height=min([ceil(sqrt(ntiles)) boardSize(1)]);
if (ntiles/boardSize(2))>height
height=ceil(ntiles/boardSize(2));
end
else
ntiles=nElem;
height=boardSize(1);
end
for k=1:ntiles
[y,x]=ind2sub([height,boardSize(2)],k);
board(y,x)=-1;
end
last = [y,x];
for i=8:-1:1
b(:,:,i) = board;
o(:,i) = orientation;
end
list = played;
[b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,list,o(:,1),ntiles,boardSize, cs);
[b(:,:,1),o(:,1),list] = place(height:-1:1,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles,boardSize, cs);
newList(:,:,1) = list;
list = played;
[b(:,:,5),o(:,5),list] = place(height:-1:1,last(2),b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(height,1:last(2),b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(1:height,1,b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(1,1:last(2),b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
newList(:,:,2) = list;
for i=[4 0]
[b(:,:,i+2),o(:,i+2),list] = place(2:height-1,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
[b(:,:,i+3),o(:,i+3),list] = place(height-1:-1:2,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
[b(:,:,i+4),o(:,i+4),list] = place(2:height-1,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
[b(:,:,i+1),o(:,i+1),list] = place(height-1:-1:2,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs);
end
[b(:,:,9 ), o(:,9 )] = picky(tiles, boardSize);
[b(:,:,10), o(:,10)] = calibrating_pure(tiles, boardSize);
overall = zeros(10,1);
for i=1:10
overall(i) = overallScore(b(:,:,i),o(:,i),tiles, cs);
end
[~,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);
%disp([' Mejor SOLUCION SOLVER_' num2str(mo) '. diff9 = ' num2str(num2str(overall(9) - overall(mo),'%d '))])
end
function [score] = overallScore(board, orientation, tiles, cs)
boardSize=size(board);
tile = zeros(boardSize(1)*4,boardSize(2));
tmp = tiles.';
for y = 1:boardSize(1)
for x = 1:boardSize(2)
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 [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles, boardSize, cs)
k = 1;
brd = board;
ort = orientation;
lst = list;
L = size(lst,1);
for y=rowRange
for x=colRange
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, boardSize, cs);
[t, o] = findBestTile(lst, L, n, e, s, w, cs);
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 tiles = discardUnplayed(numUnplayed, tiles)
if numUnplayed>0
sums = sum(tiles,2);
for i = 1:numUnplayed
[~, m]=min(sums);
tiles(m,:)=inf(1,4);
sums(m)=inf;
end
end
end
function [tile, orientation] = findBestTile(list, L, north, east, south, west, cs)
score = int32(zeros(L,4));
grid = ones(L,1)*[north east south west];
for i=1:4
score(:,i) = sum(int32(abs(list(:,cs(:,i))-grid)),2);
end
[ms, t ] = min(score);
[~ , orientation] = min(ms);
tile = t(orientation);
end
function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col, boardSize, cs)
north = boundary(board,tiles,orientation,row-1,col ,3, boardSize, cs);
south = boundary(board,tiles,orientation,row+1,col ,1, boardSize, cs);
west = boundary(board,tiles,orientation,row ,col-1,2, boardSize, cs);
east = boundary(board,tiles,orientation,row ,col+1,4, boardSize, cs);
end
function value = boundary(board,tiles,orientation,row,col,id,boardSize,cs)
if row<1 || col<1 || row>boardSize(1) || col>boardSize(2)
value = 0;
else
if board(row,col) == -1
value = nan;
elseif board(row,col) == 0
value = 0;
else
tile = tiles(board(row,col),cs(orientation(board(row,col)),:));
value = tile(id);
end
end
end
function [board, orientation] = picky(tiles, boardSize)
nt = size(tiles,1);
board = zeros(boardSize);
nrow = boardSize(1);
ncol = boardSize(2);
nb = nrow*ncol;
orientation = ones(nt,1);
unused = true(1,nt);
rt{4} = circshift(tiles,[0 1]);
rt{3} = circshift(tiles,[0 2]);
rt{2} = circshift(tiles,[0 3]);
rt{1} = tiles;
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{j}(unused,:),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{ori}(pick,2);
end;
if (mod(i,nrow) ~= 0)
goalN(i+1) = rt{ori}(pick,3);
end;
end;
end
function [board, orientation] = calibrating_pure(tiles, boardSize)
ntiles = size(tiles, 1);
nfields = prod(boardSize);
methods = [1,2,4,5];
methods = [methods + 20, methods + 30, methods + 10, methods];
% methods = [methods, 44];
% methods = [methods + 10, methods];
% if ntiles >= nfields * 0.8;
% methods = [methods + 30, methods + 20, methods + 10, methods];
% else
% methods = [methods + 20, methods + 10, methods];
% end
% methods = 2;
methods = 24;
nmethods = numel(methods);
scores = inf(nmethods, 1);
results = cell(nmethods, 2);
for i = 1:nmethods;
method = methods(i);
[b,o,s] = mysolver(tiles, boardSize, method);
if s < 100;
% bail out
board = b;
orientation = o;
return;
end
scores(i) = s;
results{i, 1} = b;
results{i, 2} = o;
end
[bestscore, pick] = min(scores);
board = results{pick, 1};
orientation = results{pick, 2};
end
function [board, orientation, score] = mysolver(tiles, boardSize, pmethod)
board = zeros(boardSize);
orientation = ones(size(tiles,1), 1);
boarde = board;
score = sum(tiles(:));
nrows = boardSize(1);
ncols = boardSize(2);
start = floor(pmethod / 10);
method = mod(pmethod, 10);
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])];
tilesvalues = sum(tiles, 2);
tilestaken = false(4*ntiles, 1);
% place initial tile
if start == 0;
midrow = round(nrows./2);
midcol = round(ncols./2);
tileix = maxtile();
placetile(tileix, midrow, midcol);
elseif start == 1;
% Again, Kudos to Martin F. for halving my score with this single loc.
boarde(1,1) = 4;
elseif start == 2;
boarde(nrows,1) = 4;
% boarde( 1 , 1 ) = 2;
% boarde( 1 ,ncols) = 2;
% boarde(nrows, 1 ) = 2;
% boarde(nrows,ncols) = 2;
elseif start == 3;
boarde( 1 , : ) = 3e10;
boarde(nrows, : ) = 3e10;
boarde( : , 1 ) = 3e10;
boarde( : ,ncols) = 3e10;
boarde( 1 , 1 ) = 6e10;
boarde( 1 ,ncols) = 6e10;
boarde(nrows, 1 ) = 6e10;
boarde(nrows,ncols) = 6e10;
% elseif start == 4;
% boarde( 1 , : ) = 3e10;
% boarde(nrows, : ) = 3e10;
% boarde( : , 1 ) = 3e10;
% boarde( : ,ncols) = 3e10;
% boarde( 1 , 1 ) = 6e10;
% boarde( 1 ,ncols) = 6e10;
% boarde(nrows, 1 ) = 6e10;
% boarde(nrows,ncols) = 6e10;
end
f = nextfield();
while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
function ret = findbesttilefor(r, c)
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];
tilecosts = bsxfun(@minus, tiles, v);
tilecosts = abs(tilecosts);
tilecosts = mynansum(tilecosts, 2);
tilecosts(tilestaken) = inf;
[newerror, ret] = min(tilecosts - 1e-10*sum(tiles(:, isnan(v)), 2));
newerror = ceil(newerror);
score = score - sum(tiles(ret, ~isnan(v))) - mynansum(v, 2) + newerror;
end
function ret = maxtile()
[~, ret] = max(tilesvalues(~tilestaken));
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;
switch method
case 1; method1();
case 2; method2a();method2b();method2c();
case 3; method3();
case 4; method4a();method4b();method4c();
case 5; method5a();method5b();method5c();
end
poptile(tileix);
function method1()
% plain cross
if row > 1 && ~board(row-1,col ); boarde(row-1, col ) = boarde(row-1, col ) + 1; end;
if row < nrows && ~board(row+1,col ); boarde(row+1, col ) = boarde(row+1, col ) + 1; end;
if col > 1 && ~board(row ,col-1); boarde(row , col-1) = boarde(row , col-1) + 1; end;
if col < ncols && ~board(row ,col+1); boarde(row , col+1) = boarde(row , col+1) + 1; end;
% assert(all(boarde(:)<=4));
end
function method2a()
% count neighboring stones + diagonal bonus
if row > 1 && ~board(row-1,col ); boarde(row-1, col ) = boarde(row-1, col ) + 1; end;
if row < nrows && ~board(row+1,col ); boarde(row+1, col ) = boarde(row+1, col ) + 1; end;
if col > 1 && ~board(row ,col-1); boarde(row , col-1) = boarde(row , col-1) + 1; end;
if col < ncols && ~board(row ,col+1); boarde(row , col+1) = boarde(row , col+1) + 1; end;
end
function method2b()
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 method2c()
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 method3()
% pricy stones
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 method4a()
% 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()
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()
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 method5a()
% 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 method5b()
if row > 1 && col > 1 && ~board(row-1,col-1); boarde(row-1, col-1) = boarde(row-1, col-1) + 2; end;
if row > 1 && col < ncols && ~board(row-1,col+1); boarde(row-1, col+1) = boarde(row-1, col+1) + 2; end;
end
function method5c()
if row < nrows && col > 1 && ~board(row+1,col-1); boarde(row+1, col-1) = boarde(row+1, col-1) + 2; end;
if row < nrows && col < ncols && ~board(row+1,col+1); boarde(row+1, col+1) = boarde(row+1, col+1) + 2; end;
end
end
function poptile(pix)
ix = mod(pix-1, ntiles)+1;
o = ceil(pix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
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, score] = werner(tiles, boardSize)
nmethods = 2;
results = cell(nmethods, 3);
i=1;
[results{i,1} results{i,2} results{i,3}] = solver12a(tiles, boardSize);if results{i,3}<1,board = results{i, 1}; orientation = results{i, 2}; score = results{i, 3};return,end
i=2;
[results{i,1} results{i,2} results{i,3}] = solver13a(tiles, boardSize);if results{i,3}<1,board = results{i, 1}; orientation = results{i, 2}; score = results{i, 3};return,end
%i=3;
%[results{i,1} results{i,2} results{i,3}] = solver14(tiles, boardSize);if results{i,3}<1,board = results{i, 1}; orientation = results{i, 2}; score = results{i, 3};return,end
%i=4;
%[results{i,1} results{i,2} results{i,3}] = solver16(tiles, boardSize);if results{i,3}<1,board = results{i, 1}; orientation = results{i, 2}; score = results{i, 3};return,end
% [bestscore, pick] = min([results{:,3}]);
%
% i=5;
%
% [results{i,1} results{i,2} results{i,3}] = solver15_new(tiles, boardSize, results{pick,1}, results{pick,2});
%
%
% %i=6;
%
% %[bestscore, pick] = min([results{:,3}]);
% %[results{i,1} results{i,2} results{i,3}] = solver15a(tiles, boardSize, results{pick,1}, results{pick,2});
%
%
%
[~, pick] = min([results{:,3}]);
% if pick==5,disp('YUHUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU'),end
% if pick==6,disp('AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH'),end
%
% pick = 5;
board = results{pick, 1};
orientation = results{pick, 2};
score = results{pick, 3};
end
function [board orientation score] = solver12a(tiles, boardSize)
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])];
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);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
function ret = findbesttilefor(r, c)
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];
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
tilecosts(tilestaken) = inf;
[newerror, ret] = min(tilecosts-sum(tiles,2).*1e-6);
score = score - sum(tiles(ret, ~isnan(v))) - mynansum(v,2) + newerror;
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);
end
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(pix)
ix = mod(pix-1, ntiles)+1;
o = ceil(pix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
end
function [board orientation score] = solver13a(tiles, boardSize)
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])];
tilestaken = false(4*ntiles, 1);
boardSize_orig = boardSize;
nrows_orig = boardSize_orig(1);
ncols_orig = boardSize_orig(2);
if ntiles<nrows*ncols
rectangles=[repmat(1:nrows_orig,1,ncols_orig);repmat(1:ncols_orig,1,nrows_orig)];
rectangles_area = prod(rectangles);
rectangles_area(rectangles_area<ntiles)=inf;
[~,b] = min(rectangles_area-ntiles+2*sum(rectangles));
boardSize=rectangles(:,b)';
board = zeros(boardSize);
nrows = boardSize(1);
ncols = boardSize(2);
end
boarde = board;
try
boarde(:,3) = 10.^6./8;
boarde(:,ncols-2) = 10.^6./8;
boarde(3,:) = 10.^6./8;
boarde(nrows-2,:) = 10.^6./8;
boarde(:,2) = 10.^6./4;
boarde(:,ncols-1) = 10.^6./4;
boarde(2,:) = 10.^6./4;
boarde(nrows-1,:) = 10.^6./4;
boarde(:,1) = 10.^6./2;
boarde(:,ncols) = 10.^6./2;
boarde(1,:) = 10.^6./2;
boarde(nrows,:) = 10.^6./2;
boarde(1,1) = 10.^6;
boarde(1,ncols) = 10.^6;
boarde(nrows,1) = 10.^6;
boarde(nrows,ncols) = 10.^6;
end
if size(boarde,1)~=size(board,1) | size(boarde,2)~=size(board,2)
boarde = zeros(size(board));
end
f = nextfield();
while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
if ntiles<nrows_orig*ncols_orig
board_pimp=board;
board = zeros(boardSize_orig);
board(1:nrows,1:ncols)=board_pimp;
end
boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
function ret = findbesttilefor(r, c)
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];
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
tilecosts(tilestaken) = inf;
[newerror, ret] = min(tilecosts-sum(tiles,2).*1e-6);
score = score - sum(tiles(ret, ~isnan(v))) - mynansum(v,2) + newerror;
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);
end
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) + 2; end;
if row > 1 && col < ncols && ~board(row-1,col+1); boarde(row-1, col+1) = boarde(row-1, col+1) + 2; 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) + 2; end;
if row < nrows && col < ncols && ~board(row+1,col+1); boarde(row+1, col+1) = boarde(row+1, col+1) + 2; end;
end
function poptile(pix)
ix = mod(pix-1, ntiles)+1;
o = ceil(pix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
end
function [board orientation score] = solver14(tiles, boardSize)
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])];
tilestaken = false(4*ntiles, 1);
boarde = board;
boarde(ceil(nrows./2),ceil(ncols./2)) = 4;
f = nextfield();
while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
function ret = findbesttilefor(r, c)
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];
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
tilecosts(tilestaken) = inf;
[newerror, ret] = min(tilecosts-sum(tiles,2).*1e-6);
score = score - sum(tiles(ret, ~isnan(v))) - mynansum(v,2) + newerror;
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);
end
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(pix)
ix = mod(pix-1, ntiles)+1;
o = ceil(pix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
end
function [board orientation score] = solver16(tiles, boardSize)
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])];
tilesvalues = sum(tiles, 2);
tilestaken = false(4*ntiles, 1);
boardSize_orig = boardSize;
nrows_orig = boardSize_orig(1);
ncols_orig = boardSize_orig(2);
if ntiles<nrows*ncols
rectangles=[repmat(1:nrows_orig,1,ncols_orig);repmat(1:ncols_orig,1,nrows_orig)];
rectangles_area = prod(rectangles);
rectangles_area(rectangles_area<ntiles)=inf;
[~,b] = min(rectangles_area-ntiles+2*sum(rectangles));
boardSize=rectangles(:,b)';
board = zeros(boardSize);
nrows = boardSize(1);
ncols = boardSize(2);
end
boarde = board; % boardedgesoccupied
boarde(:,1) = 10.^6./2;
boarde(:,ncols) = 10.^6./2;
boarde(1,:) = 10.^6./2;
boarde(nrows,:) = 10.^6./2;
boarde(1,1) = 10.^6;
boarde(1,ncols) = 10.^6;
boarde(nrows,1) = 10.^6;
boarde(nrows,ncols) = 10.^6;
boarde(ceil(nrows./2),ceil(ncols./2)) = 10.^7;
f = nextfield();
while ~isempty(f) && ~all(tilestaken);
nextrow = f(1);
nextcol = f(2);
tix = findbesttilefor(nextrow, nextcol);
placetile(tix, nextrow, nextcol);
f = nextfield();
end
if ntiles<nrows_orig*ncols_orig
board_pimp=board;
board = zeros(boardSize_orig);
board(1:nrows,1:ncols)=board_pimp;
end
function ret = findbesttilefor(r, c)
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];
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
tilecosts(tilestaken) = inf;
[newerror, ret] = min(tilecosts-sum(tiles,2).*1e-6);
score = score - sum(tiles(ret, ~isnan(v))) - mynansum(v,2) + newerror;
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);
end
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(pix)
ix = mod(pix-1, ntiles)+1;
o = ceil(pix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;
end
function ret = mynansum(m, d)
m(isnan(m)) = 0;
ret = sum(m, d);
end
|
