The snake-in-the-box problem in graph theory and coding theory 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 must never travel to a corner which has been marked unusable.
In other words, a snake is a connected open path in the hypercube where each node has exactly two neighbors that are also in the path, with the exception of the first and last nodes, which each has only one neighbor in the path. The rule for generating a snake is that a node in the hypercube may be visited if it is connected to the current node and it is not a neighbor of any previously visited node in the snake, other than the current node.
