function [board, orientation] = solver(tiles, boardSize)
[board,orientation,solved,nrow,ncol,ntiles] = board_perfect_snake(boardSize,tiles);
if solved;return;end
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 nnz(sorted(numUnplayed+1) == sorted(numUnplayed+1:end)) ~= length(equals)
temp_si = si(equals);
[trash,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,board,board,board,board);
o = ones(size(tiles,1), 18);
S=0;
NZ0= sum(tiles==0,2);
NZ = NZ0*0;
[b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,played,o(:,1),ntiles, cs,nrow,ncol,0,NZ);
[b(:,:,1),o(:,1),list] = place(height:-1:1,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles, cs,nrow,ncol,0,NZ);
newList(:,:,1) = list;
[b(:,:,2),o(:,2),list] = place(height:-1:1,last(2),b(:,:,2),played,played,o(:,2),ntiles, cs,nrow,ncol,0,NZ);
[b(:,:,2),o(:,2),list] = place(height,1:last(2),b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,0,NZ);
[b(:,:,2),o(:,2),list] = place(1:height-1,1,b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,0,NZ);
[b(:,:,2),o(:,2),list] = place(1,2:last(2),b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,0,NZ);
newList(:,:,2) = list;
NZ = NZ0*1;
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,1,NZ);
[b(:,:,i+2),o(:,i+2)] = place(2:height-1,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol,1,NZ);
[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,1,NZ);
[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,1,NZ);
end
NZ = sum(tiles,2);
[b(:,:,S+1 ), o(:,S+1 )] = picky(tiles, boardSize,nrow,ncol,cs,1,NZ);
[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);
S = S+1;
[b(:,:,S),o(:,S)] = placeRand(height:-1:1,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 + ii;
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
[trash,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)=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, lst, ort, 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;
[trash, sort_index] = sort(dist_center(:));
loop_order = flipud(sort_index)';
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
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);
nesw = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
score = sum(int32(abs(bsxfun(@minus,lst,nesw))),2);
[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, brd, tiles, lst, ort, ntiles, cs,nrow,ncol,flag,NZ)
k = 1;
for y=rowRange
for x=colRange
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,nrow,ncol);
nesw = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
score = sum(int32(abs(bsxfun(@minus,lst,nesw))),2);
[TT, O] = find(score==min(min(score)));
if flag
[trash,idx_t] = max(NZ(TT));
else
[trash,idx_t] = min(NZ(TT));
end
t = TT(idx_t);
o = O(idx_t);
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, brd, tiles, lst, ort, ntiles, cs,nrow,ncol)
k = 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);
%
nesw = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
score = sum(int32(abs(bsxfun(@minus,lst,nesw))),2);
% [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 || board(row,col) == 0
value = 0;
elseif board(row,col) == -1
value = nan;
else
value = tiles(board(row,col),cs(orientation(board(row,col)),id));
end
end
function [board, orientation] = picky(tiles, boardSize,nrow,ncol,cs,flag,NZ)
nt = size(tiles,1);
board = zeros(boardSize);
nb = nrow*ncol;
orientation = ones(nt,1);
unused = true(1,nt);
[n, e, s, w] = deal(nan(boardSize));
n(1,:) = 0;
s(end,:) = 0;
e(:,end) = 0;
w(:,1) = 0;
tsum = sum(tiles,2);
% greedily pick tiles
for i = 1:min(nb,nt)
nesw = cat(3, [n(i) e(i) s(i) w(i)], [w(i) n(i) e(i) s(i)], [s(i) w(i) n(i) e(i)],[e(i) s(i) w(i) n(i)]);
hsm = sum(int32(abs(bsxfun(@minus,tiles(unused,:),nesw))),2);
hsm(hsm~=min(hsm(:))) = inf;
hsm = bsxfun(@minus,hsm,tsum(unused));
[TT, OO] = find(hsm==min(min(hsm)));
if flag
[trash,idx_t] = max(NZ(TT));
else
[trash,idx_t] = min(NZ(TT));
end
pick = TT(idx_t);
ori = OO(idx_t);
pick = find(unused,pick);
pick = pick(end);
board(i) = pick;
orientation(pick) = ori;
unused(pick) = false;
% update goals
if (i+nrow <= nb)
w(i+nrow) = tiles(pick,cs(ori,2));
end
if (mod(i,nrow) ~= 0)
n(i+1) = tiles(pick,cs(ori,3));
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);
% 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;
[trash, ret] = min(tilecosts-sum(tiles,2).*1e-6);
else
tilecosts = bsxfun(@minus, tiles, v);
tilecosts = abs(tilecosts);
tilecosts = mynansum(tilecosts, 2);
tilecosts(tilestaken) = inf;
[trash, ret] = min(tilecosts - 1e-10*sum(tiles(:, isnan(v)), 2));
end
end
% Richard routine adds with otile removal tweak
function [board,orientation,solved,nr,nc,numtiles]=board_perfect_snake(boardSize,tiles)
% check for perfect unique board
solved=false;
board = zeros(boardSize);
numtiles=size(tiles,1);
orientation = ones(numtiles, 1);
[nr nc]=size(board);
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
nrnc=nr*nc;
if numtiles~=nrnc,return;end
otiles=tiles;
[board,orientation,otiles,valid]= ...
find_corner(board,tiles,otiles,orientation);
if ~valid,return;end
for i=1:nr
if i>1
tile=board(i-1,1);
[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,tiles,otiles,i,1,nrnc,tile,3);
% [board,orientation,otiles,valid]= ...
% first_column(board,orientation,otiles,tiles,i,j,nelem,tile,edge);
if ~valid,return;end
end % i>1
for j=2:nc
tile=board(i,j-1);
[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,tiles,otiles,i,j,nrnc,tile,2);
if ~valid,return;end
end % j 2:nc
end % i 1:nr
solved=true;
end
function [board,orientation,otiles,valid]= ...
find_corner(board,tiles,otiles,orientation)
valid=false;
for i=1:4
j=i-1; if j==0,j=4;end
adj=abs(tiles(:,i))+abs(tiles(:,j));
tv=find(adj==0,1); % Corner found
if ~isempty(tv)
orientation(tv)=i;
otiles(tv,:)=rot_tile(orientation(tv),tiles(tv,:));
board(1,1)=tv;
valid=true;
return; % corner found and rotated to position
end
end
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,tiles,otiles,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
|
