| Code: |
function [board, orientation] = solver(tiles, boardSize)
orientation = ones(size(tiles,1), 1);
ntiles = size(tiles,1);
board = zeros(boardSize);
played = discardUnplayed(ntiles-numel(board), tiles);
orientation = ones(size(tiles,1), 1);
ntiles = size(tiles,1);
board = zeros(boardSize);
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
played = discardUnplayed(ntiles-numel(board), tiles);
if (ntiles-numel(board)<0)
height=min([ceil(sqrt(ntiles)) boardSize(1)]);
if (ntiles/boardSize(2))>height
height=ceil(ntiles/boardSize(2));
end
else
ntiles=numel(board);
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([1 height],last(2):-1:1,b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
[b(:,:,5),o(:,5),list] = place(1:height,[1 last(2)],b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs);
newList(:,:,2) = list;
for i=[0 4]
[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
overall = zeros(8,1);
for i=1:8
b(:,:,i) = board;
o(:,i) = orientation;
overall(i) = overallScore(b(:,:,i),o(:,i),tiles, cs);
end
list = played;
[b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,list,o(:,1),ntiles);
[b(:,:,1),o(:,1),list] = place(1:height,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles);
newList(:,:,1) = list;
list = played;
[b(:,:,5),o(:,5),list] = place([1 height],last(2):-1:1,b(:,:,5),played,list,o(:,5),ntiles);
[b(:,:,5),o(:,5),list] = place(1:height,[last(2) 1],b(:,:,5),played,list,o(:,5),ntiles);
newList(:,:,2) = list;
% list = played;
% [b(:,:,9),o(:,9),list] = place([1 height],last(2):-1:1,b(:,:,9),played,list,o(:,9),ntiles);
% [b(:,:,9),o(:,9),list] = place(1:height,[last(2) 1],b(:,:,9),played,list,o(:,9),ntiles);
% newList(:,:,3) = list;
%
% list = played;
% [b(:,:,13),o(:,13),list] = place([height 1],last(2):-1:1,b(:,:,13),played,list,o(:,13),ntiles);
% [b(:,:,13),o(:,13),list] = place(1:height,[last(2) 1],b(:,:,13),played,list,o(:,13),ntiles);
% newList(:,:,4) = list;
for i=[0 4]
[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);
[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);
[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);
[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);
end
for i=1:8
overall(i) = overallScore(b(:,:,i),o(:,i),tiles);
end
[~,mo] = min(overall);
board = b(:,:,mo);
orientation = o(:,mo);
end
function [score] = overallScore(board, orientation, tiles)
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
boardSize=size(board);
tile = zeros(boardSize(1)*4,boardSize(2));
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)),:))';
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));
score = internal + external;
end
function [score] = overallScore(board, orientation, tiles, cs)
function [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles)
boardSize=size(board);
tile = zeros(boardSize(1)*4,boardSize(2));
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)),:))';
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));
score = internal + external;
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);
[t, o] = findBestTile(lst, n, e, s, w);
[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 played = discardUnplayed(numUnplayed, tiles)
played = tiles;
if numUnplayed>0
function [played] = discardUnplayed(numUnplayed, tiles)
played = tiles;
sums = sum(tiles,2);
[~,si] = sort(sums);
played(si(1:numUnplayed),:) = Inf(numUnplayed,4);
for i = 1:numUnplayed
[~, m]=min(sums);
played(m,:)=inf(1,4);
sums(m)=inf;
end
end
end
function [tile, orientation] = findBestTile(list, north, east, south, west)
score = int32(zeros(size(list,1),4));
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
grid = ones(size(list,1),1)*[north east south west];
for i=1:4
temp = int32(abs(list(:,cs(:,i))-grid));
score(:,i) = sum(temp,2);
end
[ms, t] = min(score);
[~, orientation] = min(ms);
tile = t(orientation);
function [tile, orientation] = findBestTile(list, L, north, east, south, west, cs)
% [t, o] = find(score==min(score(:)));
% %[~, which] = max(mean(t,2));
% which = 1;%round(length(t)/2);%round(rand*(length(t)-1)+1);
% tile = t(which);
% orientation = o(which);
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)
north = boundary(board,tiles,orientation,row-1,col,3);
south = boundary(board,tiles,orientation,row+1,col,1);
west = boundary(board,tiles,orientation,row,col-1,2);
east = boundary(board,tiles,orientation,row,col+1,4);
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)
cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3];
try
if (board(row,col)==0)
value = 0;
elseif (board(row,col)==-1)
value = nan;
else
tile = tiles(board(row,col),cs(orientation(board(row,col)),:));
value = tile(id);
end
catch
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
|
