Code covered by the BSD License  

Highlights from
Boggle (V2.0)

image thumbnail

Boggle (V2.0)

by

 

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:
%http://www.mathworks.com/matlabcentral/newsreader/view_thread/298048
%

Contact us