The P300 brain-computer interface (BCI) using electroencephalogram (EEG) signals can allow amyotrophic lateral sclerosis (ALS) patients to instruct computers to perform tasks. To strengthen the P300 response and increase classification accuracy, we proposed an experimental design where characters are intensified according to orthogonal Latin square pairs. These orthogonal Latin square pairs satisfy certain distance constraint so that neighboring characters are not intensified simultaneously. However, it is unknown whether such distance-constrained, orthogonal Latin square pairs actually exist. In this paper, we show that for every matrix size commonly used in P300 BCI, thousands to millions of such distance-constrained, orthogonal Latin square pairs can be systematically and efficiently constructed and are sufficient for the purpose of being used in P300 BCI. © Springer Science+Business Media, LLC 2010.