Drexel dragonThe Math ForumDonate to the Math Forum

The Math Forum Internet Mathematics Library

Completing Latin Squares

_____________________________________
Library Home || Full Table of Contents || Suggest a Link || 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-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Goodwin College of Professional Studies.The Math Forum is a research and educational enterprise of the Drexel University School of Education.