Este desafio não é sobre o jogo Snake.

Imagine uma cobra 2D formada desenhando uma linha horizontal de comprimento n. Em pontos inteiros ao longo de seu corpo, essa cobra pode girar seu corpo em 90 graus. Se definirmos a frente da cobra na extremidade esquerda, a rotação moverá a parte de trás da cobra e a parte da frente permanecerá em pé. Fazendo rotações repetidas, ele pode criar muitas formas diferentes de corpo de cobra.

Regras

1. Uma parte do corpo da cobra não pode se sobrepor a outra.
2. Tem que ser possível alcançar a orientação final sem que nenhuma parte do corpo da cobra se sobreponha entre elas. Dois pontos que tocam são contados como sobrepostos nesse problema.
3. Eu considero uma cobra e seu reverso como tendo a mesma forma.

Tarefa

Até rotação, translação e simetria de espelho, qual é o número total de diferentes formas de corpos de serpentes que podem ser feitas?

Exemplo de rotação de parte do corpo das cobras. Imagine n=10e a cobra está na orientação inicial de uma linha reta. Agora gire no ponto 490 graus no sentido anti-horário. Ficamos com a cobra de 4que 10(a cauda da cobra) deitado verticalmente ea cobra a partir 0de 4deitado na horizontal. A cobra agora tem um ângulo reto em seu corpo.

Aqui estão alguns exemplos, graças a Martin Büttner.

Começamos com a cobra horizontal.

Agora nós giramos da posição 4.

Terminamos após a rotação nesta orientação.

Agora vamos considerar essa orientação de uma cobra diferente.

Agora podemos ver um movimento ilegal em que haveria uma sobreposição causada durante a rotação.

Ponto

Sua pontuação é a maior npara a qual seu código pode resolver o problema em menos de um minuto no meu computador.

Quando uma rotação acontece, ela move metade da cobra. Precisamos nos preocupar se alguma parte desta que é girada pode se sobrepor a uma parte da cobra durante a rotação. Para simplificar, podemos assumir que a cobra tem largura zero. Você só pode girar em um ponto específico da cobra até 90 graus no sentido horário ou anti-horário. Pois, você nunca pode dobrar completamente a cobra em duas, pois isso envolveria duas rotações no mesmo ponto na mesma direção.

Formas que não podem ser criadas

Um exemplo simples de uma forma que não pode ser feita é uma capital T. Uma versão mais sofisticada é

(Obrigado a Harald Hanche-Olsen por este exemplo)

Neste exemplo, todas as linhas horizontais adjacentes estão separadas por 1 e são as verticais. Portanto, não há movimento legal a partir dessa posição e, como o problema é reversível, não há como chegar a partir da posição inicial.

Línguas e bibliotecas

Você pode usar qualquer idioma que tenha um compilador / intérprete disponível gratuitamente / etc. para Linux e quaisquer bibliotecas que também estão disponíveis gratuitamente para Linux.

Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 de oito núcleos. Isso também significa que eu preciso poder executar seu código. Como conseqüência, use apenas software livre facilmente disponível e inclua instruções completas sobre como compilar e executar seu código.

Python 3 - pontuação provisória: n = 11 (n = 13 com PyPy *)

Como não houve respostas na primeira semana, aqui está um exemplo em Python para incentivar a competição. Tentei torná-lo razoavelmente legível para que as ineficiências possam ser facilmente identificadas para fornecer idéias para outras respostas.

Abordagem

• Comece com a cobra reta e encontre todas as posições que podem ser legalmente alcançadas em um único movimento.
• Encontre todas as posições que podem ser alcançadas legalmente a partir dessas posições, que ainda não foram identificadas.
• Repita até que não seja mais encontrado e retorne o número de posições encontradas.

Código

(agora com alguns documentos e declarações após minha primeira tentativa incorreta)

'''
Snake combinations

A snake is represented by a tuple giving the relative orientation at each joint.
A length n snake has n-1 joints.
Each relative orientation is one of the following:

0: Clockwise 90 degrees
1: Straight
2: Anticlockwise 90 degrees

So a straight snake of length 4 has 3 joints all set to 1:

(1, 1, 1)

x increases to the right
y increases upwards

'''


import turtle


def all_coords(state):
    '''Return list of coords starting from (0,0) heading right.'''
    current = (1, 0)
    heading = 0
    coords = [(0,0), (1,0)]
    for item in state:
        heading += item + 3
        heading %= 4
        offset = ((1,0), (0,1), (-1,0), (0,-1))[heading]
        current = tuple(current[i]+offset[i] for i in (0,1))
        coords.append(current)
    return coords


def line_segments(coords, pivot):
    '''Return list of line segments joining consecutive coords up to pivot-1.'''
    return [(coords[i], coords[i+1]) for i in range(pivot+1)]


def rotation_direction(coords, pivot, coords_in_final_after_pivot):
    '''Return -1 if turning clockwise, 1 if turning anticlockwise.'''
    pivot_coord = coords[pivot + 1]
    initial_coord = coords[pivot + 2]
    final_coord = coords_in_final_after_pivot[0]
    initial_direction = tuple(initial_coord[i] - pivot_coord[i] for i in (0,1))
    final_direction = tuple(final_coord[i] - pivot_coord[i] for i in (0,1))
    return (initial_direction[0] * final_direction[1] -
            initial_direction[1] * final_direction[0]
            )


