Algorithms for interactive Sprouts

The simplicity of the pen-and-paper game Sprouts hides a surprising combinatorial complexity. We describe an optimisation called boundary matching that accommodates this complexity to allow move generation for Sprouts games of arbitrary size at interactive speeds. This extended version of the paper also describes methods for plotting and visualising Sprouts moves, using a conforming Delaunay triangulation of the game's underlying geometry.