Classics Collection

Classics Collection: Tapa

This has been a busy weekend. There have been three interesting online contests (actually, they are still running as I write these lines), and maybe I will post a brief summary shortly. Meanwhile, it is time for another installment of the Classics Collection series.

Tapa, like Masyu, is not the most intuitive puzzle type, but it has a rich potential for interesting constellations and beautiful puzzles. Since its introduction in the late 2000s, its popularity has increased rapidly, and Tapa has soon become one of the most well received puzzle styles in the community. As such, it certainly has its rightful place in the Classics Collection.

Here is the link to the new PDF file: Tapa

Rules: Shade some cells so that all shaded cells are connected and no 2×2 square is completely shaded. Cells with numbers cannot be shaded. The numbers indicate how many of the horizontally, vertically and diagonally neighbouring cells are shaded: Each number corresponds to a contiguous group of shaded cells, two such groups are separated by one or more unshaded cells. Position and order of the numbers within a cell are irrelevant.

Example and solution:

As with other Shading Puzzles (e.g. Nurikabe), I prefer to designate both shaded and unshaded cells in the solution. Well, there are times (in competition) when I feel I must make up some ground, in which case I limit myself to a very crude form of shading and leave the unshaded cells as they are. But when it comes to quality solving, I think it is a good idea to take the time and mark the empty cells as well.

As far as solving techniques are concerned, it is important to first understand the meaning of the clues. Given a grid cell away from the edges, its neighbourhood is a set of eight other cells which has a “circular” structure. A clue of 8 means that all these cells are shaded; a clue of 0 means that they are all unshaded. That is the easy part.

Given any other clue, it is not possible to mark any neighbouring cell as shaded or unshaded with certainty. Take a 6, for instance. The clue indicates that six of the neighbouring cells are shaded, and that those cells form a single group within the neighbourhood (i.e. if one stands on the first cell and moves in 45° steps, one will pass the rest of the group in five steps without skipping a cell in the circular arrangement).

This sounds like one has a good chance of hitting a shaded cell if one picks one at random, but logical puzzles are not designed to be solved using probabilities. The shaded group can be rotated eight different ways, which means that any specific cell in the neighbourhood can be shaded or unshaded. The same holds for other clue numbers or even number combinations, although the exact number of possibilities will vary.

Cells along the edges and in particular in corners are quite different. The rotation argument does not apply here; instead, the neighbourhoods of such cells have a “linear” structure. A 5 in an edge cell or a 3 in a corner still means that all cells are shaded, but other numbers carry more weight here. A clue of 4, for instance, means that there are only two solutions in the neighbourhood of this cell, and they share three shaded cells. A clue of 3 at least requires a shaded cell in the middle, no matter what.

Number combinations can also be more powerful in edge cells, for pretty much the same reason. Since there are not that many constellations, we can list the relevant ones: A 2/2 combination and a 1/1/1 combination have a unique solution. A 3/1 clue has two solutions, but with three common shaded cells. By the way, a 1/1 in a corner is unique, and a clue of 2 in a corner cell must have its diagonally touching cell shaded. Other combinations do not yield any shaded or unshaded cells with certainty.

You will find such clues in the training puzzles from this set. For example, Tapa 1 has an 8 inside the grid, a 5 and a 3 along different edges and a corner cell with a clue of 2. Tapa 2 has a clue of 0, a 2/2 combination in an edge cell and a 4; Tapa 3 has 2/2 and 3/1 combinations. It is generally a good idea to look for such clues at the beginning, since they typically give you straightforward starting points.

There are a few other interesting constellations. A 1/1/1/1 clue has only two solutions, namely with all the orthogonally adjacent cells shaded and the diagonally touching cells unshaded, and vice versa. Very often, it is possible early on to eliminate one possibility. For instance, if the clue is only one cell away from an edge of the grid (see Tapa 8), the solution with the orthogonally adjacent cells shaded does not work – one would obtain a shaded cell which cannot be connected with the rest. Try it.

A 3/3 clue is exciting, too. It turns out that the unshaded cells must lie opposite each other, so there are only four ways to satisfy the clue. In practice, once again one can often eliminate some of them, and each elimination yields two shaded cells. Have a look at Tapa 4 from the PDF file: If the cells in R7C5 and R5C7 were unshaded, one would obtain an isolated shaded group in the corner. This kind of step is quite typical.

