Classics Collection

Classics Collection: Star Battle

Hi folks,
it is time for another installment of our Classics Collection series. Today’s post is about Star Battle, a fairly popular Placement Puzzle style. Actually, this puzzle type is not ideal for our beginner series format, due to the size constraints (see the explanation below the example), but I have decided to use it anyway. Here is the new set: Star Battle

Rules: Place stars in the grid such that each row, each column and each outlined region contains exactly the given number of stars. The stars cannot touch each other, not even diagonally.

Example and solution:

First, regarding the name of the puzzle style: There is no “battle” involved anywhere, but I prefer the English name to the German one (“Doppelstern”) anyway, because the latter suggests that puzzles of this type should use two stars in every row, column and region. Of course one could change the German name if a different number of stars is to be used, but the corresponding designation for the single-star version sounds rather clumsy.

Now, let us discuss suitable puzzle dimensions. Let NxN denote the grid size (clearly the grid has to be quadratic) and K denote the number of stars in each row/column/region. Even if we forget about the regions entirely, it turns out that the task of placing stars in the grid such that each row and column contains K stars without any touching has no solution if N is smaller than 4K, that there is only one solution up to isomorphism for N=4K, and that the solution space for N=4K+1 is still very small.

With K=1, for instance, we can place stars in the cells R1C2, R2C4, R3C1 and R4C3 to obtain a solution in a 4×4 grid (and the mirror image of this quadruplet is the only other solution). There are just three substantially different solutions for N=5, meaning that every other solution can be reached from one of those via rotation and reflection. With K=2, the fun starts with 9×9 grids, but sometimes it feels this is too rigid.

In order to get an idea what this is about, let us assume we have K=2 and N=6. We have already seen in other Placement Puzzles (Tents and Battleships) that any 2×2 square can only contain one star. This means that a pair of adjacent rows (or columns), which comes down to a 2×6 rectangle, can only accommodate three stars, but four would be required to satisfy the placement conditions.

It may appear that K=2 and N=7 will do (by placing a star in the first, third, fifth and seventh column for a pair of adjacent rows as above). This works only locally, though, not for the entire grid. N=8 is the smallest grid that admits a solution with two stars, and the only possible solutions are larger versions of the two 4×4 constellations from earlier. Even in a 9×9 grid, the location of just a few stars will have sort of a “ripple effect” that limits the possibilities throughout the grid severely.

If one ever encounters a puzzle with N=4K in a contest (I was told this happened once in a WPC final, when this puzzle style was still in its infancy), it suffices to check which of the two possible arrangements is compatible with the given regions. However, this is already impractical for a grid size a little larger than 4K, which brings us to the matter of actual solving techniques.

For the sake of simplicity, I will discuss solving steps for K=1 (the first six puzzles of today’s set) and only make a few short remarks regarding the application to the K=2 case afterwards. Even though K=1 and N=5 has a limited potential for the placement of stars, this size is useful to approach the solving logic of this puzzle style.

The first thing I would like to emphasize is that I find it helpful to mark not only the cells containing stars, but also to check all the cells which are determined to be empty, and that I recommend doing the same (at least in the early stages of the solving path). This can be very time-consuming; on the other hand, virtually all the non-trivial solving step serve to eliminate locations for the stars, and it is important to keep track of the progress one makes. Only the more experienced solvers can afford to save the time.

Now, where to begin. If a region consists of a single cell, a star can be entered immediately, but let us stay reasonable; in practice one will hardly ever encounter such a situation. The next best thing is a region of two or three cells. Let us have a look at the puzzle SB1 from the PDF file. Either R4C4 or R5C4 must a star. As a consequence, neither of the cells R4C3, R5C3, R4C5 and R5C5 can accommodate a star, since they all touch both cells in the small region.

In Part 4 of the Classics Collection, “Regional Polyominoes”, we called these cells killer cells, and the principle is pretty much the same here. Note that killer cells can also occur for regions of size 3 (or more); for instance, R5C2 in the same puzzle is a killer for the region of three cells nearby. It is worth mentioning that killer cells can exist in the K=2 situation as well, they are just a little harder to spot.

This is not all there is about the domino region in SB1. Since this region lies exclusively in Column 4, neither of the cells R1C4, R2C4 and R3C4 can contain a star, or else we would have two stars in the same column. Once again, this is something that works with larger regions, too. For instance, there is a region within the top row of SB2, hence no other cell in the top row (R1C1 or R1C2) can contain another star. Something similar applies to the region in Column 1.

