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.