Brute force solution to that twisty snake puzzle thing.

puzzle_solver.py

import copy
import datetime

# The length of each segment, in order.
# Note that blocks at an intersection count as part of both segments
puzzle = [
    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,
]

directions = {
    # name: (axis, sign),
    'left': ('x', 1),
    'right': ('x', -1),
    'up': ('y', 1),
    'down': ('y', -1),
    'forward': ('z', 1),
    'backward': ('z', -1),
}


class PuzzleState(object):

    def __init__(self):
        self.history = []
        self.current_direction = None
        self.current_axis = None
        self.current_sign = None
        self.position = {'x': 0, 'y': 0, 'z': 0}
        self.occupied_spaces = {(0, 0, 0)}
        self.max_bounds = {'x': 0, 'y': 0, 'z': 0}
        self.min_bounds = {'x': 0, 'y': 0, 'z': 0}

    def copy(self):
        # I initially used copy.deepcopy, but killed it after 18 minutes
        # without finding the solution. Switching to a targeted copy brings
        # that down to < 1.5 minutes
        state = PuzzleState()
        state.history = copy.copy(self.history)
        state.max_bounds = copy.copy(self.max_bounds)
        state.min_bounds = copy.copy(self.min_bounds)
        state.occupied_spaces = copy.copy(self.occupied_spaces)
        state.position = copy.copy(self.position)
        return state

    def turn(self, direction):
        axis, sign = directions[direction]
        assert axis != self.current_axis
        state = self.copy()
        state.history.append(direction)
        state.current_direction = direction
        state.current_axis = axis
        state.current_sign = sign
        return state

    def walk(self, num_steps):
        for _ in range(num_steps):
            self.step()

    def step(self):
        new_coord = self.position[self.current_axis] + self.current_sign
        self.position[self.current_axis] = new_coord

        # check that the next step doesn't take us out of a 4x4 area
        new_max = max(new_coord, self.max_bounds[self.current_axis])
        self.max_bounds[self.current_axis] = new_max
        new_min = min(new_coord, self.min_bounds[self.current_axis])
        self.min_bounds[self.current_axis] = new_min
        assert (new_max - new_min) < 4

        # check that we haven't already been to this next position
        position = (self.position['x'], self.position['y'], self.position['z'])
        assert position not in self.occupied_spaces
        self.occupied_spaces.add(position)


def solve(remaining_puzzle, state):
    # this takes a while to run, so provide some indication of progress
    if len(state.history) < 5:
        print datetime.datetime.now(), state.history

    if not remaining_puzzle:
        return state

    segment = remaining_puzzle[0]
    for direction in ['forward', 'backward', 'left', 'right', 'up', 'down']:
        try:
            next_state = state.turn(direction)
            next_state.walk(segment - 1)
        except AssertionError:
            next
        else:
            solution = solve(remaining_puzzle[1:], next_state)
            if solution:
                return solution


if __name__ == '__main__':
    print "attempting!"
    solution = solve(puzzle, PuzzleState())
    for step, count in zip(solution.history, puzzle):
        print step, count