Completing Latin Squares
Library Home 
Full Table of Contents 
Library Help
http://www.maa.org/mathland/mathtrek_5_8_00.html  


Ivars Peterson (MathTrek)  
Using only the numbers 1, 2, 3, and 4, arrange four sets of these numbers into a fourbyfour 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 socalled 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 NPcomplete. As the number of elements, n, increases, a computer’s solution time grows exponentially in the worst case.  


Levels:  High School (912), College 
Languages:  English 
Resource Types:  Articles 
Math Topics:  Group Theory, Computer Science 
[Privacy Policy] [Terms of Use]
© 1994 The Math Forum at NCTM. All rights reserved.
http://mathforum.org/