Denver Dev Day snake puzzle solver

At https://www.meetup.com/DenverDevDay/ 2023 Fall I get the following puzzle.

When disassembled it looks this way

Quite hard puzzle I would say. I decided to write a C# program to solve it.

const int dim = 3;
int[] snake = { 3, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 3, 2, 2, 3 };

bool[,,] used = new bool[dim, dim, dim];

Stack<Point> path = new();
used[0, 0, 0] = true;

if (DFS((0, 0, 0), 0, (0, 0, 0))) {
    foreach (var m in path.Reverse()) {
        Console.WriteLine(m);
    }
};

bool DFS(Point p, int idx, Point m) {
    if (idx >= snake.Length) {
        return false;
    }

    if (p == (dim - 1, dim - 1, dim - 1) && idx == snake.Length - 1) {
        Console.WriteLine("done!");
        return true;
    }

    foreach (var move in Point.Moves) {
        if (move == m) { continue; }
        var len = (snake[idx] - 1);
        var nextLen1Or2 = p + (move * len);
        var nextLen1 = p + move;
        if (!nextLen1Or2.InCube(dim)) { continue; }
        if (used[nextLen1Or2.X, nextLen1Or2.Y, nextLen1Or2.Z]) { continue; }
        if (used[nextLen1.X, nextLen1.Y, nextLen1.Z]) { continue; }
        path.Push(move);
        used[nextLen1Or2.X, nextLen1Or2.Y, nextLen1Or2.Z] = true;
        used[nextLen1.X, nextLen1.Y, nextLen1.Z] = true;
        if (DFS(nextLen1Or2, idx + 1, move)) {
            return true;
        }
        path.Pop();
        used[nextLen1Or2.X, nextLen1Or2.Y, nextLen1Or2.Z] = false;
        used[nextLen1.X, nextLen1.Y, nextLen1.Z] = false;
    }

    return false;
}

public record struct Point(int X, int Y, int Z) {
    public static readonly Point[] Moves = { (-1, 0, 0), (0, -1, 0), (0, 0, -1), (1, 0, 0), (0, 1, 0), (0, 0, 1) };
    public static Point operator +(Point a, Point b) => new(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    public static Point operator *(Point a, int f) => new(a.X * f, a.Y * f, a.Z * f);
    public static implicit operator Point((int X, int Y, int Z) p) => new(p.X, p.Y, p.Z);
    public readonly bool InCube(int size) => X >= 0 && X < size && Y >= 0 && Y < size && Z >= 0 && Z < size;
}

So the solution is:

Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 1, Z = 0 }
Point { X = -1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = 1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = -1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = -1, Z = 0 }
Point { X = -1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = 1 }
Point { X = 0, Y = 1, Z = 0 }
Point { X = 0, Y = 0, Z = -1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 0, Z = 1 }
Point { X = 1, Y = 0, Z = 0 }
Point { X = 0, Y = 1, Z = 0 }

Blog

Denver Dev Day snake puzzle solver

Stanislav Berkov

Join Our Newsletter. No Spam, Only the good stuff.

Related