Abstract
One of Claude Shannon鈥檚 best remembered 鈥渢oys鈥 was his maze-solving machine, created by partitions on a rectangular grid. A mechanical mouse was started at one point in the maze with the task of finding cheese at another point. Relays under the board guided successive moves, each of which were taken in the first open counterclockwise direction from the previous move. In belated honor of Shannon鈥檚 centenary and of amnesia in the mouse at age 70, we compare this deterministic search strategy with a random search requiring no memory. For simplicity, the rectangular grid with partitions is replaced by a finite connected graph. A maze is then a graph with some given destination node. The worst case required number of steps to find the cheese for deterministic searches and the expected number for random searches are remarkably similar, each being, for example,聽|E2||E2| taken over all graphs of聽|E||E| edges. Finally, we demonstrate a simple improvement to the above algorithms that generates an Eulerian cycle on the directed edges of聽GG, i.e., a walk on聽GG of聽2|E|2|E| steps that traverses each edge in聽GG exactly once in each direction before returning to the starting point.