function [board, orientation] = solver(tiles, boardSize)
% Clone of Nuwan 2012-04-08 00:31:26
% Add Unique Snake solve
board = zeros(boardSize);
%Richard add
%board = zeros(boardSize);
%[nr nc]=size(board);
%numtiles=size(tiles,1);
%orientation = ones(size(tiles,1), 1);
%if ntiles==nElem % Do Perfect Unique Board Check
[board,orientation,solved]=board_perfect_snake(board,tiles);
if solved,return;end
%end
% End of Main routine Richard add
ntiles = size(tiles,1);
nrow = boardSize(1);
ncol = boardSize(2);
nElem = nrow*ncol;
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);
[sorted,si] = sort(sums);
equals = find(sorted(numUnplayed+1)==sorted);
if(length(find(sorted(numUnplayed+1)==sorted(numUnplayed+1:end)))~=length(equals))
temp_si = si(equals);
[~,mi] = sort(min(tiles(temp_si,:),[],2));
for i=1:length(equals)
si(equals(end+1-i))= temp_si(mi(i));
end
end
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,board,board,board,board,board);
o = ones(size(tiles,1), 18);
S=0;
[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(:,:,2),o(:,2),list] = place(height:-1:1,last(2),b(:,:,2),played,played,o(:,2),ntiles, cs,nrow,ncol);
[b(:,:,2),o(:,2),list] = place(height,1:last(2),b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol);
[b(:,:,2),o(:,2),list] = place(1:height-1,1,b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol);
[b(:,:,2),o(:,2),list] = place(1,2:last(2),b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol);
newList(:,:,2) = list;
for i=[2 6]
c = floor(i/6) + 1;
[b(:,:,i+1),o(:,i+1),~] = place(height-1:-1:2,ncol-1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles , cs,nrow,ncol);
[b(:,:,i+2),o(:,i+2),~] = place(2:height-1,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol);
[b(:,:,i+3),o(:,i+3),~] = place(height-1:-1:2,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol);
[b(:,:,i+4),o(:,i+4),~] = place(2:height-1,ncol-1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol);
end
[b(:,:,S+1 ), o(:,S+1 )] = picky(tiles, boardSize,nrow,ncol,cs);
[b(:,:,S+2 ), o(:,S+2 )] = calibrating_pure(tiles, boardSize,nrow,ncol);
S = 11;
[b(:,:,S),o(:,S),~] = placeRand(1:height,1:ncol,b(:,:,S),played,played,o(:,S),ntiles,cs,nrow,ncol);
if nElem < 1000
for ii = 1:4
[b(:,:,S+ii),o(:,S+ii)] = MichaelC(height,last(2), tiles, played, o(:,S+ii), ntiles, cs,nrow,ncol);
end
S = S + 4;
if nElem < 200
[b(:,:,S+1), o(:,S+1)] = 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);
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);
dist_center = dist_center + rand(size(dist_center))*0.01;
[~, 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, o] = find(score==min(score(:)));
which = round(rand*(length(ms)-1)+1);
t = ms(which);
ort(t) = o(which);
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 [brd, ort, lst] = placeRand(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);
[ms, o] = find(score==min(score(:)));
which = ceil(length(ms)/2);%round(rand*(length(ms)-1)+1);
t = ms(which);
ort(t) = o(which);
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
% Richard routine adds
function [board,orientation,solved]=board_perfect_snake(board,tiles)
% check for perfect unique board
solved=false;
orientation = ones(size(tiles,1), 1);
[nr nc]=size(board);
nrnc=nr*nc;
%numtiles=size(tiles,1);
ptiles=prod(tiles,2); % search for zeros to count edge/corner pieces
% minimum required #tiles with a zero
if size(find(ptiles==0),1)<2*(nr+nc-2),return;end % No solution
otiles=tiles;
%gtiles=ones(numtiles,1); % Unused tiles
[board,orientation,otiles,valid]= ...
find_corner(board,otiles,tiles,orientation);
if valid==false,return;end
for i=1:nr
if i>1
tile=board(i-1,1);
[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,otiles,tiles,i,1,nrnc,tile,3);
% [board,orientation,otiles,valid]= ...
% first_column(board,orientation,otiles,tiles,i,j);
if valid==false,return;end
end % i>1
for j=2:nc
tile=board(i,j-1);
[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,otiles,tiles,i,j,nrnc,tile,2);
if valid==false,return;end
end % j 2:nc
end % i 1:nr
solved=true;
%brd_score=board_scr(board,orientation,tiles);
end
function [board,orientation,otiles,valid]= ...
find_corner(board,otiles,tiles,orientation)
valid=false; % could remove valid=false from returns
% Find a corner %
adj=abs(tiles(:,1))+abs(tiles(:,4));
tv=find(adj==0,1); % corner found No rotation
if isempty(tv)
found=false;
for i=2:4
adj=abs(tiles(:,i))+abs(tiles(:,i-1));
tv=find(adj==0,1); % Corner found
if ~isempty(tv)
orientation(tv)=i;
otiles(tv,:)=rot_tile(orientation(tv),tiles(tv,:));
found=true;
break; % corner found and rotated to position
end
end
if ~found,return;end % No Zero corners
end
board(1,1)=tv;
valid=true;
end % find corner
function [one_tile]=rot_tile(rot,tile)
one_tile=circshift(tile,[0 1-rot]);
end
function [board,orientation,otiles,valid]= ...
find_tiles(board,orientation,otiles,tiles,i,j,nrnc,tile,ul)
% [board,orientation,otiles,valid]= ...
% first_column(board,orientation,otiles,tiles,i,j,nrnc,tile,UL);
valid=false; % could remove valid=false from returns
goal=otiles(tile,ul);
tvec=find(otiles==goal);
if size(tvec,1)~=2,return;end % Non Unique solutions
% Have two solution - one already used
tnum=mod(tvec-1,nrnc)+1;
trot=floor((tvec-1)/nrnc)+1;
if tnum(1)~=tile % use
tv=tnum(1);
rot=trot(1);
else % use 2nd
tv=tnum(2);
rot=trot(2);
end
% for found pushed to L(4) 4:1,3:4,2:3,1:2
if j>1 % doing rows
if rot==4
rot=1;
else
rot=rot+1;
end
end
board(i,j)=tv;
otiles(tv,:)=rot_tile(rot,tiles(tv,:));
orientation(tv)=rot;
valid=true;
end % fill rows
|
