Futoshiki squares

Futoshiki is a puzzle in the spirit of sudoku, involving constructing a Latin square from some partial information, which can be found in some newspapers now, including the Saturday Guardian. Probably someone has looked at the mathematics of futoshiki, but I have never seen anything (and Wikipedia is not very forthcoming); rather than go looking, I will put my own thoughts here.

The puzzle presents you with an n×n grid of boxes, which are to be filled with the numbers 1,…,n to construct a Latin square. The given information is of two types:

  • inequalities between neighbouring cells in a row or a column;
  • some preassigned numbers.

I will call a futoshiki pure if it has no preassigned numbers, and mixed otherwise. I will not consider futoshiki which have preassigned numbers but no inequalities, since the problem in this case is just completion of partial Latin squares, which has been well studied. Until the end, I will just discuss pure squares.

As with sudoku, the puzzle is valid only if there is a unique solution. Accordingly, I will call a Latin square of order n on the symbol set 1,…n a futoshiki square if it is the unique Latin square which satisfies all the inequalities between neighbouring entries in a row or column. In deciding this, we may assume that all possible inequalities are present: removing some inequalities, while preserving the fact that there is a unique solution, makes a more interesting puzzle, but doesn’t change the property of being a futoshiki square.

Some questions which might arise are:

  • Is every Latin square a futoshiki square? If not, how many are, and what is the smallest non-futoshiki square?
  • Is every pattern of inequality signs realised by a Latin square? IF not, how many are, and what is the smallest non-realised pattern?

I will discuss these questions first in the one-dimensional case, then say something about the problems above, and finally speculate about extensions.

The 1-dimensional case

In this case we are looking at a permutation of the numbers 1,…,n, and attempting to characterise it by the inequalities satisfied by neighbouring elements. This is what happens:

  1. The only permutations which are uniquely determined by these inequalities are the increasing permutation 12…n and the decreasing permutation n…21. For suppose that two consecutive numbers i and i+1 are not in consecutive positions. Then they can be swapped without violating the inequalities, since all other elements are either smaller than or larger than both. The only permutations not containing such a pair are the increasing and decreasing permutations.
  2. In particular, the smallest non-futoshiki permutations have n = 3, and there are four of them.
  3. Since the number n! of permutations is asymptotically greater than the number 2n−1 of patterns of inequalities, it is clear that most permutations are non-futoshiki (even without our exact characterisation). Can some statistics for the number of permutations realising a sequence be derived?
  4. Every pattern of inequalities is realised by at least one permutation. This can be proved by induction on n, the base case n = 1 being trivial. So suppose the result holds for n−1. Choose a permutation of 1,2,…n−1 satisfying the first n−2 inequalities. If the last inequality is <, simply append n; if it is >, move each of the first n−1 entries up by one and append 1.

The 2-dimensional case

The results in this case are very similar, with one important difference.

  1. Again it is true that the number of Latin squares (at least (n/c)n2) is asymptotically greater than the number 22n(n−1) of patterns of inequalities, so that almost all Latin squares are non-futoshiki.
  2. For n ≤ 3, every Latin square is futoshiki. This is trivial for n = 2. For n = 3, we use the fact that all twelve Latin squares are known; each has one row which is either increasing or decreasing, and the other two are cyclic permutations of this row (which have patterns < > and > < and so can be distinguished). We Will see very soon that the smallest non-futoshiki square has order 4.
  3. If a Latin square contains an intercalate (a 2×2 subsquare) which has consecutive entries but not in consecutive rows or columns, then it is not a futoshiki square, since the intercalate can be switched by interchanging the entries, analogously to the 1-dimensional case. For every order at least 4, there exists such a Latin square. Indeed, there are many such squares. I do not expect that they will make up a majority of non-futoshiki squares.
  4. On the other hand, for every order, there is at least one futoshiki square. One example is the cyclic square whose first row and column consist of the numbers 1,2,…,n in natural order. It suffices to include all the inequalities above the main antidiagonal, since every number above the antidiagonal lies in a maximum chain. Then, for example, the second row is 2…n followed by a blank space, which must contain 1; and so on down the other rows.
  5. Not every pattern of inequalities is realised by a Latin square. For a simple example, we can specify that the first two rows are both increasing, which is clearly impossible.

Further questions

Here is a selection of further questions which could be investigated.

  1. What about higher-dimensional Latin hypercubes? We suppose that we have an n×…×n array over the alphabet 1, …, n, in which each “coordinate line” (with all but one of the coordinates fixed) is a permutation of the alphabet.
  2. We saw that not every Latin square is a pure futoshiki square. Let us say that the defect of a Latin square is the smallest number of entries that must be pre-specified in order for the mixed futoshiki puzzle should have a unique solution. How is this parameter distributed over Latin squares of order n? In particular, what are its average and maximum values?
Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , . Bookmark the permalink.

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