de Bruijn Torus

A de Bruijn torus is a rectangular array over a finite alphabet, with rows and columns read cyclically, in which each possible array over that alphabet occurs exactly once as a contiguous window (Kreitzer et al. 2024). Reading past the last row or column continues at the first, so opposite boundaries are identified as on a torus. This is a two-dimensional generalization of a de Bruijn sequence.

For an alphabet of size , an de Bruijn torus with windows necessarily satisfies

since there is one window starting at each position and possible windows.

For example, the binary array

contains all 16 possible binary windows exactly once when read with wraparound (Kreitzer et al. 2024).