Snake Cube Puzzle Solver

In Octave / Matlab

I got this 4×4 “maximum” difficulty snake cube for christmas (with the solution removed from the package of course…) and decided it would be much faster to solve it by programming it than by hand…

So, if you’re searching for a solution, here is a general one

You will need GNU Octave, you can install it on OSX by running brew install octave assuming you have homebrew installed. For Windows, just follow the link above.

Run by creating the two files below in your favourite text editor, modify the Snake Vector S, start vector P and starting direction v to match your snake, run octave, start RunSnake

Script (RunSnake.m), edit your Cube here

# Octave Snake Code
# 31.12.2014 - 1.1.2015, Wolfram Teetz <wolframteetz@gmail.com>

global iter;
global maxdepth;
global maxmatrix;
global nulltime;
global lasttime;

iter = 0;         % Iteration
maxdepth = 0;     % Maximum solved depth so far
maxmatrix = 0;    % Best solution so far
nulltime=0;       % Start time in seconds
lasttime=0;       % Start time of last iteration in seconds

S = [4 2 4 2 2 2 2 3 2 2 2 2 2 3 2 4 2 3 3 4 2 3 2 2 2 2 2 2 2 2 2 4 2 4 2 4 4 4 3]; % My snake - length of all edges
S = fliplr(S);    % Solve backwards (optional)
W = zeros(4,4,4); % Cube volume
v = +1;           % Starting direction +1=Ascending in dimension 1 == x, -2 would be descending in y etc.
p = [2 1 1];      % Starting position x=2, y=1, z=1
nr = 1;           % Start with stone #1

disp ('Starting Search...');
fflush(stdout);
nulltime = time;
r=OctaveSnake(S,W,v,p,nr,false);
fflush(stdout);

The recusive main function (OctaveSnake.m)

function r = OctaveSnake(xS, xW, xv, xp, xnr, dispy)

    global iter;
    global maxdepth;
    global maxmatrix;
    global nulltime;
    global lasttime;

    iter = iter + 1;
    if (mod(iter,10000) == 0)
        clc
        disp("Iteration ");
        disp(iter);
        disp("Time");
        disp((time-lasttime));
        lasttime=time;
        disp("Total Time");
        disp((time-nulltime));
        disp("Maxdepth ");
        disp(maxdepth);
        disp("Max Matrix");
        disp(maxmatrix);
        fflush(stdout);
    endif

    if (dispy) disp("Try to continue from position"); endif;
    if (dispy) disp(xp); endif;
    if (dispy) disp("Direction"); endif;
    if (dispy) disp(xv); endif;

    for (i=2:xS(1))

        % Check state
        if (min(xp)<1)
            r = false;
            if (dispy) disp("  out of 4x4 -- abort"); endif;
            return;
            % out of bounds
        endif
        if (dispy) disp("  minok"); endif;

        if (max(xp)>4)
            r = false;
            if (dispy) disp("  out of 4x4 -- abort"); endif;
            return;
            % out of bounds
        endif
        if (dispy) disp("  maxok"); endif;

        if (xW(xp(1),xp(2),xp(3))!=0)
            r = false;
            if (dispy) disp("  collision -- abort"); endif;
            return;
            % collision, stone at this position already
        endif
        if (dispy) disp("  no collision"); endif;

        % Test, if there are enough free complete rows of 4 stones empty for remaining 4-rows
        if (i==2) % Only on the first iteration per call
            cremaining = length(find(xS==4));
            cfree = sum(sum( (sum(xW, 1)==0) ));
            cfree += sum(sum( (sum(xW, 2)==0) ));
            cfree += sum(sum( (sum(xW, 3)==0) ));
            if (cremaining>cfree)
                r = false;
                return;
            endif
        endif

        if (dispy) disp("  place length"); endif;
        if (dispy) disp(xS(1)); endif;

        if (dispy) disp("Set Stone #"); endif;
        if (dispy) disp(xnr); endif;

        xW(xp(1),xp(2),xp(3))=xnr; %  Set stone, prepare next stone
         % xW(xp) = xnr; % Keep in mind this gives an error in Octave

        xnr = xnr + 1;
        xp(abs(xv)) += sign(xv);

        if (dispy) disp("New Position"); endif;
        if (dispy) disp(xp); endif;

        % New maximum depth found
        if (xnr>maxdepth)
            maxdepth = xnr;
            maxmatrix = xW;
        endif

        if (xnr>63)
            disp("S O L U T I O N");
            disp("---------------");
            disp(xW); % Display state
            r = true;
            fflush(stdout);
            pause;
            return;
        endif

        % Move one field
    endfor

    for (nV=[-3 -2 -1 1 2 3])
        if (abs(nV) != abs(xv)) % Orthogonal turn
            r = OctaveSnake(xS(2:length(xS)), xW, nV, xp, xnr,dispy); % Turn and enter recursion
            if (r) return; endif;
        endif
    endfor

endfunction

Your solution will be displayed like this :

S O L U T I O N
—————
ans(:,:,1) =

12   11   10    9
1   24   25    8
2   27   26    7
3    4    5    6

ans(:,:,2) =

13   22   31   32
14   23   30   33
15   28   29   34
16   37   36   35

ans(:,:,3) =

20   21   50   51
19   48   49   52
18   47   54   53
17   38   55   56

ans(:,:,4) =

43   44   61   60
42   45   62   59
41   46   63   58
40   39    0   57

Meaning you should put the first stone (1) on the lowest level (:,:,1), stone 2 below, stone 3 below, stone 4 to the right, … , stone 12 to the left, stone 13 above #12, then 14 below 13 and so on…