Code covered by the BSD License

# Boggle (V2.0)

by

### Sean de (view profile)

08 Aug 2011 (Updated )

The traditional Boggle Master Game from Hasbro

binpath(A)
```function path = binpath(A)
% function path = binpath(A)
% returns the path coordinates go through a 3D object stored binary array A
% INPUT: A, 3D binary array
% OUTPUT:
% if such path exists
% PATH an (3 x r) array, each column of B is a coordinate in A:
% - the path links first slide and the last slide
% - the path will never have (x,y) coordinates repeated
% - every depth slide is used only once
% otherwise empty array is returned
%

A = logical(A);
[m n p] = size(A);
if p==0
path = [];
return
end
B = true([m n]); % B allowed (x,y) coordinates
depth = 0;
path = zeros(3,2*p);
for i=1:m
for j=1:n
if A(i,j,1)
OK = findpathdynprog(i,j,1);
if OK
% cut the tail
path(:,depth+1:end) = [];
return
end
end
end
end
path = [];
return

% nested function dynamic programming
function OK = findpathdynprog(i,j,k)
depth = depth+1;
if depth>size(path,2) % grow the path
path(:,2*end) = 0;
end
% store the coordinates
path(:,depth) = [i; j; k];
if (k==p) % reach the last slide, stop recursion
OK = true;
return
else
% save the current state of B(i,j)
Bij = B(i,j);
B(i,j) = false; % mark as occupied
% Get the clipped 3x3x3 box
ii = max(i-1,1):min(i+1,m);
jj = max(j-1,1):min(j+1,n);
kk = min(k+1,p); % Change here
neighbor = bsxfun(@and, A(ii,jj,kk), B(ii,jj));
l = 0;
for kl = kk
for jl = jj
for il = ii
l = l+1;
if neighbor(l)
OK = findpathdynprog(il,jl,kl);
if OK
return
end
end
end
end
end
% fail
OK = false;
% restore the initial state
depth = depth-1;
B(i,j) = Bij;
end
end % path = binpath(A)

end % binpath

% Bruno

%Reference: