The Well-Posed Puzzle

INTRODUCTION

Where do puzzles come from? Is it enough to say they come from puzzle posers? Very well, but then how do puzzle posers make their puzzles? In a puzzle where we have to fill in the missing information, how does the puzzle maker know just how much information can be left out? Why, when we try to set up a puzzle ourselves without thinking about it, do we discover that it is so difficult to devise an interesting puzzle that can be solved, can be solved in only one way, and is worth the trouble to solve?

These are questions that have appeared in my mind from time to time, and I've usually been content to wave them aside. Surely this information is too trivial to worry about, or too arcane for anyone to care about save the puzzlemasters themselves. But now I think it possible to say one or two things about puzzles. I'd like to consider the kinds of puzzles in which a single framework can be used over and over again, simply by changing the set of clues that are supplied.

So I'd like to start by showing some examples of these sorts of families of puzzles, and then turn to the question of how a set of clues may or may not correspond to a solution; whether there might be more than one solution; how one might go about picking good clues; and how, from the clues, one can sometimes carry out an automatic procedure for the solution of the puzzle.

SOME PUZZLE GAMES

In the game known as "MINESWEEPER", a rectangular grid of cells is displayed. Some cells contain a mine, and some don't. The number of mines is known, but their location is not. The goal of the game is to determine which cells contain mines. The first step - a very dangerous step! - is to pick a single cell. At this point, the solver has no information to go on, so this is purely a matter of chance. If the chosen cell contains a mine, it explodes, and the player is dead. Otherwise, the cell is revealed as empty, and all neighboring cells that are not neighbors of mines are also revealed as empty. The border of the revealed region now displays the number of neighboring mines. These values, and the shape of the border, particularly at corners, contains clues as to where other mines are. The careful puzzler can often solve the rest of the puzzle with no further guessing.

In the game of "LIGHTS OUT", a 5 by 5 grid of lights is presented. Some lights are on. A light can be turned on or off by pressing it. However, this also switches the state of the lights immediately above, below, left and right of the light. Thus, it's hard to predict the effect of pushing several lights in sequence. The object is to turn all the lights off.

In the game known as "BATTLESHIPS", a rectangular grid contains a number of ships. There a four submarines of length 1 cell, 3 cruisers of length 2, 2 destroyers of length 3, and a single battleship of length 4. Only a few cells are marked as containing an initial or intermediate part of a battleship, while the rest of the grid is unknown. However, each row and column lists the number of cells containing a ship. We also know that around every ship there is an boundary one cell thick which contains no other ships. The task is to determine where the ships are. The big ships are usually the easiest to determine.

In the game of "PAINT BY NUMBERS", a rectangular grid represents a picture, with some cells white and others black. The user is given a blank grid, and is told the length of each of the strings of consecutive black squares that comprise each row and column. Thus, a single row might be marked as containing (5, 3, 2) meaning that the row is entirely white, except for a string of 5 black cells, followed not immediately by 3, followed not immediately by 2. The object is to fill in the black squares and display the picture.

In the game of "SHERLOCK", there are five houses in a row. Each house has a particular occupant, a number, a color, a letter, a fruit, and and means of transportation. A few of the facts have been filled in. There are many clues, of various types, including

• (the-same): The house labeled 2 is green;
• (next-to): The house with the old man is next to the house with the bicycle;
• (left-of): The house with the woman is somewhere to the left of the house with the banana;
• (three-in-a-row): the houses with the baby, balloon, and 4 are in a row, in that order or the reverse;

THE PUZZLE SOLVER'S QUESTIONS:

Each puzzle I've described has multiple versions. By that, I mean that once you've solved the puzzle, you can easily request a new puzzle of the same format, but with different data. The skills you've developed on the previous puzzle will help, but you've now got a different version of the problem to handle. If there is a common theme to the puzzles, then it's reasonable to wonder whether there is a common strategy to solving them; if not a key, then perhaps some simple guidelines.

In between wasting time on some of those silly puzzles, we now frame a few questions that we wish we could address when we see the next puzzle. The first one is the existence question:

• Is there no solution?
• Is there a solution?
• Are there several solutions?

Usually we don't bother asking if there are solutions; we just try to come up with one. Often, we can methodically construct a partial solution, that is, determine some of the hidden information. Sometimes, the production of the full solution seems a random process of tugging at various clues, until we stumble into the full answer. This leads us to the construction question:

• Is there a simply way to construct a partial solution?
• Can a full solution be constructed methodically?

THE PUZZLE POSER'S QUESTIONS:

You may find, after working on these puzzles, that you wonder how the puzzlemasters churn them out. After all, in Sherlock, you can't just hope that any old set of clues will make a puzzle; they might contradict each other. You could solve that problem by setting up the answer, and then only writing down clues that describe that answer. But then, how do you know when you've written enough clues?

Posing the puzzles seems to have its own set of problems. We raise a few questions:

• The Robotic Poser: can I guarantee that the next puzzle I generate is (uniquely) solvable?
• The Thorough Poser: Can I describe how to produce every solvable puzzle?
• The Puzzle Reckoner: Can I count how many puzzles there are? How many solvable puzzles? How many uniquely solvable puzzles?

The Game of SUBMARINES

When we work on a puzzle, we might even use the (assumed) fact that there must be a solution in order to solve the puzzle! But many of the puzzles we've seen can easily be set up without knowing the solution. Can we assume that, for every set of clues, there is a solution? If not, is there a way to tell which clues are solvable and which not, short of simply trying every possible solution?

Let us look at a very simple version of BATTLESHIPS which we will call "SUBMARINES". Your job is to determine the locations of submarines in a patch of ocean. The ocean is represented by a rectangle, divided into cells. Each cell may contain one submarine or none. To set up the puzzle, the poser simply places a 0 or 1 in each cell. The clues given to the player are the sum of the entries in each row, and in each column. The player is asked to determine the hidden values, that is, which cells contain a submarine.

Here is a sample problem for a 3 by 3 board:

```        ? ? ? | 0
? ? ? | 1
? ? ? | 1
------+
1 1 0
```

It's easy to fill in the first row and the third column. but then we're stuck. If we play sloppy, we just guess that there's a 1 in row 2, column 1, and we find the solution:

```        0 0 0 | 0
1 0 0 | 1
0 1 0 | 1
------+
1 1 0
```
So we might walk away satisfied. But we shouldn't be, because there's another solution:
```        0 0 0 | 0
0 1 0 | 1
1 0 0 | 1
------+
1 1 0
```
This makes it easier for a sloppy player, who never realizes the difficulty, but makes it impossible for a careful player, who will not put down an answer until it can be justified.

It is also possible to come up with data like:

```        ? ? ? | 3
? ? ? | 2
? ? ? | 0
------+
1 3 1
```
which has NO solutions, and data like
```        ? ? ? | 2
? ? ? | 1
? ? ? | 3
------+
1 2 3
```
which has exactly one solution:
```        0 1 1 | 2
0 0 1 | 1
1 1 1 | 3
------+
1 2 3
```

For the 3 by 3 puzzle, it's obvious that the clues consist of the row and column sums, and that these are simply six numbers. If we agree to list the row sums first, then any string of 6 values could represent a set of clues. Our questions then become:

• What clues don't represent a solvable puzzle?
• What clues represent a puzzle with only one solution?
• How many uniquely solvable puzzles are there?
• Can we determine the solution of any uniquely solvable puzzle?

Solvability or "Existence"

Let's start with the question of which clues represent solvable puzzles. It should be obvious that some sets of clues do not represent a solvable puzzle at all. Sometimes this can be seen from the clues almost immediately. Here are two obvious rules:

1. If the value of any clue entry is less than 0, or greater than 3, the clue set is invalid;
2. If the sum of the first 3 clues is not equal to the sum of the last 3, the clue set is invalid;
These rules are necessary, that is, a set of clues must satisfy these conditions, and if it violates one of these rules, it is not a solvable puzzle. But the rules are not sufficient, that is, if a set of clues satisfies these conditions, that's not enough to ensure that the clues are actually valid.

But there is a single check we can make which is necessary and sufficient. It puts all the valid puzzles on one side, and the invalid ones on the other. Briefly, if we call the row sums R, and the column sums C, and we sort both sets of sums in decreasing order, then the clues represent a "valid" puzzle, that is, there is at least one solution to the puzzle, if, and only if

• The conjugate list R* majorizes C.
Of course, now we'll need to do some explaining.

Consider the valid problem whose row sums were R=(2,1,3) and column sums were C=(1,2,3). If we sort the lists as required, we have R=(3,2,1) and C=(3,2,1). Now we make the conjugate list R* from R as follows: R*(1) is the number of elements of R greater than or equal to 1, R*(2) counts the number of elements greater than 2, and so on. This gives us R*=(1,2,3). Now we must compare C and R* in a majorization check. We require that:

```        C(1)               <= R*(1)
C(1) + C(2)        <= R*(1) + R*(2)
C(1) + C(2) + C(3) <= R*(1) + R*(2) + R*(3)
```
which turns out to be very simple to verify. So that puzzle is valid.

Now consider the example of an invalid puzzle mentioned above. The sorted data is R=(3,2,0) and C=(3,1,1). Then R*=(2,2,1). Our majorization check is:

```        3         <= 2          FALSE!
3 + 1     <= 2 + 2      (true)
3 + 1 + 1 <= 2 + 2 + 1  (true)
```
and because the first check fails, this puzzle is invalid.

Thus, we see that a set of clues can represent no solutions, or one, or several, and that it is not always obvious how to determine this. We have seen an example of a rule that allows us to determine which puzzles are valid, without actually coming up with a solution to the puzzle. In the next section, we will talk about how to go about finding a solution to a valid problem.

Uniqueness

But wait, our work is not done. Suppose we have a pair of row and column sum vectors, and we apply our test. If it is negative, then there is no possible submarine configuration corresponding to this data, and that is a satisfactory answer. But if the test is positive, we know that there is some corresponding configuration, but that's not the same as saying the puzzle is solvable - at least, it doesn't guarantee that there is exactly one answer. And for a puzzle, we definitely don't what there to be multiple answers!

To see that this could really happen, consider a case where we have R = (2,2,1) and C = (1,3,1). After we sort C and compute R*, our validity test goes as follows:

```             Sorted C                Conjugate R

3      1      1                3       2       0

C(1)               = 3 <= 3 = R*(1)
C(1) + C(2)        = 4 <= 5 = R*(1) + R*(2)
C(1) + C(2) + C(3) = 5 <= 5 = R*(1) + R*(2) + R*(3)
```
Therefore, R and C can be used to construct a submarine puzzle.

Once we know a puzzle is solvable, it's not hard to find a solution. Here we have one:

```        1 1 0 | 2
0 1 1 | 2
0 1 0 | 1
------+
1 3 1
```
Unfortunately, we might not realize that this same set of data allows for another solution:
```        0 1 1 | 2
1 1 0 | 2
0 1 0 | 1
------+
1 3 1
```
This means that the original R and C data does not correspond to a unique solution.

Supposing that we have R and C data that we know is solvable, can we think of any tests that would allow us to discard data for which more than one solution exists? Let's start with the following observation about the simplest possible ambiguous data, R = (1,1) and C = (1,1), which allows the following two distinct solutions:

```        1 0 | 1    0 1 | 1
0 1 | 0    1 0 | 0
----+      ----+
1 0        1 0
```

Now note that the important thing is that there are four data items in the array which can switch positions without changing the row and column sums. This same pattern could occur in a bigger array, and would cause the same difficulty. For example, let us suggest how this might look in a 4 by 4 problem:

```        a 1 b 0 | ?    a 0 b 1 | ?
c d e f | ?    c d e f | ?
g h i j | ?    g h i j | ?
k 0 l 1 | ?    k 1 l 0 | ?
--------+      --------+
? ? ? ?        ? ? ? ?
```
and note that when we switch the 1's and 0's from the left solution to the right, rows 1 and 3, columns 2 and 4 still have the same sums they did; in other words, any puzzle which has this pattern will have at least two solutions.

A statement like this is interesting, but it doesn't really suffice. After all, it doesn't have the power to take any puzzle and announce whether it has no solutions, one solution, or many. Let's concentrate on the possiblity that, for a given set of row and column sum vectors R and C, we have at least two distinct solutions, which we'll name A and B.

We can think of A and B as M by N matrices of 0's and 1's, and we can subtract them to get the matrix A-B. Note that A-B is a solution to a matrix row/column sum problem in which we allow entries of -1, 0 or 1, and in which both the R and C vectors are entirely zero.

We will now show that A-B must have the chain property, that is, that there is a rectangular path, moving in "alternating rook moves" down and across the matrix, from a +1 entry to a -1 entry, never landing on an entry twice until the path closes at the entry where it began. There may be more than one such chain, but there must always be at least one in a matrix A-B corresponding to two distinct solutions.

To see this fact, note that A-B must have at least one nonzero entry, otherwise the two solutions would be identical. For convenience, let us suppose that this entry is -1, and has row and column coordinates (I1,J1). Since column J1 sums to 0, there must be a +1 entry somewhere in this column, say at entry (I2,J1). We have never visited row I2 before, so we know that the +1 entry must be balanced by a -1 entry in the same row, but at a new column, say (I2,J2). We continue in this way, alternately moving to a new row or new column, and each time "landing" on a new nonzero entry of A-B. Since we are "using up" an entry each time, we cannot do this forever. But since the row and column sums are 0, it must always be possible to find an entry of opposite sign in the new row or column. Therefore, at some point, this balancing entry will in fact be one of the entries we already landed on. We can now regard the sequence of row and column indices as a "chain", or a series of rook moves that alternate in row and column direction, always turning at a new nonzero entry of A-B and forming a closed path. And so, if an array A-B has at least one such chain path, we say it has the chain property.

Now when we are asking whether a given solution is unique, we are not going to have two solutions A and B, but just, say A. Is there some detectable structure inherent in A that both allows the chain to exist, and that can be detected by us?

The answer is both simple and tedious to check. To determine whether there is a second solution B or now, we can "simply" make the following test: starting at any nonzero entry of A, is it possible to return to that entry making a series of alternating rook moves, in which the vertical moves are to 0 entries, and the horizontal moves are to 1 entries, and in which no entry is ever visited twice (except of course that we return to the initial entry)?

If there is such an alternating path or chain, then the second solution B is constructed by swapping all 0's and 1's on that path. So what we're doing is making chain test on A-B with an unknown B. And it turns out we don't really need to see B to make the test, we just have to be prepared to look at A very carefully. Below is an example in which a chain in A is found (not the shortest one, certainly) and is used to construct a new solution B. You should see that simpler chains exist from which other solutions could be found.

```           Solution A   ==>  Solution B
+==============================
2 |  1-0-0 0 1 0      0-0-1 0 1 0
|  |   |            |   |
1 |  0 0 1-0-0-0      0 0 0-0-0-1
|  |         |      |         |
1 |  0-0-0-0-1 0      1-0-0-0-0 0
|          | |              | |
3 |  0 1 0 1 1 0      0 1 0 1 1 0
|          | |              | |
2 |  0 1 0 0 0-1      0 1 0 0 1-0
+=============================
1 2 1 1 3 1      1 2 1 1 3 1
```

If no such chain can be found, then A has "passed" the chain test, and represents a unique solution of the row and column sum problem. Let us leave aside for the moment the fact that the chain test seems like it might be difficult to carry out for a large problem. It is evident that if a solution "passes" the chain test (no chains), then it represents a unique solution, and if it fails, there are multiple solutions.

The chain test tells us whether a given solution is unique. The majorization test tells us whether a pair of row and column sum vectors correponds to a problem with zero solutions, or more than zero solutions. Is this everything we need? Unfortunately, no. If we start with a given R and C vector, we may find that they admit at least one solution, but how can we, in general, compute a solution? After all, if we can't actually come up with a solution A, it's no use having a test to tell us whether that unavailable solution would be unique!

Construction

Certainly, in most cases, patience and a simple checking of all possibilities will lead to the discovery that one of the unknown facts can be determined from the given data. In an unsystematic way, it is possible to gradually stumble towards the solution.

AN INVERTIBLE PUZZLE

Before we look at "real" puzzles, let us start with a model puzzle which is quite simple and is especially amenable to mathematical analysis. We call this puzzle "Laplace's Ashes". You may recognize it as being related to MINESWEEPER.

To define a puzzle, begin with a rectangular grid. In each cell of the grid, write a number. This is the solution of the puzzle. For example:

```        1  3  6  2
4  2  1  1
2  3  4  9
```

Now, to form the clues, make a copy of the grid. But now, in each clue cell, write the sum of the values that occur in the corresponding solution cell and its eight immediate neighbors. If a neighbor is "missing" because the solution cell is on the border of the grid, behave as though that number were zero.

Here is the corresponding clue grid:

```        10  17  15  10
15  26  31  23
11  16  20  15
```

Now, interestingly, we can write a set of equations that relate the values in the clue grid to the values in the solution grid. Let us begin by numbering the cells in both grids starting in the upper left corner, sweeping left to right, and from top to bottom. In this case, the cells will be numbered as follows:

```        1   2   3   4
5   6   7   8
9  10  11  12
```

Secondly, let us call the values in the solution grid X values, and the clue grid values B. Then it should be clear that the value in the first clue cell can be defined by the formula:

```        B1 = X1 + X2
+ X5 + X6.
```

In fact, a similar equation can be written for each of the B variables. There is a standard way of writing the relationship between the B variables and the X variables by storing the appropriate coefficients in a matrix we will call A. The relationship is summarized by

```        B = A * X
```
where the coefficient matrix A has the form:
```        1 1 0 0  1 1 0 0  0 0 0 0
1 1 1 0  1 1 1 0  0 0 0 0
0 1 1 1  0 1 1 1  0 0 0 0
0 0 1 1  0 0 1 1  0 0 0 0

1 1 0 0  1 1 0 0  1 1 0 0
1 1 1 0  1 1 1 0  1 1 1 0
0 1 1 1  0 1 1 1  0 1 1 1
0 0 1 1  0 0 1 1  0 0 1 1

0 0 0 0  1 1 0 0  1 1 0 0
0 0 0 0  1 1 1 0  1 1 1 0
0 0 0 0  0 1 1 1  0 1 1 1
0 0 0 0  0 0 1 1  0 0 1 1
```

Now with the problem formulated in this way, a mathematician realizes that situation can be summarized immediately as follows:

• The behavior of the problem is entirely determined by the properties of the matrix A.
• If A is nonsingular, then for every value of B, there is always exactly one solution X.
• If A is singular, then there will be some B's for which there is no solution, and other B's for which there will be multiple solutions. In particular, the B which is entirely zero will have multiple solutions.

If we can show that, for the puzzle in which B is entirely zero, the only solution is the one for which X is entirely zero, then we have shown that A is nonsingular, and hence that every puzzle is solvable.

With this fact in mind, let's consider the case where our clue matrix is entirely zero:

```        0  0  0  0
0  0  0  0
0  0  0  0
```
One solution for this set of clues is certainly the zero solution. Can we show that the only solution of this problem is the zero solution?

Let us try to combine some of the facts so we can eliminate the unnecessary ones. We begin by supposing only that we have a solution X to the problem. So the values in X satisfy the rules of the puzzle, and give us a result of zero. What, if anything, can we deduce about the actual values in X?

We start by looking at the facts:

```        X(1) + X(2) + X(5) + X(6) = 0
```
and
```        X(1) + X(2) + X(5) + X(6) + X(9) + X(10) = 0.
```
Putting these facts together, we can see that it must be true that
```        X(9) + X(10) = 0
```

If we call the value of X(9) a, then the value of X(10) must be -a. Now our solution grid looks like this:

```        ?   ?   ?   ?
?   ?   ?   ?
a  -a   ?   ?
```

Using similar reasoning, we can compare the sum of the neigbors at a corner with the sum at the cell one position higher or lower, to fill in the solution grid a little more:

```        b  -b  -c   c
?   ?   ?   ?
a  -a  -d   d
```

Now look at the equation associated with cell 5:

```        X(1) + X(2) + X(5) + X(6) + X(9) + X(10) = 0
```

We already know that the pairs X(1) and X(2), and X(9) and X(10) cancel out, allowing us to conclude that X(5) and X(6) are opposite values. Similarly, we can conclude the same about X(7) and X(8):

```        b  -b  -c   c
-e   e   f  -f
a  -a  -d   d
```

Now look at the equation for B(10):

```        X(5) + X(6) + X(7) + X(9) + X(10) + X(11) = 0
```
but this says
```        -e + e + f + a - a - d = 0
```
or
```        f - d = 0
```
so we know that f and d are equal.

Similarly, we can conclude that f and c are equal, that e and b are equal, and that e and a are equal. This means our table has the form:

```         e  -e  -f   f
-e   e   f  -f
e  -e  -f   f
```

