We present several models for the generation of totally spatially-balanced Latin squares. While it is unclear at this stage how the local search approach could be tuned to give optimal solutions for orders greater than 9, our results with CP based models were very encouraging; We could find totally spatially-balanced Latin instances up to order 18. Moreover, our different CP based models provided us with good insights about the structure of the problem. In fact, we conjecture that totally spatially-balanced Latin squares can be generated using a polynomial time construction, based on a representation that exploits the underlying traversal structure of Latin squares corresponding to matchings in bipartite graphs, as well as the duality between rows, columns, and symbols in a balanced Latin square. We also conjecture that, for certain orders, spatially-balanced Latin squares can be generated by means of composition, in polynomial time. If some symbols are pre-assigned to specific cells of the Latin square, our conjecture is that the problem of deciding if a partially filled Latin square can be completed into a balanced Latin square is an NP-complete problem. We hope that our results will further stimulate research on this interesting and challenging problem.
展开▼
