Latin square

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Here is an example:

 A B C C A B B C A

The name “Latin square” was inspired by mathematical papers by Leonhard Euler, who used Latin characters as symbols.[1] Other symbols can be used instead of Latin letters: in the above example, the alphabetic sequence A, B, C can be replaced by the integer sequence 1, 2, 3.

There is no known easily computable formula for the number Ln of n × n Latin squares with symbols 1,2,…,n. The most accurate upper and lower bounds known for large n are far apart. One classic result[2] is that

$\prod_{k=1}^n \left(k!\right)^{n/k}\geq L_n\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}.$

A simple and explicit formula for the number of Latin squares was published in 1992, but it is still not easily computable due to the exponential increase in the number of terms.This formula for the number Ln of n × n Latin squares is,[3]

$L_n = n! \sum_{A \in B_n}^{} (-1)^{\sigma_0 (A)} (^{per A} _{\ \ n}),$

where Bn is the set of all {0,1} n × n matrices, σ0(A) is the number of zero entries in matrix A, and per(A) is the permanent of matrix A.

The problem of determining if a partially filled square can be completed to form a Latin square is NP-complete.[10]

The popular Sudoku puzzles are a special case of Latin squares; any solution to a Sudoku puzzle is a Latin square.

Sudoku imposes the additional restriction that nine particular 3×3 adjacent subsquares must also contain the digits 1–9 (in the standard version). The more recent KenKenpuzzles are also examples of Latin squares.

Boardgames

Latin squares have been used as the basis for several board games, notably the popular abstract strategy game Kamisado.

affine geometries, error-correcting codes, graph theory, number theory, cryptography, statistics, chess, and Sudoku (amongst other things) all as applications of the concept of Latin squares.

In recreational mathematics, a magic square is an arrangement of distinct numbers (i.e., each number is used once), usually integers, in a square grid, where the numbers in each row, and in each column, and the numbers in the main and secondary diagonals, all add up to the same number, called the magic constant.” A magic square has the same number of rows as it has columns, and in conventional math notation, “n” stands for the number of rows (and columns) it has. Thus, a magic square always contains n2numbers, and its size (the number of rows [and columns] it has) is described as being “of order n.”[1] A magic square that contains the integers from 1 to n2 is called a normalmagic square. (The term “magic square” is also sometimes used to refer to any of various types of word squares.)

Normal magic squares of all sizes except 2 × 2 (that is, where n = 2) can be constructed. The 1 × 1 magic square, with only one cell containing the number 1, is trivial. The smallest (and unique up to rotation and reflection) non-trivial case, 3 × 3, is shown below.

Any magic square can be rotated and reflected to produce 8 trivially distinct squares. In magic square theory, all of these are generally deemed equivalent and the eight such squares are said to make up a single equivalence class.[2]

The constant that is the sum of every row, column and diagonal is called the magic constant or magic sum, M. Every normal magic square has a constant dependent on n,calculated by the formula M = [n(n2 + 1)] / 2. For normal magic squares of order n = 3, 4, 5, 6, 7, and 8, the magic constants are, respectively: 15, 34, 65, 111, 175, and 260 (sequence A006003 in the OEIS).

Magic squares have a long history, dating back to 650 BC in China. At various times they have acquired magical or mythical significance, and have appeared as symbols in works of art. In modern times they have been generalized a number of ways, including using extra or different constraints, multiplying instead of adding cells, using alternate shapes or more than two dimensions, and replacing numbers with shapes and addition with geometric operations.

A geometric magic square, often abbreviated to ‘geomagic square’, is a generalization of magic squares invented by Lee Sallows in 2001. A traditional magic square is a square array of numbers (almost always positive integers) whose sum taken in any row, any column, or in either diagonal is the same target number. A geomagic square, on the other hand, is a square array of geometrical shapes in which those appearing in each row, column, or diagonal can be fitted together to create an identical shape called the target shape. As with numerical types, it is required that the entries in a geomagic square be distinct. Similarly, the eight trivial variants of any square resulting from its rotation and/or reflection, are all counted as the same square. By the dimension of a geomagic square is meant the dimension of the pieces it uses. Hitherto interest has focused mainly on 2D squares using planar pieces, but pieces of any dimension are permitted.