P. Orland

 L. Fagan

M. Tarquini

D. Passaro

M. Manko

E. Heyes

A. Gruen

G. Butbaia

J. Tan

S. Gukov

Induced paths in hypercubes, or ‘snakes’, of record length are found using novel search methods built for difficult long-horizon problems.

The snake-in-the-box problem, introduced in 1958, seeks the longest induced path, or 'snake', in a hypercube. This is a long-horizon extremal combinatorial problem with very sparse rewards. By relaxing the search to collections of disjoint snakes, we break the longstanding record in order 9, and establish new lower bounds in orders 10-13. We also develop a learned search method to generate diverse snakes tabula rasa.

The snake-in-the-box problem asks for a longest induced path in the hypercube graph Qn. We find a length-191 snake in dimension n=9, the lowest dimension where the maximum is unknown, improving the previous record of 190 that had stood for 14 years. We also establish new lower bounds in dimensions 10-13. To find these records, we introduce snakepits, collections of disjoint snakes, to expand the search space and open new routes between snakes. This motivates our new Snakepit-in-the-Box benchmark, which seeks maximal edge counts when allowing multiple components. Finally, we introduce Beam Anchor, a search-supervised learned constructor algorithm that finds 100 inequivalent length-190 snakes in dimension 9.

New snake-in-the-box records via snakepit surgery and learned construction

Record-breaking snakes