There is a “dual” technique based on a region which encompasses an entire row or column. For example, a star has to lie somewhere in the rightmost column of SB1 according to the rules. But the same region is not supposed to contain a second star. Therefore, the cells R3C3 and R4C3 must be empty. A similar situation occurs in SB3, and a special case can be seen in SB4: The corner cell R1C1 must contain a star, because every other location in this region would either kill the top row or the leftmost column.

Most of the six small puzzles in this set have various starting points of these types. They yield numerous empty cells, and it is important to realize that one can follow up on these deductions. Each cell found empty in one of the above ways reduces the size of another region, leading to more progress. In the simplest case, only one cell in a region is left, as in SB1: The cell R4C2 is the only one left in the tromino region following the earlier steps. The same happens with R2C2 in SB2.

In other cases, the “reduced” region still has a size larger than 1, but the previous techniques can be applied. In SB3, for instance, the cell R4C3 is a killer for the adjacent tetromino region to its left, and once it is marked as empty, we are left with a reduced region which lies fully within the bottom row. Also, the large region in this grid completely covers Column 1, leading to four empty cells in the top rows, and as a consequence the previously mentioned tetromino shape covers the entire reduced Column 2. And so on.

Some of the techniques we have seen work with more than one region. The two L-shaped trominoes in SB4 must “share” the two stars from Column 2 and Column 3, and thus no other cell in the same columns can contain a star. An analogous argument applies to the two leftmost columns of SB5 or the two top rows in SB6. On the other hand, the two bottom regions in SB6 completely cover Row 4 and Row 5, which means that the other cells belonging to the bottom-left region must remain empty.

Let us go back to the “killer” technique from the beginning. Sometimes it makes sense to study several small regions at the same time. We know that the 2×3 block in SB4 comprised of the two tromino regions must contain two stars, and this does not work if either R3C2 or R3C3 contains a star. (Each of these cells is a killer for the neighboring region, but the argument stands for itself. This is noteworthy because such a formation is also relevant as a single region in Star Battle puzzles with K=2.)

In general, it is a good idea to study clusters of small regions. This may not sound like a big deal for the first six puzzles of the set, since more or less everything is small here, but the same advice also applies to larger grids. Sometimes there are groups of regions which admit only very few arrangements of stars, even if every single region yields several options.

Killer cells can also work with groups of regions. The cell R3C1 in SB4 must be empty; a star in this position would imply stars in R2C3 and R4C3 (R2C2 and R4C2 both touch the hypothetical star), but we cannot have two stars in Column 3. Likewise, R3C4 in the same grid must be empty. Furthermore, a cell can kill a region indirectly. For example, a star in R4C4 of SB5 leaves only one cell in the bottom-right region, namely R4C2, but that one lies in the same row. Similarly, a star in R5C2 of SB3 would kill the corner region to its right.

What we have seen here is actually overkill for puzzles as small as this. In many cases, there are half a dozen arguments why certain cells cannot contain stars, and often the very simplest arguments will do. Still, it is worth knowing such techniques, because they may be necessary in puzzles with K>1. In particular, a single star yields empty cells for the rest of the same row and column in case of K=1, but not in larger puzzles, hence progress tends to be much slower.

Most of the logic remains valid, though. For instance, we have a region in SB9 which lies entirely in a single column, and this region must contain all the stars of that column. On the other hand, there are regions which encompass a full row or column (e.g. Column 4 of SB7), and it does not matter that we have K=2 instead of K=1; the rest of the region must remain empty in any case.

On other occasions, there are groups of regions lying within the same number of rows or columns, such as the three relatively small regions in the three top rows of SB10, or conversely groups of regions completely covering the same number of rows/columns. In my experience, however, the most common starting points for K=2 (or larger) are still small regions and killer cells.

There are a few shapes which immediately allow the placement of one star (or both, in extreme cases). There is only one way to place two stars in the T-shaped tetromino region in SB7, and at least one star can be entered in the P-pentomino in the same grid. One should especially keep an eye open for regions which fit in a 2×3 box, but slightly larger regions are often useful as well.

In SB8 there are many small regions grouped in the center of the grid, and there is a considerable number of killer cells. Some of them (R3C4 or R3C7) would make it impossible to enter even a single star in a neighboring region; others (R1C7 or R4C7) would leave room for one star but not for two. Note that, in the case of K>1, a cell be a killer for its own region: If a star were placed in the cell R7C5, no second star would fit in the same region.

I think this is enough on solving techniques. I hope you enjoy the puzzles!

Leave a Reply

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