def intersects(arc, line):
    '''Return True if the arc intersects the line segment.'''
    if line_segment_cuts_circle(arc, line):
        cut_points = points_cutting_circle(arc, line)
        if cut_points and cut_point_is_on_arc(arc, cut_points):
            return True


def line_segment_cuts_circle(arc, line):
    '''Return True if the line endpoints are not both inside or outside.'''
    centre, point, direction = arc
    start, finish = line
    point_distance_squared = distance_squared(centre, point)
    start_distance_squared = distance_squared(centre, start)
    finish_distance_squared = distance_squared(centre, finish)
    start_sign = start_distance_squared - point_distance_squared
    finish_sign = finish_distance_squared - point_distance_squared
    if start_sign * finish_sign <= 0:
        return True


def distance_squared(centre, point):
    '''Return the square of the distance between centre and point.'''
    return sum((point[i] - centre[i]) ** 2 for i in (0,1))


def cut_point_is_on_arc(arc, cut_points):
    '''Return True if any intersection point with circle is on arc.'''
    centre, arc_start, direction = arc
    relative_start = tuple(arc_start[i] - centre[i] for i in (0,1))
    relative_midpoint = ((relative_start[0] - direction*relative_start[1])/2,
                         (relative_start[1] + direction*relative_start[0])/2
                         )
    span_squared = distance_squared(relative_start, relative_midpoint)
    for cut_point in cut_points:
        relative_cut_point = tuple(cut_point[i] - centre[i] for i in (0,1))
        spacing_squared = distance_squared(relative_cut_point,
                                           relative_midpoint
                                           )
        if spacing_squared <= span_squared:
            return True


def points_cutting_circle(arc, line):
    '''Return list of points where line segment cuts circle.'''
    points = []
    start, finish = line
    centre, arc_start, direction = arc
    radius_squared = distance_squared(centre, arc_start)
    length_squared = distance_squared(start, finish)
    relative_start = tuple(start[i] - centre[i] for i in (0,1))
    relative_finish = tuple(finish[i] - centre[i] for i in (0,1))
    relative_midpoint = tuple((relative_start[i] +
                               relative_finish[i]
                               )*0.5 for i in (0,1))
    determinant = (relative_start[0]*relative_finish[1] -
                   relative_finish[0]*relative_start[1]
                   )
    determinant_squared = determinant ** 2
    discriminant = radius_squared * length_squared - determinant_squared
    offset = tuple(finish[i] - start[i] for i in (0,1))
    sgn = (1, -1)[offset[1] < 0]
    root_discriminant = discriminant ** 0.5
    one_over_length_squared = 1 / length_squared
    for sign in (-1, 1):
        x = (determinant * offset[1] +
             sign * sgn * offset[0] * root_discriminant
             ) * one_over_length_squared
        y = (-determinant * offset[0] +
             sign * abs(offset[1]) * root_discriminant
             ) * one_over_length_squared
        check = distance_squared(relative_midpoint, (x,y))
        if check <= length_squared * 0.25:
            points.append((centre[0] + x, centre[1] + y))
    return points


def potential_neighbours(candidate):
    '''Return list of states one turn away from candidate.'''
    states = []
    for i in range(len(candidate)):
        for orientation in range(3):
            if abs(candidate[i] - orientation) == 1:
                state = list(candidate)
                state[i] = orientation
                states.append(tuple(state))
    return states


def reachable(initial, final):
    '''
    Return True if final state can be reached in one legal move.

    >>> reachable((1,0,0), (0,0,0))
    False

    >>> reachable((0,1,0), (0,0,0))
    False

    >>> reachable((0,0,1), (0,0,0))
    False

    >>> reachable((1,2,2), (2,2,2))
    False

    >>> reachable((2,1,2), (2,2,2))
    False

    >>> reachable((2,2,1), (2,2,2))
    False

    >>> reachable((1,2,1,2,1,1,2,2,1), (1,2,1,2,1,1,2,1,1))
    False

    '''
    pivot = -1
    for i in range(len(initial)):
        if initial[i] != final[i]:
            pivot = i
            break

    assert pivot > -1, '''
        No pivot between {} and {}'''.format(initial, final)
    assert initial[pivot + 1:] == final[pivot + 1:], '''
        More than one pivot between {} and {}'''.format(initial, final)

    coords_in_initial = all_coords(initial)
    coords_in_final_after_pivot = all_coords(final)[pivot+2:]
    coords_in_initial_after_pivot = coords_in_initial[pivot+2:]
    line_segments_up_to_pivot = line_segments(coords_in_initial, pivot)

    direction = rotation_direction(coords_in_initial,
                                   pivot,
                                   coords_in_final_after_pivot
                                   )

    pivot_point = coords_in_initial[pivot + 1]

    for point in coords_in_initial_after_pivot:
        arc = (pivot_point, point, direction)
        if any(intersects(arc, line) for line in line_segments_up_to_pivot):
            return False
    return True


def display(snake):
    '''Display a line diagram of the snake.

    Accepts a snake as either a tuple:

    (1, 1, 2, 0)

    or a string:

    "1120"

    '''
    snake = tuple(int(s) for s in snake)
    coords = all_coords(snake)

    turtle.clearscreen()
    t = turtle.Turtle()
    t.hideturtle()
    s = t.screen
    s.tracer(0)

    width, height = s.window_width(), s.window_height()

    x_min = min(coord[0] for coord in coords)
    x_max = max(coord[0] for coord in coords)
    y_min = min(coord[1] for coord in coords)
    y_max = max(coord[1] for coord in coords)
    unit_length = min(width // (x_max - x_min + 1),
                      height // (y_max - y_min + 1)
                      )

    origin_x = -(x_min + x_max) * unit_length // 2
    origin_y = -(y_min + y_max) * unit_length // 2

    pen_width = max(1, unit_length // 20)
    t.pensize(pen_width)
    dot_size = max(4, pen_width * 3)

    t.penup()
    t.setpos(origin_x, origin_y)
    t.pendown()

    t.forward(unit_length)
    for joint in snake:
        t.dot(dot_size)
        t.left((joint - 1) * 90)
        t.forward(unit_length)
    s.update()


def neighbours(origin, excluded=()):
    '''Return list of states reachable in one step.'''
    states = []
    for candidate in potential_neighbours(origin):
        if candidate not in excluded and reachable(origin, candidate):
            states.append(candidate)
    return states


def mirrored_or_backwards(candidates):
    '''Return set of states that are equivalent to a state in candidates.'''
    states = set()
    for candidate in candidates:
        mirrored = tuple(2 - joint for joint in candidate)
        backwards = candidate[::-1]
        mirrored_backwards = mirrored[::-1]
        states |= set((mirrored, backwards, mirrored_backwards))
    return states


def possible_snakes(snake):
    '''
    Return the set of possible arrangements of the given snake.

    >>> possible_snakes((1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1))
    {(1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1)}

    '''
    reached = set()
    candidates = set((snake,))

    while candidates:
        candidate = candidates.pop()
        reached.add(candidate)
        new_candidates = neighbours(candidate, reached)
        reached |= mirrored_or_backwards(new_candidates)
        set_of_new_candidates = set(new_candidates)
        reached |= set_of_new_candidates
        candidates |= set_of_new_candidates

    excluded = set()
    final_answers = set()
    while reached:
        candidate = reached.pop()
        if candidate not in excluded:
            final_answers.add(candidate)
            excluded |= mirrored_or_backwards([candidate])

    return final_answers


def straight_derived_snakes(length):
    '''Return the set of possible arrangements of a snake of this length.'''
    straight_line = (1,) * max(length-1, 0)
    return possible_snakes(straight_line)


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    import sys
    arguments = sys.argv[1:]
    if arguments:
        length = int(arguments[0])
    else:
        length = int(input('Enter the length of the snake:'))
    print(len(straight_derived_snakes(length)))

Resultados

Na minha máquina, a cobra mais longa que pode ser calculada em menos de 1 minuto é o comprimento 11 (ou 13 com PyPy *). Obviamente, isso é apenas uma pontuação provisória até descobrirmos qual é a pontuação oficial da máquina de Lembik.

Para comparação, eis os resultados para os primeiros valores de n:

 n | reachable orientations
-----------------------------
 0 | 1
 1 | 1
 2 | 2
 3 | 4
 4 | 9
 5 | 22
 6 | 56
 7 | 147
 8 | 388
 9 | 1047
10 | 2806
11 | 7600
12 | 20437
13 | 55313
14 | 148752
15 | 401629
16 | 1078746
17 | MemoryError (on my machine)

Informe-me se algum deles estiver incorreto.

Se você tiver um exemplo de um arranjo que não possa ser desdobrado, poderá usar a função neighbours(snake)para encontrar todos os arranjos alcançáveis ​​em uma etapa, como um teste do código. snakeé uma tupla de direções da junta (0 no sentido horário, 1 no reto, 2 no sentido anti-horário). Por exemplo (1,1,1) é uma cobra reta de comprimento 4 (com 3 articulações).

Visualização

Para visualizar uma cobra que tem em mente, ou qualquer uma das cobras retornados por neighbours, você pode usar a função display(snake). Isso aceita uma tupla como as outras funções, mas como não é usada pelo programa principal e, portanto, não precisa ser rápida, também aceita uma string, para sua conveniência.

display((1,1,2,0)) é equivalente a display("1120")

Como Lembik menciona nos comentários, meus resultados são idênticos ao OEIS A037245, que não leva em consideração as interseções durante a rotação. Isso ocorre porque, para os primeiros valores de n, não há diferença - todas as formas que não se interceptam podem ser alcançadas dobrando uma cobra reta. A correção do código pode ser testada chamando neighbours()-se uma cobra que não pode ser desdobrada sem interseção. Como não tem vizinhos, contribuirá apenas para a sequência OEIS, e não para esta. O menor exemplo que conheço é o tamanho 31 da serpente que Lembik mencionou, graças a David K :

(1,1,1,1,2,1,2,1,1,1,1,1,1,2,1,1,1,2,1,1,2,2,1,0,1,0,1,1,1,1)

display('111121211111121112112210101111') fornece a seguinte saída:

Dica: Se você redimensionar a janela e depois chamar novamente, a cobra será ajustada ao novo tamanho da janela.

Eu adoraria ouvir de quem tem um exemplo mais curto sem vizinhos. Suspeito que o menor exemplo desse tipo marque o menor n para o qual as duas seqüências diferem.

* Observe que cada incremento de n leva aproximadamente três vezes mais, portanto, aumentar de n = 11 para n = 13 requer quase 10 vezes o tempo. É por isso que o PyPy permite apenas aumentar n em 2, mesmo que seja consideravelmente mais rápido que o interpretador Python padrão.

C ++ 11 - quase funcionando :)

Depois de ler este artigo , coletei um pouco de sabedoria daquele cara que aparentemente trabalhou por 25 anos no problema menos complicado de contar caminhos evitáveis ​​em uma treliça quadrada.

#include <cassert>
#include <ctime>
#include <sstream>
#include <vector>
#include <algorithm> // sort

using namespace std;

// theroretical max snake lenght (the code would need a few decades to process that value)
#define MAX_LENGTH ((int)(1+8*sizeof(unsigned)))

#ifndef _MSC_VER
#ifndef QT_DEBUG // using Qt IDE for g++ builds
#define NDEBUG
#endif
#endif

#ifdef NDEBUG
inline void tprintf(const char *, ...){}
#else
#define tprintf printf
#endif

void panic(const char * msg)
{
    printf("PANIC: %s\n", msg);
    exit(-1);
}

// ============================================================================
// fast bit reversal
// ============================================================================
unsigned bit_reverse(register unsigned x, unsigned len)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16)) >> (32-len);
}

// ============================================================================
// 2D geometry (restricted to integer coordinates and right angle rotations)
// ============================================================================

// points using integer- or float-valued coordinates
template<typename T>struct tTypedPoint;

typedef int    tCoord;
typedef double tFloatCoord;

typedef tTypedPoint<tCoord> tPoint;
typedef tTypedPoint<tFloatCoord>  tFloatPoint;

template <typename T>
struct tTypedPoint {
    T x, y;

    template<typename U> tTypedPoint(const tTypedPoint<U>& from) : x((T)from.x), y((T)from.y) {} // conversion constructor

    tTypedPoint() {}
    tTypedPoint(T x, T y) : x(x), y(y) {}
    tTypedPoint(const tTypedPoint& p) { *this = p; }
    tTypedPoint operator+ (const tTypedPoint & p) const { return{ x + p.x, y + p.y }; }
    tTypedPoint operator- (const tTypedPoint & p) const { return{ x - p.x, y - p.y }; }
    tTypedPoint operator* (T scalar) const { return{ x * scalar, y * scalar }; }
    tTypedPoint operator/ (T scalar) const { return{ x / scalar, y / scalar }; }
    bool operator== (const tTypedPoint & p) const { return x == p.x && y == p.y; }
    bool operator!= (const tTypedPoint & p) const { return !operator==(p); }
    T dot(const tTypedPoint &p) const { return x*p.x + y * p.y; } // dot product  
    int cross(const tTypedPoint &p) const { return x*p.y - y * p.x; } // z component of cross product
    T norm2(void) const { return dot(*this); }

    // works only with direction = 1 (90° right) or -1 (90° left)
    tTypedPoint rotate(int direction) const { return{ direction * y, -direction * x }; }
    tTypedPoint rotate(int direction, const tTypedPoint & center) const { return (*this - center).rotate(direction) + center; }

    // used to compute length of a ragdoll snake segment
    unsigned manhattan_distance(const tPoint & p) const { return abs(x-p.x) + abs(y-p.y); }
};


struct tArc {
    tPoint c;                        // circle center
    tFloatPoint middle_vector;       // vector splitting the arc in half
    tCoord      middle_vector_norm2; // precomputed for speed
    tFloatCoord dp_limit;

    tArc() {}
    tArc(tPoint c, tPoint p, int direction) : c(c)
    {
        tPoint r = p - c;
        tPoint end = r.rotate(direction);
        middle_vector = ((tFloatPoint)(r+end)) / sqrt(2); // works only for +-90° rotations. The vector should be normalized to circle radius in the general case
        middle_vector_norm2 = r.norm2();
        dp_limit = ((tFloatPoint)r).dot(middle_vector);
        assert (middle_vector == tPoint(0, 0) || dp_limit != 0);
    }

    bool contains(tFloatPoint p) // p must be a point on the circle
    {
        if ((p-c).dot(middle_vector) >= dp_limit)
        {
            return true;
        }
        else return false;
    }
};

// returns the point of line (p1 p2) that is closest to c
// handles degenerate case p1 = p2
tPoint line_closest_point(tPoint p1, tPoint p2, tPoint c)
{
    if (p1 == p2) return{ p1.x, p1.y };
    tPoint p1p2 = p2 - p1;
    tPoint p1c =  c  - p1;
    tPoint disp = (p1p2 * p1c.dot(p1p2)) / p1p2.norm2();
    return p1 + disp;
}

// variant of closest point computation that checks if the projection falls within the segment
bool closest_point_within(tPoint p1, tPoint p2, tPoint c, tPoint & res)
{
    tPoint p1p2 = p2 - p1;
    tPoint p1c = c - p1;
    tCoord nk = p1c.dot(p1p2);
    if (nk <= 0) return false;
    tCoord n = p1p2.norm2();
    if (nk >= n) return false;
    res = p1 + p1p2 * (nk / n);
    return true;
}

// tests intersection of line (p1 p2) with an arc
bool inter_seg_arc(tPoint p1, tPoint p2, tArc arc)
{
    tPoint m = line_closest_point(p1, p2, arc.c);
    tCoord r2 = arc.middle_vector_norm2;
    tPoint cm = m - arc.c;
    tCoord h2 = cm.norm2();
    if (r2 < h2) return false; // no circle intersection

    tPoint p1p2 = p2 - p1;
    tCoord n2p1p2 = p1p2.norm2();

    // works because by construction p is on (p1 p2)
    auto in_segment = [&](const tFloatPoint & p) -> bool
    {
        tFloatCoord nk = p1p2.dot(p - p1);
        return nk >= 0 && nk <= n2p1p2;
    };

    if (r2 == h2) return arc.contains(m) && in_segment(m); // tangent intersection

    //if (p1 == p2) return false; // degenerate segment located inside circle
    assert(p1 != p2);

    tFloatPoint u = (tFloatPoint)p1p2 * sqrt((r2-h2)/n2p1p2); // displacement on (p1 p2) from m to one intersection point

    tFloatPoint i1 = m + u;
    if    (arc.contains(i1) && in_segment(i1)) return true;
    tFloatPoint i2 = m - u;
    return arc.contains(i2) && in_segment(i2);
}

// ============================================================================
// compact storage of a configuration (64 bits)
// ============================================================================
struct sConfiguration {
    unsigned partition;
    unsigned folding;

    explicit sConfiguration() {}
    sConfiguration(unsigned partition, unsigned folding) : partition(partition), folding(folding) {}

    // add a bend
    sConfiguration bend(unsigned joint, int rotation) const
    {
        sConfiguration res;
        unsigned joint_mask = 1 << joint;
        res.partition = partition | joint_mask;
        res.folding = folding;
        if (rotation == -1) res.folding |= joint_mask;
        return res;
    }

    // textual representation
    string text(unsigned length) const
    {
        ostringstream res;

        unsigned f = folding;
        unsigned p = partition;

        int segment_len = 1;
        int direction = 1;
        for (size_t i = 1; i != length; i++)
        {
            if (p & 1)
            {
                res << segment_len * direction << ',';
                direction = (f & 1) ? -1 : 1;
                segment_len = 1;
            }
            else segment_len++;

            p >>= 1;
            f >>= 1;
        }
        res << segment_len * direction;
        return res.str();
    }

    // for final sorting
    bool operator< (const sConfiguration& c) const
    {
        return (partition == c.partition) ? folding < c.folding : partition < c.partition;
    }
};

// ============================================================================
// static snake geometry checking grid
// ============================================================================
typedef unsigned tConfId;

class tGrid {
    vector<tConfId>point;
    tConfId current;
    size_t snake_len;
    int min_x, max_x, min_y, max_y;
    size_t x_size, y_size;

    size_t raw_index(const tPoint& p) { bound_check(p);  return (p.x - min_x) + (p.y - min_y) * x_size; }
    void bound_check(const tPoint& p) const { assert(p.x >= min_x && p.x <= max_x && p.y >= min_y && p.y <= max_y); }

    void set(const tPoint& p)
    {
        point[raw_index(p)] = current;
    }
    bool check(const tPoint& p)
    {
        if (point[raw_index(p)] == current) return false;
        set(p);
        return true;
    }

public:
    tGrid(int len) : current(-1), snake_len(len)
    {
        min_x = -max(len - 3, 0);
        max_x = max(len - 0, 0);
        min_y = -max(len - 1, 0);
        max_y = max(len - 4, 0);
        x_size = max_x - min_x + 1;
        y_size = max_y - min_y + 1;
        point.assign(x_size * y_size, current);
    }

    bool check(sConfiguration c)
    {
        current++;
        tPoint d(1, 0);
        tPoint p(0, 0);
        set(p);
        for (size_t i = 1; i != snake_len; i++)
        {
            p = p + d;
            if (!check(p)) return false;
            if (c.partition & 1) d = d.rotate((c.folding & 1) ? -1 : 1);
            c.folding >>= 1;
            c.partition >>= 1;
        }
        return check(p + d);
    }

};

// ============================================================================
// snake ragdoll 
// ============================================================================
class tSnakeDoll {
    vector<tPoint>point; // snake geometry. Head at (0,0) pointing right

    // allows to check for collision with the area swept by a rotating segment
    struct rotatedSegment {
        struct segment { tPoint a, b; };
        tPoint  org;
        segment end;
        tArc    arc[3];
        bool extra_arc; // see if third arc is needed

        // empty constructor to avoid wasting time in vector initializations
        rotatedSegment(){}
        // copy constructor is mandatory for vectors *but* shall never be used, since we carefully pre-allocate vector memory
        rotatedSegment(const rotatedSegment &){ assert(!"rotatedSegment should never have been copy-constructed"); }

        // rotate a segment
        rotatedSegment(tPoint pivot, int rotation, tPoint o1, tPoint o2)
        {
            arc[0] = tArc(pivot, o1, rotation);
            arc[1] = tArc(pivot, o2, rotation);
            tPoint middle;
            extra_arc = closest_point_within(o1, o2, pivot, middle);
            if (extra_arc) arc[2] = tArc(pivot, middle, rotation);
            org = o1;
            end = { o1.rotate(rotation, pivot), o2.rotate(rotation, pivot) };
        }

        // check if a segment intersects the area swept during rotation
        bool intersects(tPoint p1, tPoint p2) const
        {
            auto print_arc = [&](int a) { tprintf("(%d,%d)(%d,%d) -> %d (%d,%d)[%f,%f]", p1.x, p1.y, p2.x, p2.y, a, arc[a].c.x, arc[a].c.y, arc[a].middle_vector.x, arc[a].middle_vector.y); };

            if (p1 == org) return false; // pivot is the only point allowed to intersect
            if (inter_seg_arc(p1, p2, arc[0])) 
            { 
                print_arc(0);  
                return true;
            }
            if (inter_seg_arc(p1, p2, arc[1]))
            { 
                print_arc(1); 
                return true;
            }
            if (extra_arc && inter_seg_arc(p1, p2, arc[2])) 
            { 
                print_arc(2);
                return true;
            }
            return false;
        }
    };

public:
    sConfiguration configuration;
    bool valid;

    // holds results of a folding attempt
    class snakeFolding {
        friend class tSnakeDoll;
        vector<rotatedSegment>segment; // rotated segments
        unsigned joint;
        int direction;
        size_t i_rotate;

        // pre-allocate rotated segments
        void reserve(size_t length)
        {
            segment.clear(); // this supposedly does not release vector storage memory
            segment.reserve(length);
        }

        // handle one segment rotation
        void rotate(tPoint pivot, int rotation, tPoint o1, tPoint o2)
        {
            segment.emplace_back(pivot, rotation, o1, o2);
        }
    public:
        // nothing done during construction
        snakeFolding(unsigned size)
        {
            segment.reserve (size);
        }
    };

    // empty default constructor to avoid wasting time in array/vector inits
    tSnakeDoll() {}

    // constructs ragdoll from compressed configuration
    tSnakeDoll(unsigned size, unsigned generator, unsigned folding) : point(size), configuration(generator,folding)
    {
        tPoint direction(1, 0);
        tPoint current = { 0, 0 };
        size_t p = 0;
        point[p++] = current;
        for (size_t i = 1; i != size; i++)
        {
            current = current + direction;
            if (generator & 1)
            {
                direction.rotate((folding & 1) ? -1 : 1);
                point[p++] = current;
            }
            folding >>= 1;
            generator >>= 1;
        }
        point[p++] = current;
        point.resize(p);
    }

    // constructs the initial flat snake
    tSnakeDoll(int size) : point(2), configuration(0,0), valid(true)
    {
        point[0] = { 0, 0 };
        point[1] = { size, 0 };
    }

    // constructs a new folding with one added rotation
    tSnakeDoll(const tSnakeDoll & parent, unsigned joint, int rotation, tGrid& grid)
    {
        // update configuration
        configuration = parent.configuration.bend(joint, rotation);

        // locate folding point
        unsigned p_joint = joint+1;
        tPoint pivot;
        size_t i_rotate = 0;
        for (size_t i = 1; i != parent.point.size(); i++)
        {
            unsigned len = parent.point[i].manhattan_distance(parent.point[i - 1]);
            if (len > p_joint)
            {
                pivot = parent.point[i - 1] + ((parent.point[i] - parent.point[i - 1]) / len) * p_joint;
                i_rotate = i;
                break;
            }
            else p_joint -= len;
        }

        // rotate around joint
        snakeFolding fold (parent.point.size() - i_rotate);
        fold.rotate(pivot, rotation, pivot, parent.point[i_rotate]);
        for (size_t i = i_rotate + 1; i != parent.point.size(); i++) fold.rotate(pivot, rotation, parent.point[i - 1], parent.point[i]);

        // copy unmoved points
        point.resize(parent.point.size()+1);
        size_t i;
        for (i = 0; i != i_rotate; i++) point[i] = parent.point[i];

        // copy rotated points
        for (; i != parent.point.size(); i++) point[i] = fold.segment[i - i_rotate].end.a;
        point[i] = fold.segment[i - 1 - i_rotate].end.b;

        // static configuration check
        valid = grid.check (configuration);

        // check collisions with swept arcs
        if (valid && parent.valid) // ;!; parent.valid test is temporary
        {
            for (const rotatedSegment & s : fold.segment)
            for (size_t i = 0; i != i_rotate; i++)
            {
                if (s.intersects(point[i+1], point[i]))
                {
                    //printf("! %s => %s\n", parent.trace().c_str(), trace().c_str());//;!;
                    valid = false;
                    break;
                }
            }
        }
    }

    // trace
    string trace(void) const
    {
        size_t len = 0;
        for (size_t i = 1; i != point.size(); i++) len += point[i - 1].manhattan_distance(point[i]);
        return configuration.text(len);
    }
};

// ============================================================================
// snake twisting engine
// ============================================================================
class cSnakeFolder {
    int length;
    unsigned num_joints;
    tGrid grid;

    // filter redundant configurations
    bool is_unique (sConfiguration c)
    {
        unsigned reverse_p = bit_reverse(c.partition, num_joints);
        if (reverse_p < c.partition)
        {
            tprintf("P cut %s\n", c.text(length).c_str());
            return false;
        }
        else if (reverse_p == c.partition) // filter redundant foldings
        {
            unsigned first_joint_mask = c.partition & (-c.partition); // insulates leftmost bit
            unsigned reverse_f = bit_reverse(c.folding, num_joints);
            if (reverse_f & first_joint_mask) reverse_f = ~reverse_f & c.partition;

            if (reverse_f > c.folding)
            {
                tprintf("F cut %s\n", c.text(length).c_str());
                return false;
            }
        }
        return true;
    }

    // recursive folding
    void fold(tSnakeDoll snake, unsigned first_joint)
    {
        // count unique configurations
        if (snake.valid && is_unique(snake.configuration)) num_configurations++;

        // try to bend remaining joints
        for (size_t joint = first_joint; joint != num_joints; joint++)
        {
            // right bend
            tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint,1).text(length).c_str());
            fold(tSnakeDoll(snake, joint, 1, grid), joint + 1);

            // left bend, except for the first joint
            if (snake.configuration.partition != 0)
            {
                tprintf("%s -> %s\n", snake.configuration.text(length).c_str(), snake.configuration.bend(joint, -1).text(length).c_str());
                fold(tSnakeDoll(snake, joint, -1, grid), joint + 1);
            }
        }
    }

public:
    // count of found configurations
    unsigned num_configurations;

    // constructor does all the work :)
    cSnakeFolder(int n) : length(n), grid(n), num_configurations(0)
    {
        num_joints = length - 1;

        // launch recursive folding
        fold(tSnakeDoll(length), 0);
    }
};

// ============================================================================
// here we go
// ============================================================================
int main(int argc, char * argv[])
{
#ifdef NDEBUG
    if (argc != 2) panic("give me a snake length or else");
    int length = atoi(argv[1]);
#else
    (void)argc; (void)argv;
    int length = 12;
#endif // NDEBUG

    if (length <= 0 || length >= MAX_LENGTH) panic("a snake of that length is hardly foldable");

    time_t start = time(NULL);
    cSnakeFolder snakes(length);
    time_t duration = time(NULL) - start;

    printf ("Found %d configuration%c of length %d in %lds\n", snakes.num_configurations, (snakes.num_configurations == 1) ? '\0' : 's', length, duration);
    return 0;
}

Construindo o executável

Compile com eu uso o MinGW no Win7 com g ++ 4.8 para compilações "linux", portanto a portabilidade não é 100% garantida.g++ -O3 -std=c++11

Também funciona (mais ou menos) com um projeto MSVC2013 padrão

Ao definir indefinidamente NDEBUG, você obtém traços de execução de algoritmos e um resumo das configurações encontradas.

Performances

com ou sem tabelas de hash, o compilador da Microsoft executa miseravelmente: a compilação g ++ é 3 vezes mais rápida .

O algoritmo praticamente não usa memória.

Como a verificação de colisão é aproximadamente em O (n), o tempo de computação deve ser em O (nk ⁿ ), com k ligeiramente menor que 3.
No meu [email protected], n = 17 leva cerca de 1:30 (cerca de 2 milhões cobras / minuto).

Não terminei de otimizar, mas não esperaria mais do que um ganho de x3, portanto, basicamente, espero alcançar talvez n = 20 em uma hora ou n = 24 em um dia.

Atingir a primeira forma inconstante conhecida (n = 31) levaria entre alguns anos e uma década, assumindo que não houvesse falta de energia.

Contando formas

Uma cobra de tamanho N tem juntas N-1 .
Cada articulação pode ser deixada reta ou dobrada para a esquerda ou direita (3 possibilidades).
O número de possíveis dobras é, portanto, 3 ^N-1 .
As colisões reduzirão um pouco esse número, de modo que o número real esteja próximo de 2,7 ^N-1

No entanto, muitas dessas dobras levam a formas idênticas.

duas formas são idênticas se houver uma rotação ou simetria que possa transformar uma na outra.

Vamos definir um segmento como qualquer parte reta do corpo dobrado.
Por exemplo, uma cobra de tamanho 5 dobrada na 2ª junta teria 2 segmentos (um com 2 unidades de comprimento e o segundo com 3 unidades).
O primeiro segmento será nomeado como cabeça e a última cauda .

Por convenção, orientamos a cabeça das cobras horizontalmente com o corpo apontando para a direita (como na primeira figura do OP).

Designamos uma figura com uma lista de comprimentos de segmentos assinados, com comprimentos positivos indicando uma dobra à direita e negativos uma dobra à esquerda.
O comprimento inicial é positivo por convenção.

Separando segmentos e dobras

Se considerarmos apenas as diferentes maneiras pelas quais uma cobra de comprimento N pode ser dividida em segmentos, terminamos com uma repartição idêntica às composições de N.

Usando o mesmo algoritmo mostrado na página da wiki, é fácil gerar todas as 2 partições ^N-1 possíveis da cobra.

Cada partição, por sua vez, gera todas as dobras possíveis aplicando dobras à esquerda ou à direita em todas as suas juntas. Uma dessas dobras será chamada de configuração .

Todas as partições possíveis podem ser representadas por um número inteiro de bits N-1, onde cada bit representa a presença de uma junta. Vamos chamar esse número inteiro de gerador .

Partições de poda

Observando que dobrar uma partição da cabeça para baixo é equivalente a dobrar a partição simétrica da cauda para cima, podemos encontrar todos os pares de partições simétricas e eliminar uma em duas.
O gerador de uma partição simétrica é o gerador da partição escrito em ordem de bits reversa, o que é trivialmente fácil e barato de detectar.

Isso eliminará quase metade das partições possíveis, com exceção das partições com geradores "palíndricos" que são mantidos inalterados pela reversão de bits (por exemplo, 00100100).

Cuidando de simetrias horizontais

Com nossas convenções (uma cobra começa a apontar para a direita), a primeira dobra aplicada à direita produzirá uma família de dobras que serão simétricas horizontais daquelas que diferem apenas na primeira dobra.

Se decidirmos que a primeira curva sempre estará à direita, eliminaremos toda a simetria horizontal de uma só vez.

Limpando os palíndromos

Esses dois cortes são eficientes, mas não o suficiente para cuidar desses palíndromos traquinas.
A verificação mais completa no caso geral é a seguinte:

