Snake In The Box

Description
The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner after it has been marked unusable.

Imagine a 3-dimensional cube with corners labeled with three digit numbers of the x,y,z coordinates: 000, 001, 011, 010, 100, 101, 111, 110. The longest tour of this cube, given the rules above, follows the path 000 -> 001 -> 011 -> 111 -> 110 for a length of 4.

As you may imagine, as the dimensionality of the hypercube grows the complexity also grows. For dimensions above 9 there is no concrete answer, only longest lengths found so far.

Input Description
You'll be given a single digit n per line indicating the dimensionality of the cube on which to operate. Example:

3
Output Description
Your program should emit the length of the longest edge traversal path it can find following the constraints above. You should also emit the corners toured - consider using the labeling system from above. Example:

3 = 000 -> 001 -> 011 -> 111 -> 110
Challenge Input
4
6
8
The 8D hypercube will really stress the efficiency of your algorithm.


Solution
in Java

class Colony {
    private int dimension;
    private Node start;
    IntList best;

    Colony(int dimension) {
        this.dimension = dimension;
        start = new Node(dimension, new BitSet(dimension));
        HashMap<Integer, Node> nodes = new HashMap<>();
        nodes.put(start.id, start);
        int max = (int) Math.pow(2, dimension);
        // Create nodes in graph
        for (int i = 1; i < max; i++) {
            BitSet id = new BitSet(dimension);
            String bitString = Long.toBinaryString(i);
            if (bitString.length() < dimension) {
                char[] fill = new char[dimension - bitString.length()];
                Arrays.fill(fill, '0');
                bitString = new String(fill) + bitString;
            } else bitString = bitString.substring(bitString.length() - dimension);
            bitString = new StringBuilder(bitString).reverse().toString();
            for (int j = 0; j < dimension; j++)
                id.set(j, bitString.charAt(j) == '1');
            nodes.put(i, new Node(dimension, id));
        }
        // Add edges in graph
        for (Node n : nodes.values()) {
            BitSet id = n.bits;
            for (int i = 0; i < dimension; i++) {
                boolean b = id.get(i);
                id.set(i, !b);
                nodes.get(n.createId()).addEdge(n, i);
                id.set(i, b);
            }
        }
    }

    void work(int iterations, int attempts){
        IntList bestAnt = new IntList(200),
                bestInGen = new IntList(200),
                currAnt = new IntList(200);
        for(int ignore = 0; ignore < iterations; ignore++) {
            bestInGen.clear();
            for(int ignored = 0; ignored < attempts; ignored++) {
                currAnt.clear();
                findPath(currAnt);
                if(bestInGen.size() < currAnt.size())
                    bestInGen.copy(currAnt);
            }
            applyPath(bestInGen);
            if(bestAnt.size() < bestInGen.size())
                bestAnt.copy(bestInGen);
        }

        this.best = bestAnt;
    }

    private void applyPath(IntList path){
        int length = path.size();
        Node at = start;
        for (int i = 0; i < length; i++) {
            int e = path.get(i);
            at.alter(e);
            at = at.edges[e];
            at.alter(e);
        }
    }

    private void findPath(IntList curr) {
        HashSet<Integer> blocked = new HashSet<>();
        Node at = start, next = null;
        blocked.add(at.id);

        do {
            double odds = 1.0;
            for (int i = 0; i < dimension; i++)
                if (blocked.contains(at.edges[i].id)) odds -= at.odds[i];
            odds *= Math.random();

            boolean looking = true;

            for (int i = 0; i < dimension; i++) {
                if (blocked.contains(at.edges[i].id)) continue;
                else blocked.add(at.edges[i].id);
                if (!looking) continue;
                odds -= at.odds[i];
                if (odds <= 0) {
                    curr.add(i);
                    next = at.edges[i];
                    looking = false;
                }
            }

            if(!looking) at = next;

        } while (Arrays.stream(at.edges)
                .filter(node -> !blocked.contains(node.id))
                .map(res -> true).findFirst().orElse(false));
    }
}

class Node {
    final BitSet bits;
    final int id;
    final Node[] edges;
    final double[] odds;

    Node(int dimesions, BitSet id) {
        this.bits = id;
        this.id = createId();
        edges = new Node[dimesions];
        odds = new double[dimesions];
        double odd = 1.0 / dimesions;
        Arrays.fill(odds, odd);
    }

    void addEdge(Node node, int i) {
        if (edges[i] != null) return;
        edges[i] = node;
        node.edges[i] = this;
    }

    void alter(int edge) {
        double unassigned = 1;
        for (int i = 0; i < odds.length; i++) {
            if (i != edge) {
                double taking = odds[i] * 0.01;
                odds[edge] += taking;
                odds[i] -= taking;
            }
            unassigned -= odds[i];
        }
        odds[edge] += unassigned;
    }

    int createId() {
        return bits.length() > 0 ? (int) bits.toLongArray()[0] : 0;
    }

    public String toString() {
        String res = String.valueOf(Integer.toBinaryString(id));
        char[] arr = new char[edges.length - res.length()];
        Arrays.fill(arr, '0');
        return new String(arr) + res;
    }
}

class IntList {
    private int size;
    private int[] list;

    IntList(int length){
        list = new int[length];
    }

    void add(int e) {
        list[size++] = e;
    }

    void copy(IntList other) {
        this.size = other.size;
        System.arraycopy(other.list, 0, list, 0, size);
    }

    void clear() {
        size = 0;
    }

    int size(){ return size; }

    int get(int i) {
        return list[i];
    }
}

Input

public static void main(String... args) {
    for (int i = 1; i <= 9; i++) {
        Time.init("Dimension: " + i);
        Colony colony = new Colony(i);
        colony.work(1000, 200);
        Time.write("Dimension: " + i);
        Note.writenl("Dimension: " + i + " -> " + (colony.best.size()));
    }
}

Output

Dimension: 1 took 0.106 seconds
Dimension: 1 -> 1
Dimension: 2 took 0.161 seconds
Dimension: 2 -> 2
Dimension: 3 took 0.128 seconds
Dimension: 3 -> 4
Dimension: 4 took 0.333 seconds
Dimension: 4 -> 7
Dimension: 5 took 0.539 seconds
Dimension: 5 -> 13
Dimension: 6 took 0.942 seconds
Dimension: 6 -> 26
Dimension: 7 took 1.899 seconds
Dimension: 7 -> 50 (usually hits 45-48)
Dimension: 8 took 4.038 seconds
Dimension: 8 -> 77 (best so far has been 92)
Dimension: 9 took 8.174 seconds
Dimension: 9 -> 126 (reeally far off)