Drexel dragonThe Math Forum

The Math Forum Internet Mathematics Library

Completing Latin Squares

Library Home || Full Table of Contents || Library Help

Visit this site: http://www.maa.org/mathland/mathtrek_5_8_00.html

Author:Ivars Peterson (MathTrek)
Description: 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
Languages: English
Resource Types: Articles
Math Topics: Group Theory, Computer Science

[Privacy Policy] [Terms of Use]

Home || The Math Library || Quick Reference || Search || Help

© 1994- The Math Forum at NCTM. All rights reserved.