# Is this N=3 Star Battle unsolvable?

Recently I've been solving some puzzles known as Star Battle, but I've come across a puzzle that no matter how many times I restart, I always seem to arrive at a contradiction.

Star Battle is played by placing stars in boxes such that every row, column, and enclosed area contains exactly $$N$$ stars. However, stars can not be vertically, horizontally, or diagonally adjacent to each other.

In this puzzle, $$N$$ is $$3$$.

A playable version of this puzzle (and the website where the puzzle comes from) is here: www.puzzle-star-battle.com

Am I consistently making the same logical misstep, or is this puzzle unsolvable? If it's possible, please provide the solution, otherwise some proof of its insolvability.

## 2 Answers

I didn't keep track of deductions (and I used brute force once) so no explanation, but at least I can say that

this puzzle is uniquely solvable!

Nice to see a puzzle with three stars (I've only seen one or two-star puzzles so far). I made a mistake once myself and ran into contradiction, so you might need to more carefully look into every step in your own logic.

• Aha! Great job! I see where I went wrong, I was eliminating all 6 squares under the long L shape near the bottom right, when only the first 4 should be... – Matthew Jensen Oct 14 '20 at 23:57

Here's an answer to explain the logic step-by-step without any need to brute-force the solution, in case other people get stuck on this puzzle (which is a tricky one) and need a resource to help them through. Throughout this write-up, green cells indicate a star, beige cells are confirmed empty.

Step 1:

Top-centre (right-angle): To get 3 stars in here, one must be at the lowest point in the shape. The other 2 must be in different halves of the shape’s top row. Spaces adjacent to the known star and to the 2 leftmost squares within this shape must be blank.

Top-right (fish-hook): To get 3 stars in here there must be 1 in the left-hand column and 2 in the right-hand column. Adjacent spaces must be blank.

Left-centre (distorted M): To get 3 stars in here there must be 1 at the lowest point in the shape, 1 in the first two spaces of its second row, and 1 in the corner-shaped section. Adjacent spaces which would complete a 2x2 block in other shapes can be shaded.

Bottom-right (hockey stick): To get 3 stars in here, there must be 1 in the leftmost 2 spaces, 1 in the next 2 spaces, and a third in the corner-shaped section. Adjacent spaces which would complete a 2x2 block in other shapes can be shaded. (From now on I will use ‘Blank out adjacents’ as shorthand for this...)

Step 2:

Left-centre (long G): We now see that there must be stars in the lowest cell and the third cell down, with the remaining one to be found in the topmost 2 cells. Blank out adjacents.

Top-left (distorted C): This means we must have a star in one of the 2 cells of the tail, one of the 2 central cells of the riser, and one of the 3 cells of the corner-shaped section. In fact, it cannot go in the topmost cell of this shape or it would leave only 2 stars able to be placed in the ‘7’ shape above it. This in turn means the star in the riser must be in R5C1 so as not to be adjacent to the other. Blank out adjacents.

Top-left (7-shape): Note next that one of the stars in this shape must go in the central riser, with the other 2 stars in the remaining cell-pairs at opposite ends of the shape.

Top-left (distorted C): This would be the final star in column 3, so the star at the bottom of the distorted C must be right at the very end. Blank out adjacents.

Note also that in column 2, of the 3 remaining spaces, the top 2 cannot both be a star, or none can be placed in the 7-shape’s central riser. Thus the lowest (at the tip of the distorted G) must be a star. Also the second space down in column 3 cannot be a star since it must be adjacent to the last star remaining in column 2. Blank out adjacents.

Step 3:

Now consider Row 1. We know there must be a star among the first 2 spaces, and that there must also be 2 stars among the spaces in columns 4-7. Thus all other spaces in row 1 are unshaded, which settles all of the stars in the fish-hook shape. Blank out adjacents.

Top-left (7-shape): We also now know that the star in the 7-shape’s riser must be in its bottom 2 cells, meaning the cell within this shape in column 4 must be left blank and a star must be in the cell to its right. Blank out adjacents. This sets the position of the star in row 1, the 2 remaining stars in column 4, the last star in row 2, and the last star in column 1. In turn, this sets the position of the last star in column 3 as being in R4C3 at the base of the ‘7’.

Step 4:

It isn't too obvious at this stage what our next deduction should be, but there are at least a few more spaces we can shade, knowing that a star cannot occupy them:

- R5C10 (adjacent to all 3 possible spaces for the last star in row 4).
- R14C6 and R15C6 (adjacent to both possible spaces for the last star in column 5).
- R11C7 (now adjacent to 3 spaces which must contain at least 1 star in column 6).
- R13C8 (if a star, only 2 stars could be legally placed in the bottom piece).
- R9C12 (if a star, only 2 stars could be legally placed in the key-shaped piece beside it).
- Then R7C13 and R9C13 (would leave space for only 1 of the required 2 further stars in this shape).

Step 5:

Let's now try and place the 3 stars in the bottom shape. If we assume that R13C5 is blank, we soon end up with a contradiction where there is only space for 2 stars in row 12:

Thus R13C5 must be a star, which enables us to place a couple more stars on the bottom row too:

Step 6:

Now consider the final 2 columns. We already have 2 stars from the fish-hook shape. We need 4 more – 2 of these must be provided by the square in the bottom-right corner (to get 6 in the bottom two rows) and the corner-shape at the end of the hockey-stick above it. The remaining 2 must come from the shape that stretches down the right-hand edge (there is only room in other columns to place 1 of this shape’s stars).

This means that R8C12 must be a star (and R10C13 cannot be).

Furthermore, we can now deduce the positions of 2 stars in the 'key' shape, simultaneously finishing off row 9.

Meanwhile, looking at column 6 we can see there must be a star in R1C6, with the remaining 2 stars for the column belonging in separate cell-pairs, whose adjacent squares can be shaded as empty.

Step 7:

Now consider the 4 central cells of the grid (highlighted pink below):

At the very most, there can be one star in this area. Note then that if we put a star in R13C7 we force a position which requires 2 stars to share this area in order for columns 7 and 8 both to have 3 stars – this is a contradiction, so R13C7 is empty and instead the last star in that bottom shape should be in row 14.

This then forces a star in R11C14 (since it cannot be adjacent to the star which must occupy either R13C13 or R13C14) and another in R8C14, enabling rows 8, 10 and 11 to be completed:

Step 8 (last one!):

Note now that R12C8 must be empty (the third star in this shape must be in row 13), meaning that R12C7 must contain a star, which completes column 7. There is now only one way to complete row 7, then column 8, then column 9, then column 10, then row 5.

Finally, add stars in R12C11, R6C12, R6C14 and a last one in R13C13 – the puzzle is at last complete!