History of Latin Puzzles

The Latin Square Puzzle. A Latin square of order n is an arrangement of n x n cells in which every row and every column holds numbers 1 to n –other symbols may be used provided they are all different. Latin squares are well known objects and the base of Sudoku. They are so named because 18th century mathematician Leonhard Euler used Latin letters as symbols in his paper De Quadratis Magicis. Latin squares have a long and rich history. They are mentioned in relation to magic squares as early as the 17th century, although they seem to have been used in amulets much earlier.

We can remove symbols from Latin squares to obtain a partial square that is completable to just  the original square. The challenge to complete it is the Latin Square Puzzle. There are many other Puzzles with additional arithmetic or geometric constraints whose solutions are Latin squares too. French newspapers featured some of them in the 19th century, some of them very similar to Sudoku.

The Sudoku Puzzle. Sudoku is a Puzzle with a square board holding 81 cells and 27 regions (9 rows, 9 columns and 9 3x3 subsquares) of 9 cells each. A set of 9 different symbols (usually numbers 1 to 9) must be placed on every region. A completed Sudoku is clearly both a Latin square and a Gerechte square with each 3x3 subsquare being an additional region.

Sudoku first became popular in Japan after the company Nikoli started publishing it in the eighties. It spread later to the rest of the world when The Times of London started featuring it in 2004. It was later discovered by Will Shortz –the crossword puzzle editor for The New York Times– that the Puzzle's author was actually American architect Howard Garns, whose puzzles first appeared in the Dell Pencil Puzzles and Word Games magazine in 1979 with the name Number Place.

First Latin Puzzles not based on Latin Squares. After creating puzzles Moshaiku (2010) and Konseku (2011) Spanish engineer and puzzle author Miguel Palomo investigated the possibility of using triangular and hexagonal boards for puzzles similar to Sudoku.

This first such puzzles were Canario (2012) –inspired by the Pintaderas found in the Spanish Canary Islands–, Monthai (2013) –inspired by the namesake Thai pillow– and Douze France (2013). The puzzles featured split regions, a characteristic shared by Tartan (2013) on a square board. Helios (2013) on its side had a star-shaped board that contrasted with the existing more compact ones. The main characteristic was that their solutions were not Latin squares.

In his articles Latin Polytopes (2014) and Latin Puzzles (2016), Palomo formalized ideas on board shape and proposed a generalization for Latin squares and the Latin square Puzzle. These articles contained new puzzles with, among others, tetrahedral, cubic, octahedral, dodecahedral and icosahedral boards. These results were later presented in lectures about Latin polytopes and the evolution of Sudoku.

Latin Puzzles with repeated symbols. Later experiments produced puzzles with symbols repeated, like Sudoku Ripeto. These puzzles marked yet another departure from Sudoku.

Latin puzzles with inscriptions. Repeated symbols made possible custom inscriptions: generic words inside the boards in any language and alphabet. The first such Latin puzzles appeared in 2014. Some were based on Latin squares –like Custom Sudoku and Custom Quadoku– while others like Custom Galax, Custom Star weren't.

Region Size and Number of Symbols. Up to this point regions in Latin puzzles were all the same size matching the number of symbols used. A later generalization:

  1. let the puzzle’s regions have different sizes

  2. rendered independent from those sizes the number of playing symbols

  3. added the instruction for filling a region in the general case

Definition of Latin Puzzles

The ideas regarding boards, regions, symbols and inscriptions are condensed in the Latin Puzzle Definition:

1. A board has:

  1. any set of placeholders called cells

  2. any set of cells called regions with the same size

  3. every cell at least in one region

2. A Latin puzzle (lower-case p) has:

  1. a board

  2. a multiset of symbols of the same size as the regions

  3. the instruction: Write one symbol on each empty cell so that every region has all symbols in the multiset

  4. a set of clues: a particular set of pairs (symbol, cell) for some cells

  5. a solution: the only set of pairs (symbol, cell) amongst those that fulfill the instruction to have the clues as a subset

  6. 3.A Latin Puzzle (upper-case p) is the set of puzzles that results when we render variable the multiset of symbols and the set of clues in a given puzzle. A Latin Puzzle may have an inscription: a set of pairs (symbol, point) present in all its derived puzzles

  7. 4.The Latin Puzzle (upper-case p) is the set of puzzles that results when we render variable the board, the multiset and the clues in a given puzzle

  8. A Latin Puzzle and the puzzles derived thereof are of type:

  9. LS if their solutions are Latin squares, non-LS otherwise

  10. repeat if the multiset has repeated symbols, non-repeat otherwise

  11. inscripted if there is an inscription, non-inscripted otherwise

The Latin square puzzle and Sudoku are then Latin Puzzles. They are LS, uniform and non-inscripted.

Mathematics of Latin Puzzles

Mathematically, solving a Latin puzzle can be seen as a problem of hypergraph coloring. As with Sudoku and Latin squares, finding puzzles and solutions for a particular Latin puzzle can be performed among others with techniques like constraint programming or dancing links

Of interest are questions of existence and enumeration and minimality. For example: what is the minimum number of clues a particular Latin Puzzle may have? The answer to this question for Sudoku is 17 (see here).

As with Sudoku and Latin squares, many interesting questions about sufficiently complex Latin puzzles may well be NP-complete. In this case there could be no worst-case polynomial time algorithm able to answer them. One of them is: Given a partially filled board, is it a Latin puzzle? For partially filled Latin square boards the problem is known to be NP-complete indeed. Again, for tractable inputs the algorithms mentioned above can be used to answer the question.

But given that The Latin Puzzle provides an extra level of generalization questions may also be posed at this level questions may also be posed at a higher level, for example: What are the necessary and sufficient conditions for boards to hold Latin puzzles when symbols are all different?


Related press news

Boletín de la Real Sociedad Matemática Española

"El Sudoku de los Guanches”, La Opinión de Tenerife

“Konseku”. Diario Qué

 
menu.html