considere uma configuração C com uma partição palindrômica.

• se invertermos todas as curvas em C, terminamos com uma simétrica horizontal de C.
• se invertermos C (aplicando curvas da cauda para cima), obteremos a mesma figura girada para a direita
• se invertermos e invertermos C, obteremos a mesma figura girada para a esquerda.

Poderíamos verificar todas as novas configurações contra as outras 3. No entanto, como já geramos apenas configurações começando com uma curva à direita, temos apenas uma simetria possível para verificar:

• o C invertido começará com uma curva à esquerda, que por construção é impossível duplicar
• fora das configurações invertida e invertida, somente uma começará com uma curva à direita.
  Essa é a única configuração que podemos duplicar.

Eliminando duplicatas sem armazenamento

Minha abordagem inicial foi armazenar todas as configurações em uma enorme tabela de hash, para eliminar duplicatas, verificando a presença de uma configuração simétrica previamente calculada.

Graças ao artigo acima mencionado, ficou claro que, como as partições e as dobras são armazenadas como campos de bits, elas podem ser comparadas como qualquer valor numérico.
Portanto, para eliminar um membro de um par simétrico, você pode simplesmente comparar os dois elementos e manter sistematicamente o menor (ou o maior, como desejar).

Assim, testar uma configuração para duplicação equivale a calcular a partição simétrica e, se ambas são idênticas, a dobra. Nenhuma memória é necessária.

Ordem de geração

Claramente, a verificação de colisão será a parte que mais consome tempo; portanto, reduzir esses cálculos é uma grande economia de tempo.

Uma solução possível é ter uma "cobra ragdoll" que começará em uma configuração plana e será dobrada gradualmente, para evitar recalcular toda a geometria da cobra para cada configuração possível.

Ao escolher a ordem na qual as configurações são testadas, para que no máximo um boneco de pano seja armazenado para cada número total de juntas, podemos limitar o número de instâncias a N-1.

Eu uso uma varredura recursiva do saquê da cauda para baixo, adicionando uma única junta em cada nível. Assim, uma nova instância de ragdoll é construída sobre a configuração pai, com uma única curva adicional.

Isso significa que as dobras são aplicadas em uma ordem seqüencial, o que parece ser suficiente para evitar auto-colisões em quase todos os casos.

Quando a autolisão é detectada, as dobras que levam ao movimento ofensivo são aplicadas em todas as ordens possíveis até que a dobra legítima seja encontrada ou todas as combinações sejam esgotadas.

Verificação estática

Antes de pensar em partes móveis, achei mais eficiente testar a forma final estática de uma cobra para auto-interseções.

Isso é feito desenhando a cobra em uma grade. Cada ponto possível é plotado da cabeça para baixo. Se houver uma auto-interseção, pelo menos um par de pontos cairá no mesmo local. Isso requer exatamente N plotagens para qualquer configuração de cobra, por um tempo O (N) constante.

A principal vantagem dessa abordagem é que apenas o teste estático simplesmente seleciona caminhos válidos de auto-evitação em uma treliça quadrada, o que permite testar todo o algoritmo inibindo a detecção dinâmica de colisões e assegurando que encontramos a contagem correta desses caminhos.

Verificação dinâmica

Quando uma cobra se dobra em torno de uma junta, cada segmento girado varre uma área cuja forma é qualquer coisa, menos trivial.
Claramente, você pode verificar colisões testando a inclusão em todas essas áreas varridas individualmente. Uma verificação global seria mais eficiente, mas, dada a complexidade das áreas, não consigo pensar em nenhuma delas (exceto talvez usar uma GPU para desenhar todas as áreas e executar uma verificação de ocorrência global).

Como o teste estático cuida das posições inicial e final de cada segmento, basta verificar as interseções com os arcos varridos por cada segmento rotativo.

Após uma discussão interessante com o trichoplax e um pouco de JavaScript para me orientar, criei este método:

Para tentar colocar em poucas palavras, se você chamar

• C o centro de rotação,
• S um segmento rotativo de comprimento e direção arbitrários que não contém C ,
• L a linha prolongando S
• H a linha ortogonal a L passando por C ,
• I a interseção de L e H ,

_{(fonte: free.fr )}

Para qualquer segmento que não contenha I , a área varrida é vinculada por 2 arcos (e 2 segmentos já atendidos pela verificação estática).

Se eu cair dentro do segmento, o arco varrido por eu também deverá ser levado em consideração.

Isso significa que podemos verificar cada segmento imóvel em relação a cada segmento rotativo com 2 ou 3 interseções segmento-arco

Usei a geometria vetorial para evitar completamente as funções trigonométricas.
As operações de vetor produzem código compacto e (relativamente) legível.

A interseção segmento a arco requer um vetor de ponto flutuante, mas a lógica deve ser imune a erros de arredondamento.
Encontrei esta solução elegante e eficiente em um post obscuro no fórum. Eu me pergunto por que não é mais amplamente divulgado.

Funciona?

Inibir a detecção dinâmica de colisão produz os caminhos corretos de auto-evitação, que contam até n = 19, por isso estou bastante confiante de que o layout global funcione.

A detecção dinâmica de colisão produz resultados consistentes, embora a verificação de dobras em ordem diferente esteja ausente (por enquanto).
Como conseqüência, o programa conta cobras que podem ser dobradas da cabeça para baixo (ou seja, com as juntas dobradas em ordem crescente da distância da cabeça).