Fractal Word Search: How Deep to Delve

Abstract

We look at the puzzle In the Details, which appeared in the 2013 MIT Mystery Hunt and which gained fame as the fractal word search. This seemingly impossible puzzle, whose solution could not fit the memory of a modern computer if the puzzle were solved using a brute-force approach, requires an understanding of its fundamental structure to be cracked. In this paper, we study fractal word searches in a general setting, where we consider one- and two-dimensional word searches with alphabets of any length and replacement rules of any size. We prove that the puzzle is solvable within a finite number of steps under this generalization and give an explicit upper bound on the latest level on which a word of a given length can appear for the first time in a given direction.