Circuit codes and the Snake-in-the-Box Problem

The article is based on the materials of the plenary talk “Circuit Codes and the Snake-in-the-Box Problem: Modern State, Generalizations, and Applications” presented at the XVII International Conference “Problems of Theoretical Cybernetics”, Kazan Federal University, June, 2014. In this paper we discuss the current state of research on this well-known combinatorial problem and its generalizations. A survey on the lower and upper bounds for the maximal length of a snake and a cycle in the $n$-dimensional Boolean cube is given. We compare the known methods for construction of snakes and the upper bounds for their lengths. A table of strict values of the maximal lengths for $n<9$ and the bounds for $n=10,11$ and $12$ is presented. A simple construction for a snake of length $\mathrm{const}\cdot2^n$ with $\mathrm{const}>0.26$ is given. We analyze the properties of the constructions which influence the value of the constant. A survey of the results on circuit codes (that are generalizations of snakes) is given. Several unsolved tasks are considered.