This project establishes new lower bounds (new longest snakes and coils) for the Snake-In-The-Box problem in a hypercube of nine dimensions. The lengths obtained exceed any reported in the current literature. Three important methods or tools were used: the Prolog programming language, a Genetic Algorithm, and traditional search including depth limited and a heuristic search called the Narrowest Path Heuristic. These methods were used in conjunction and expand on others previously tried. The Snake-In-The-Box problem consists of finding the longest simple non-cyclical path (a snake) or the longest simple cyclical path (a coil) in an d-dimensional hypercube without chords. The longer the Snake the better. The Snake-In-The-Box problem has a range of practical applications including error detection in analog-to-digital conversion and encryption technology. Studying computational approaches to this constraint satisfaction problem and attempting to find good solutions (long snakes or coils) has theoretical value as well. The Snake Problem belongs to a set of problems known to be non-deterministically polynomial (NP). Due to exponential and explosive growth in the search space, finding solutions to such problems is notoriously difficcult. Attempts to find long snakes in hypercubes of dimensions higher than seven have since required non-traditional or heuristic search. Evaluating new approaches to solving a constraint satisfaction problem in NP has theoretical import to other similar problems, and perhaps all problems that are NP.