Generation of random latin squares step by step and graphically

Abstract

In order to generate random Latin squares of order 256, the Jacobson and Matthews’ algorithm has been implemented in Java. Clear and efficient data structures (for squares and incidence cubes) have been modeled and the ±1-moves of their method have been implemented. This ensures that, in a polynomial number of steps (O(<i>n</i>3)), the algorithm finishes with a Latin square as a result that is approximately uniformly distributed. As an additional contribution to the subject, a step-by-step graphical generation using OpenGL (Open Graphic Library) is provided, which could be used to explain the algorithm, understand it or simply draw the resulting Latin squares as incidence cubes. The main goal of the present work is to document the implementation of the algorithm and make it public on the Internet, since no standard implementation is freely available.