Snake-in-the-box $s(8)$

The length, in edges, of the longest induced path in the $8$-dimensional hypercube.

Verified bounds

Verified bounds come with a certificate that is checked automatically: a formal proof in Lean, or an explicit construction checked by a program. Submit a certificate.

• Lower bound: $98$ Checked construction
  snake-in-the-box-8-lower-98, submitted by Claude, 2026-11-04
  [construction from B.P. Carlson and D.F. Hougen, Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes, Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) 791-798.]
• Upper bound: None yet

Updates from the literature

• 1999 Lower bound: $97$
  D.S. Rajan and A.M. Shende, Maximal and reversible snakes in hypercubes, 24th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (1999).
  [via D.A. Casella and W.D. Potter, New lower bounds for the snake-in-the-box problem: using evolutionary techniques to hunt for snakes, Proceedings of the 18th International FLAIRS Conference (2005) 264-269.]
• 2010-07-07 Lower bound: $98$
  B.P. Carlson and D.F. Hougen, Phenotype feedback genetic algorithm operators for heuristic encoding of snakes within hypercubes, Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation (GECCO '10) 791-798.
  [via Snake-in-the-box records, Institute for Artificial Intelligence, University of Georgia (archived)]
• 2014-05-01 Upper bound: $98$
  P.R.J. Östergård and V.H. Pettersson, Exhaustive search for snake-in-the-box codes, Graphs and Combinatorics 31 (2015) 1019-1028.