Now look at the equation for B(6):

```        X(1) + X(2) + X(3) + X(5) + X(6) + X(7) + X(9) + X(10) + X(11) = 0
e - e - f - e + e + f + e - e - f = 0
-f = 0
```

So f is zero. Similarly, we find that e is zero. From this we conclude that the only solution to the puzzle with zero clues is the zero solution. From this we conclude that the associated matrix is nonsingular, and that, for any set of clues, there is always one and only one solution. The question is, how do we go about this solution?

Mathematically, it is enough to compute a matrix A-1 related to the puzzle matrix A, and called the inverse of A. Then, if we take any set of clues B, we can compute the solution X by carrying out the following computation:

X = A-1 * B
If you're going to be solving the same kind of puzzle many times, it might be worth the work of computing A-1. But can we hope for a simpler rule?

A NONINVERTIBLE PUZZLE

Now let's consider a simpler puzzle. We start with the same rectangular grid containing a set of solution numbers. But now, to build our clue table, for each cell we add the upper and right neighbors, and subtract the lower and left ones. Again, neighbors outside the grid are treated as zeros.

Here is an example of a 3 by 4 solution grid:

```        1   3   6   2
4   2   1   1
2   3   4   9
```
The corresponding clue grid is:
```       -1   3  -2  -7
1  -3   1  -8
7   4   7  -3
```

This puzzle too can be expressed in a matrix form relating the clues to the answers. The matrix A is:

```         0 +1  0  0  -1  0  0  0   0  0  0  0
-1  0 +1  0   0 -1  0  0   0  0  0  0
0 -1  0 +1   0  0 -1  0   0  0  0  0
0  0 -1  0   0  0  0 -1   0  0  0  0

+1  0  0  0   0 +1  0  0  -1  0  0  0
0 +1  0  0  -1  0 +1  0   0 -1  0  0
0  0 +1  0   0 -1  0 +1   0  0 -1  0
0  0  0 +1   0  0 -1  0   0  0  0 -1

0  0  0  0  +1  0  0  0   0 +1  0  0
0  0  0  0   0 +1  0  0  -1  0 +1  0
0  0  0  0   0  0 +1  0   0 -1  0 +1
0  0  0  0   0  0  0 +1   0  0 -1  0
```

Is this puzzle invertible? You can make some progress in attacking this problem, but at some point, you will find that the variables separate into two groups, and you can't come up with a relationship that allows you to finish the solution. You can't be sure you haven't tried every way of manipulating the equations, but you might suspect that something is wrong with the puzzle. If you now consider the zero test, you may see that there are nonzero sets of solution grids that give a zero clue grid. In particular, here is one:

```        8   5   8   5
-5  -8  -5  -8
8   5   8   5
```

Reference:

A version of MINESWEEPER comes as part of the Microsoft Windows Operating system, as the executable C:\WINDOWS\WINMINE.EXE.

Several toy versions of the Lights Out puzzle are manufactured by Tiger Electronics. A number of computer versions of the game are available.

The Paint by Numbers puzzle is regularly featured in GAMES magazine. A version of this puzzle for the PC is also available, as "Descarte's Enigma", from Everett Kaser

The Battleships puzzle is regularly featured in GAMES magazine. A shareware version for the PC is available as FATHOMIT from Mountain Vista Software.

The Sherlock puzzle is available for a PC running Windows from Everett Kaser.

• The technical check on the SUBMARINES game is discussed in:
Jack van Lint, Richard Wilson,
A Course in Combinatorics,
Chapter 16, (0,1) Matrices,
Cambridge, 1992.
• The SUBMARINES game is considered as a CAT-scan problem in:
Alexander Dewdney,
The Tinkertoy Computer and Other Machinations,
Chapter 15, Scanning the Cat,
Freeman, 1993.
• Counting the number of (0,1) matrices uniquely determined by their row and column sums was discussed in:
Lonesum (0,1)-matrices and poly-Bernoulli numbers of negative index,
Master of Science Thesis,
Computer Science Department,
Iowa State University, 2005.
• The properties of (0,1) matrices have been considered in a number of articles by the mathematician Herbert Ryser, including:
Herbert Ryser,
Matrices of zeros and ones,
Bulletin of the American Mathematical Society,
Volume 16, pages 442-464, 1960.