In general, you may note the following: If the sum of the numbers within some clue cell (away from the edges) plus the clue number count in the same cell is equal to 8, shaded groups can only be separated by a single unshaded cell. For instance, a 4/2 clue has a group of four shaded cells somewhere in its neighborhood, followed by a single unshaded cell, a group of two shaded cells and another unshaded cell. There simply is no room for more unshaded cells.

I do not think the formula as such is worth memorizing, but it tells you what to look for. Groups with large sums have very few freedoms, so if one obtains one or two pieces of information from nearby, it may be enough to resolve the entire neighbourhood of the clue cell.

Another important constellation occurs when two clues lie in neighbouring cells. The point is that each one of them is automatically unshaded for the other. As such, it reduces the circular structure of the neighbourhood to a linear one. Each clue therefore gains power, sometimes enough to locate some several cells with certainty.

We can see this in Tapa 5. The 4/2 clue in R5C2 has a priori eight rotated solutions, but only two of them have an unshaded cell in R4C2. The remaining two solutions share five shaded cells. Something similar applies to the 5/1 clue in R4C6. The clue combination of 6 and 3 in touching cells in Tapa 6 is significant as well.

Bigger clusters of clues can yield a great many shaded and unshaded cells right away, but they rarely occur in Tapa puzzles. Far more often, one encounters a large number of isolated clues, typically with one or two cells between them.

When that happens, one has to factor in one of the other rules we have not studied so far. If there are many large clues in a part of the grid, there have to be many shaded cells. In that case, one can typically make progress using the rule that shaded 2×2 squares are forbidden. On the other hand, if there are many small clues (and thus very few shaded cells), the requirement that the shaded cells must all be connected is crucial.

As for the first part, one may have located three shaded cells in a 2×2 square already and can then mark the fourth cell as unshaded directly. Sometimes, though, the inferences are more subtle. After exploiting the clue of 8 in Tapa 1, look at the clues of 2 in this grid. We know that R6C6 is shaded, so we can deduce that R6C7 is unshaded – this is the blunt way. The clue in R1C6 yields no such information, but observe what happens if the cell R2C6 were shaded. It would force a shaded 2×2 square one way or another, hence a contradiction. We can conclude that R2C6 must be unshaded – this is the subtle way.

In general, if there is information available regarding the “extended neighbourhood” of a clue cell (cells which are two steps away), the number of solutions in the immediate neighbourhood may be reduced. Such eliminations are also typical and lead to slow progress.

As for the second kind of reasoning, a formation with many small clues can be seen in Tapa 2. After exploiting the two clues in the top row, look at the shaded group in R1C4/R2C4. These cells must be connected with the other shaded cells in the grid, and there is only one exit (via R3C4). This yields seven more unshaded cells next to the clue in R4C3, and after some additional work in the bottom/right part of the grid it turns out there is only way via Column 5 to connect the open ends.

Grid parts with small clues tend to produce many isolated shaded groups, and it remains to find an exit from an enclosed region or generally connections between these groups. Sometimes there is a unique passage right away; in other cases one can only prove that they require certain fixed shaded cells, like “checkpoints”. It may even be possible to find areas which are entirely cut off and cannot contain any shaded cells at all. For example, it is impossible to find an exit from R7C5/R6C5 in Tapa 6 without violating at least one of the clues.

Observant readers will notice that cells which do not lie in the neighbourhood of any clue whatsoever can only be determined using one of the last steps. In fact, such cells are either required as connections (in which case they must be shaded), or they can be found to be unshaded because they lie in a cut off region, or they are part of a 2×2 squares with the other three cells known to be shaded. Nothing else works.

This allows for fascinating uniqueness arguments (steps which exploit the assumed uniqueness of the global solution), but this would take us too far. Unless one has reached a great confidence and familiarity with Tapas, I recommend not using uniqueness techniques. Still, such observations can be helpful to verify that one is still on the right track – they serve as a control mechanism of sorts. Virtually all the Tapas in today’s contain such elements; see the top row in Tapa 4, for example.

So much about solving techniques for Tapas. There is probably some interesting stuff missing, but this should do for the moment. Enjoy the puzzles!

Leave a Reply

Your email address will not be published. Required fields are marked *