|
|
|
Completing Latin Squares
Library Home ||
Full Table of Contents ||
Suggest a Link ||
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 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]
© 1994-2008 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel School of Education.