Completing Latin Squares
Library Home || Full Table of Contents || Library Help
|Ivars Peterson (MathTrek)|
|Using only the numbers 1, 2, 3, and 4, arrange four sets of these numbers into a four-by-four array so that no column or row contains the same two numbers. The result is known as a Latin square... in Latin squares of order 4, each row (and each column) is a permutation of four distinct numbers (or symbols). Latin squares are linked to algebraic objects known as quasigroups. The so-called quasigroup completion problem concerns a table that is correctly but only partially filled in. The question is whether the remaining blanks in the table can be filled in to obtain a complete Latin square (or a proper quasigroup multiplication table). Computer scientists have proved that the quasigroup completion problem belongs to a category of difficult computational problems described as NP-complete. As the number of elements, n, increases, a computerís solution time grows exponentially in the worst case.|
|Levels:||High School (9-12), College|
|Math Topics:||Group Theory, Computer Science|
© 1994- The Math Forum at NCTM. All rights reserved.