Snake Cube Puzzle Solver

DSCN3573

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…

Advertisements

5 thoughts on “Snake Cube Puzzle Solver

  1. 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. 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. (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. 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. 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”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s