Latin Squares

I may be back from my week of vacation, and a new semester of teaching may be just around the corner, but part of my mind is still on the realm of games and puzzles. So today I want to talk about Latin squares, which sit at an interesting junction of mathematics and puzzles. (I think the intersection of mathematics and puzzles is what some people mean by “recreational mathematics”, but I’m not sure.)

Given an alphabet of n symbols (which we usually traditionally take to be the numbers 1, 2, 3, \ldots, n, but this is not necessary), a Latin square is an n\times n grid of symbols so that each symbol appears exactly once in every row and every column.

One interesting feature of these objects is their high degree of symmetry. For example, if you modify a Latin square by permuting the symbols (say, replacing all the 1’s with 4’s and all the 4’s with 1’s), the result will still be a Latin square. Likewise if you rearrange the columns or rearrange the rows of a Latin square, the result will again be a Latin square. These facts are pretty obvious, as is the fact that if you “transpose” a Latin square, switching the roles of rows and columns, the result is still a Latin square.

But there are deeper symmetries; the rows, columns, and symbols are actually play totally interchangeable roles. Suppose you have created a Latin square using the numbers from 1 to n as symbols, and you want to communicate to me which square you have. So you send me a bunch of text messages. You send me “1 2 3” to mean “in row 1, column 2, write a 3” and “5 1 4” to mean “in row 5, column 1, write a 4”, an so on until you’ve sent me all the numbers. However, we weren’t very clear when we set up the protocol, so I misunderstand your messages. I interpret “1 2 3” as “put a 1 in row 2, column 3” and “5 1 4” to mean “put a 5 in row 1, column 4”. Of course, I probably will get a totally different layout of numbers than the one you have. But, and this is what is amazing, if you start with a Latin square, what I get will also be a (wildly different) Latin square!

Example

Your Square   My Square
   12345        12345
   23514        31254
   31452        45132
   45123        24513
   54231        53421

What the previous paragraph says is very far from obvious. It’s worth some contemplation.

Now suppose you have two Latin squares of the same size, not necessarily on the same alphabet.  Imagine “superimposing” the squares.  (If we begin with the two squares above, say, the result would be as follows.)

11 22 33 44 55
23 31 52 15 44
34 15 41 53 22
42 54 15 21 33
55 43 24 32 11

It could happen that all possible pairs of symbols appear exactly once each.  This doesn’t happen here, because, say, 12 never occurs while 33 occurs twice.  If it does happen that all possible pairs occur once, then we call these mutually orthogonal Latin squares.  You can also look for sets of thre or four or more mutually orthogonal Latin squares (this means just that each pair is mutually orthogonal in the sense just described).  Sets of mutually orthogonal Latin squares are quite rare, but they have lots of nice properties.  In fact, for most sizes of square,, it is not possible to find mutually orthogonal Latin squares.

It turns out that it is possible to find a pair of mutually orthogonal 4\times 4 Latin squares.  As a little challenge, get a deck of cards and take the kings, queens, knights, and pages (or the kings, queens, jacks, and aces, if all you have are those new-fangled decks of cards).  Try to lay the 16 cards out in such a way that each suit appears once in each row and each column and likewise for the ranks.  If you can do it, then the ranks form a Latin square, and so do the suits.  The fact that you only have one King of Cups, etc., is tantamount to saying the two squares are mutually orthogonal.

Try it!

A partial Lain square is just a square grid in which some of the squares are filled in with symbols from the alphabet, but some are left blank, in such a way that no symbol appears more than once in any rrow or column.  The fundamental problem, of course, is how to complete a partial Latin square to a full Latin square.  It’s more complicated than you might think.  Just because there no duplicated symbols in any row or column yet doesn’t mean it’s possible to preserve that property as the fill the square. Here, for example, is an uncompletable partial Latin square. (What can go in the upper-right corner?)

12??
????
???3
???4

The process of filling in a partial Latin square has a “puzzle” sort of feel to it.  (It may in fact remind you of a very specific kind of puzzle.)  Indeed, many sorts of pencil-and-paper puzzles have combinatorial mathematics at their hearts.  While you certainly could just publish partial Latin squares as puzzles, much more popular have been variations in which there are addition conditions imposed.

  • The omnipresent sudoku puzzles are partial Latin squares with the additional condition that each symbol appears exactly once in each of nine 3\times 3 blocks.  Note that sudoku grids do not have as much symmetry as Latin squares.  For one thing, you can only rearrange rows and columns if you don’t disturb the block structure, and rows and columns are no longer interchangeable with symbols.
  • Kenken puzzles are partial Latin squares (typically with no symbols written in) with the additional condition that certain groups of cells satisfy some arithmetic property (the numbers add up to 8, or multiply to 60, etc.).
  • Killer sudoku puzzles are a hybrid of these types.  No starting symbols are provided, and the 3\times 3 condition is enforced, but groups of cells are marked with their sum.

These puzzles and their endless variations are well-known nowadays, but Latin squares serve as the basis of many lesser-known types of puzzles. One of these is the skyscraper puzzle.  You can find the rules and a few sample puzzles here.

By the way, a partial Latin square is not really the same thing as a Latin square puzzle.  A bona fide puzzle should only have a unique solution.  Have you ever thought about how sudoku puzzle constructors arrange to include just enough information, but not too much, to give a unique solution?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: