Algorithms for interactive Sprouts
Cameron Browne · Theoretical Computer Science · 2016
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.