In this paper we propose a construction that generates spatially balanced Latin squares (SBLSs) in polynomial time. These structures are central to the design of agronomic experiments, as they avoid biases that are otherwise unintentionally introduced due to spatial auto-correlation. Previous approaches were able to generate SBLSs of order up to 35 and required about two weeks of computation. Our algorithm runs in O(n2) and generates SBLSs of arbitrary order n where 2n + 1 is prime. For example, this algorithm generates a SBLS of order 999 in a fraction of a second.