Latin Puzzles
_on_Sudoku_board_by_Miguel_Palomo.png)
_www.didoku.com_MiguelPalomo.png)
_www.didoku.com_MiguelPalomo.png)
Latin Puzzles are a broad generalization of Sudoku regarding board topology, regions, symbols and inscriptions inside the board. This results in new categories of puzzles in addition to the existing one to which Sudoku and current variants like Hypersudoku, Wordoku and Killer Sudoku belong. The term was coined and defined by Spanish engineer and puzzle author Miguel G. Palomo.
In what follows we adopt the following puzzle-Puzzle naming convention proposed in the article Latin Puzzles:[1] puzzle refers to a partially filled board, whereas Puzzle is a set of similar puzzles, as in "a Sudoku puzzle" and "the Sudoku Puzzle" respectively.
History of Latin Puzzles[edit]
_on_Sudoku_board_by_Miguel_Palomo.png)
_www.didoku.com_MiguelPalomo.png)
_on_Sudoku_board_by_MiguelPalomo.png)
_on_Sudoku_board.png)
The Latin Square Puzzle[edit]
A Latin square of order n is a square arrangement of n x n cells in which every row and every column holds symbols 1 to n. Latin squares are so named because 18th century mathematician Leonhard Euler used Latin letters as symbols in his paper De Quadratis Magicis.[2]
We can remove symbols from Latin squares and challenge players to complete the result to the initial Latin square: this is the Latin Square Puzzle. There are other Puzzles with additional arithmetic or geometric constraints whose solutions are Latin squares too. French newspapers featured some of them in the 19th century.[3]
In 1956, W. U. Behrens introduced what he called Gerechte squares:[4] regular Latin squares with the extra condition that all symbols be also present in each of the n regions with n cells each in which the board was partitioned.
The Sudoku Puzzle[edit]
Sudoku is a Puzzle with a square board holding 81 cells and 27 regions[5] (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 then a Gerechte square with each 3x3 subsquare being an additional region.
Sudoku became popular in Japan after the company Nikoli started publishing it in the eighties. It spread 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.
Latin Puzzles not based on Latin Squares[edit]
After creating Puzzles Moshaiku[6] (2010) and Konseku[7][8] (2011) Palomo investigated the possibility of a non-square Sudoku of sorts.
This resulted in Latin Puzzles Canario[9](2012) (inspired by the Pintaderas found in the Spanish Canary Islands)[10], Monthai[11] (2013) (inspired by the namesake Thai pillow) and Douze France[12] (2013). These Puzzles had split regions, a characteristic shared by Tartan[13] (2013) but on a square board. Helios[14] (2013) on its side, had a sparse, star-shaped board that contrasted with the existing compact ones. All of these Puzzles had solutions that were not Latin squares, a departure from Sudoku and many variants thereof.
To formalize ideas on board shape, Palomo wrote the article Latin Polytopes[15](2014), where a generalization of Latin squares to boards with different shapes and dimensions was proposed. The article contained new Latin Puzzles with, among others, tetrahedral, cubic, octahedral, dodecahedral and icosahedral boards.
Repeated Symbols and Inscriptions[edit]
Latin Puzzles with symbols repeated, like Sudoku Ripeto,[16] Quadoku Ripeto and Orb Ripeto[17] appeared afterwards. This was a departure from their uniqueness in Sudoku and its variants that demanded new playing strategies.
Latin Puzzles with Inscriptions[edit]
In 2014 repeated symbols opened the door to puzzles with inscriptions: the possibility of writing generic words inside the board in any language and alphabet. Examples are Custom Sudoku,[18] Custom Quadoku, Custom Galax and Custom Star.[19] [17]
Types of Latin Puzzles[edit]
In his 2016 article Latin Puzzles[1] Palomo proposes a classification for Latin Puzzles that includes among others the following types:
- LS if their solutions are Latin squares, non-LS otherwise
- repeat if the multiset has repeated symbols, non-repeat otherwise
- inscripted if there is an inscription, non-inscripted otherwise
The Sudoku Puzzle belongs then to types LS, non-repeat, non-inscripted.
Fair Latin puzzles[edit]
A fair Latin puzzle[1] is a Latin puzzle with this property: at each step of the resolution process there is always a reasoned way to reduce the number of candidate values for an empty cell[20]. All puzzles shown in the side figures for example are fair.
A puzzle that is not fair –or a fair one for which the deduction is not found at a particular step– can be solved by trial an error by repeating this procedure:
- choose a cell and and write a symbol from the compatible ones in that cell
- continue solving
- when an incompatibility occurs, undo all changes made since the last choice
- continue from the first step, but choosing a different symbol
Mathematics of Latin Puzzles [edit]
Mathematically, solving a Latin puzzle is a problem of hypergraph coloring. As with Sudoku and Latin squares, finding puzzles and solutions for a particular Latin Puzzle can be carried out with techniques like constraint programming[21] or dancing links[22].
Of interest are questions of existence and enumeration. For example: Is there a Latin puzzle on a Sudoku board with inscription WIKIPEDIA in the middle row with less than 40 clues? The example in the side figure gives the answer –provided the solution is unique. Another interesting question is: What is the minimum number of clues a particular Latin Puzzle may have? The answer for Sudoku is 17.[23]
As with Sudoku and Latin squares, many interesting questions about sufficiently complex Latin puzzles may well be NP-complete. In this case the existence of a worst-case polynomial time algorithm able to answer them is not guaranteed. One of these questions is: Given a partially filled board, is it a Latin puzzle? For partially filled Latin squares boards the problem is known to be NP-complete indeed.[24] Again, for tractable inputs the algorithms mentioned above an others cited in[1] can be used to answer the question.
Questions may also be posed at a more general level too, for example: What are the necessary and sufficient conditions for boards to hold Latin Puzzles when symbols are all different?
See also[edit]
References[edit]
- ↑ 1.0 1.1 1.2 1.3 Palomo, Miguel G. "Latin Puzzles".
- ↑ Euler, Leonhard (1862). "De Quadratis Magicis" (PDF). p. 141.
- ↑ Boyer, Christian (2007). "Sudoku's French ancestors". The Mathematical intelligencer. 29 (1): 27–44. doi:10.1007/BF02984758.
- ↑ Behrens, W. U. (1956). "Feldversuchsanordnungen mit verbessertem Ausgleich der Bodenunterschiede". Zeitschrift für Landwirtschaftliches Versuchs- und Un- tersuchungswesen 2: 176–193.
- ↑ In Sudoku, region is sometimes used to denote just one the 3x3 subsquares. As Latin Puzzles may feature boards of any shape, the term is more general. In Sudoku, this more general meaning is expressed with the term unit or scope
- ↑ "The Moshaiku Puzzle".
- ↑ "The Konseku Puzzle".
- ↑ "Konseku. Diario Qué".
- ↑ "Latin Puzzle Canario".
- ↑ "El Sudoku de los Guanches, La Opinión de Tenerife".
- ↑ "Latin Puzzle Monthai".
- ↑ "Latin Puzzle Douze France".
- ↑ "Latin Puzzle Tartan".
- ↑ "Latin Puzzle Helios".
- ↑ Palomo, Miguel G. "Latin Polytopes".
- ↑ "Sudoku Ripeto".
- ↑ 17.0 17.1 "Latin Puzzles".
- ↑ "Custom Sudoku".
- ↑ "Acertijos y más cosas".
- ↑ In the context of Sudoku a fair puzzle is sometimes called satisfactory
- ↑ KRZYSZTOF, R. (2003). Principles of Constraint Programming. Cambridge: Cambridge University Press. p. 1. Search this book on
- ↑ KNUTH, Donald E. "Dancing links".
- ↑ McGUIRE, Gary; TUGEMANN, Bastian; CIVARIO, Gilles (2012). "There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem".
- ↑ C. Colbourn (1984). "The complexity of completing partial latin squares". Discrete Applied Mathematics. 8: 25–30. doi:10.1016/0166-218X(84)90075-1.
External links[edit]
- Latin Puzzles site
- Miguel G. Palomo site
- Politopos Latinos, Tertulia de Matemáticas
- Boletín de la Real Sociedad Matemática Española
This article "Latin Puzzles" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
