# 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
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…

## 5 thoughts on “Snake Cube Puzzle Solver”

1. Ralf says:

Hi,

I have a snkae cube S = [3 4 4 4 2 4 2 4 2 2 2 2 2 2 2 2 2 3 2 4 3 3 2 4 2 3 2 2 2 2 2 3 2 2 2 2 4 2 4];
but I can’t find a solution with your script. Can you help me, please?

Best regards,
Ralf

2. wolframteetz says:

If you set
S = [3 4 4 4 2 4 2 4 2 2 2 2 2 2 2 2 2 3 2 4 3 3 2 4 2 3 2 2 2 2 2 3 2 2 2 2 4 2 4];
and
p = [1 1 1]; % Starting position x=1, y=1, z=1 (cube is solved backwards and you start with a 4, so you need to start in a corner to get any progress)
The program will start to iterate correctly. I ran it for 2 minutes and it got to 57 stones laid out only so far, but it should be only a matter of time until the iteration succeeds. Did you run it for an hour or so?

3. wolframteetz says:

(In RunSnake.m) do not invert your vector, then it runs and quicky finds a solution

S = [3 4 4 4 2 4 2 4 2 2 2 2 2 2 2 2 2 3 2 4 3 3 2 4 2 3 2 2 2 2 2 3 2 2 2 2 4 2 4];
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

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

4. Ralf says:

Yes, it run more than 2 or 3 hours. It claimed to have found a solution, but there were at least 6 or 7 “0” in the solution.
But now I have a solution.

Thank you yery much!

Best regards,
Ralf

5. wolframteetz says:

The solver will do a depth search on all solutions from a given starting point. If the starting point does not lead to a solution, you need to manually try all relevant starting points. Selection of the starting point is usually much easier from one side than the other, thus the “mirroring”.