# Surprisingly Challenging "Normal Difficulty" Star Battle?

I was demoing the Star Battle puzzle type to a friend, and got promptly embarrassed by having to bifurcate in order to solve this puzzle:

It says "normal difficulty 2-stars 10x10" on the tin, but either normal is not what I woud expect, or, what seems much more likely, I have a blind spot for some particular deduction.

This is where I got stuck, after employing some (IMO, occasionally pretty nifty) logic to rule out several possible spots for the stars:

(Rules recap: Distribute stars into the grid so that every row, column and region has two, and no two stars are adjacent to each other either orthogonally or diagonally)

and here's the solution I got by bifurcating (checking both options for r10c5):

Is there some way to solve this puzzle with deduction chains that don't extend all the way to the final box's star placement?

Having played some more normal difficulty puzzles on that site, here are a few things I've noticed:

1. The puzzles are algorithmically generated.
2. The difficulty between two puzzles in the same category can vary significantly
3. Most of the "normal" 10x10 puzzles I saw (and even most "hard" 10x10 ones) are set up such that you can easily deduce where a star is within a minute of starting.

I don't know how this website generates the puzzles - they could either have slightly different methods of generating the puzzles for normal and hard, or have them pre-generated and then categorized into normal and hard. Either way, this puzzle does not feel similar in difficulty to the other normal 10x10 puzzles, so this just happens to be a puzzle where the algorithm results in a "normal" difficulty puzzle that is actually hard.

I have found a way to make some additional progress without guessing:

Consider rows 5-7, as highlighted below. We know that the three rows must have 6 stars total, and four of those will be in the areas highlighted blue.

Now consider the green area on the left - if there are two stars in that area, A5 must be a star. However that forces D7 to be a star, and with a star in I7 or J7 there cannot be a second star in the green region. So A3 or A4 must be a star, allowing us to cross off B3. We also know that there must be a star in the yellow area (E5, F5, F6).

The next step comes from the deleted comment with a small addition

If you look at the first three columns, you can determine that the two stars in the upper-left shape must be in those three columns. Additionally notice that there must be a star in B5 or C5, and we also know there must be exactly one star in D5-7.

The next step is a bit of a guess-and-check, but has motivation for checking the particular spot.

We know that there must be at least one star in F-H1. If we could get a similar shape in the upper left, it would mean there would be one star in A-C1. We try a star at A2, so A4 must be the other star in the column and B7 must be a star as well. With a star in I7 or J7, the region with C5, D5, and D6 can't fit two stars. So A2 is not a star.

So there must be a star in A-C1, and a star in F-H1. With I1 and J1 ruled out, we now know there is a star in J2.

I haven't found a good way to go from here to the end without making a guess and checking it. If you play around with it here you can get a sense for what makes this particular puzzle difficult - if you make a wrong guess it will almost work, and the error won't show up until you've got it almost completely filled in.

Update Dec 2022:

I decided to take another look at this, and did find a decent way to get to the end from where I got stuck. The main key was that I looked at where stars must be in row pairs.

Here every contiguous blue or green marking indicates where a star must be, sometimes going across regions. Notice that in the top three rows there are four places that must contain stars and one determined star. So there must be a single star between A3 and the area I've got in yellow. It's easy to see that if A4 is a star there will be multiple other stars determined, so we should check what we get if it is not A3 that has a star (and therefore somewhere in the yellow area).

From there, it makes it easy to finish the puzzle. This is still just a guess and check, but with more reason as to why I made the particular guess.

As I've done more puzzles on that site I've found quite a few where I couldn't make progress without guessing and checking. It is nice to be able to see right away a square that either cannot or must be a star, but it's also helpful to see squares that, if they either were or weren't a star, would lead to a number of immediate deductions. Those squares are useful to start with if you do need to guess and check.

• At most 4 stars can be in the blue region: I7, J7 might not contain a star.
– daw
Aug 18, 2022 at 6:11
• @daw I7, J7 must contain a star - if H9 and J9 were stars, the region below it would not have room for two stars. Aug 18, 2022 at 14:44
• To "easily" see that either I7 or J7 must contain a star, we can consider their region with the region below it in the bottom right corner: it's possible to entirely cover those two regions using only four 2x2 squares. Since a 2x2 square can contain at most one star, each of those four squares must contain exactly one star, and one of the squares contains I7, J7, and no other available squares. (This is the technique I used to deduce that there must be two stars at the bottom part of the columns 9 and 10, which rules out stars from the middle squares)
– Bass
Aug 18, 2022 at 15:40
• What do you get from checking that the yellow area has a star? It seems there are multiple possibilities there. Dec 22, 2022 at 5:42
• @justhalf thinking about it again, it's actually more about A3 not being a star. I reworded it a little bit to make that clear. Dec 23, 2022 at 7:06

I will be using letters for the columns and numbers for the rows.

Firstly, I will establish some facts. I think you already know them because it took me a long time to get the board to where you got to and I needed to use these facts to do so.

Fact 1:

The shape containing A8 has one star in row 8 and one in row 9. This also means that shape containing J9 has one star in the last three blocks of row 9.

Fact 2:

Any two rows or any two columns must contain exactly 4 stars. This isn't much of a revelation, but specifically columns I and J must. Since the shape containing J1 must have 2 stars, and there is an additional star in I7/J7, this means that the last star is in I9/J9/J10.

Fact 3:

The two stars in the shape containing J1 cannot be in column I because this would not allow the shape containing F1 to have two stars.

Fact 4:

By fact 3, lets assume that both stars of the shape containing J1 are in column J. Then there must be a stars in I7, G6, I9, and E10. Thus there cannot be a star in B8, nor D7 which forces a star in B5. But then we can only place one star in the E5/D5/D6 and we need 2. Thus, there is exactly 1 star in column I and one in column J for the shape containing J1, and one star in each column not in this shape - i.e. the rest of the column.

Fact 5:

The shape containing H1 must have at least one star in column H, and at least one star in row 1.

Now lets assume

A star in A5. Thus a star in D7, B8, and D9, F6 and H6, leading to J7 and I8 (Fact 4). But then we can't fill row 10.

Thus

there is no star in A5. This means the pair just above must contain a star, so there is also no star in B3.

Can we now solve it? No, not really. But it is at least progress!!

So lets continue to see if we can make more progress without backtracking from the end of the puzzle. Lets start from where we left off

So, now lets assume

a star in H9. There is one more in this shape, and it can't be J9 (shape in row 10 can't be filled). Therefore, we need to fill J10 and I7 (Fact 4). Thus G6 and F8 are the only options for that shape. That means B5/C5 and D5/E5 are pairs, and there can be no stars in D4/E4 or D6. Thus A6 has a star, and both stars in that shape are in column A, so we can eliminate all other candidates in that column (A1/A2/A8/A9). D7/B8/D9/C5/F10 quickly follow. The only options for the shape with G1 is G1 and H3. Since there is a star in A3/A4, B4 can't have a star, making B1/B2 a pair, so C1/C2 can't have a star, making C3 the only other option in that column. And now we see many problems, so we know the original assumption is wrong, there is no star in H9.

Now since Fact 4, and we know both columns I and J must contain 4 stars between them, we know that

there is a star in column J9/J10 of the shape containing those squares, leaving only I7 as the potential remaining star for column I in that shape.

Now we have our first filled star! And the rest of the puzzle follows almost trivially.

• I didn't check the entire answer very deeply yet, but it seems that after the first image in your answer, you proceed to prove that there cannot be a star at H9, but then misclick that cross into the I9 square, where it would indeed would solve the puzzle. Or maybe I'm misunderstanding something?
– Bass
Aug 16, 2022 at 5:48
• After proving there is no star in H9, it was a simple deduction to say that there must be a star in I7. The picture does not have the 'X' in H9 which it should have. Aug 17, 2022 at 13:42
• It would help your answer if you made this simple deduction (that there cannot be a star in I9, and that there should be a star in I7) explicit. Aug 17, 2022 at 14:04
• Wait, to me it seems that you ignore the possibility (from a deductive standpoint) that there could be a star in J7 instead of in J9/J10? Aug 17, 2022 at 16:55
• Agree with T. Verliefde here. J7, I9, E10, G10 seem consistent so far with H9 not a star (in fact, part of the wrong solution posted in OP) Aug 18, 2022 at 2:24

To keep track of the progress, here's a Wiki answer combining everything we have been able to deduce using techniques that don't amount to "try it out and see if it fails at some later point".

Here's the situation from the question again:

From Rob Watts' answer, we know that there cannot be a star at r3c2: if there were, then r5c1 would have to be a star, which would force three stars onto row 7: one in columns 1-2, one at r7c4 and one in columns 9-10.

There was also an encrypted comment (that has been deleted since, so I cannot attribute it to the commenter) at the question, encouraging us to consider the three leftmost columns together. This is useful, because we know the stars in the bottom box must be on different rows, which lets us deduce that the top left box must have both its stars at the three leftmost columns.

Adding those deductions, here's what the grid now looks like:

There are definitely more (short) deductions to be made, which can lead to solving the puzzle.

I will state upfront that I think these 10x10 2* puzzles are just generally difficult, even on "normal difficulty".

A few of these points were already made in different answers, but I repeat them for completeness:

A)

For C9, there is one star in R1/R4, and one star in R7/R9. Stars in both C9R1 and C9R4 would not allow two stars in the shape containing C6R1. Similarly, there cannot be stars in both C9R7 and C9R9, which creates problems for R5 or R6 (see image).

B)

There cannot be a star in C1R5 (green), since this would leave C5 (red) without any stars. From this it also follows that C2R3 is not a star.

C)

Because of point A, we have exactly one star in C8 R1/R2/R3, since two stars would not allow any stars in C9R1/C9R4. Additionally, there cannot be a star in C8R4, since this would force a star in C9R1 and thus not allow any stars in C8 R1/R2/R3. Similarly, there cannot be a star in C6R2, since this would force two stars in C8 R1/R2/R3.

D)

We can determine that for the shape containing C1R1, the stars should be contained in the first three columns. The following image shows the coloured regions in other shapes which must contain exactly one star. Since these account for only four stars for three columns, it must be that the purple region contains two stars.

E)

There cannot be stars in both C2R5 and C4R5 (green), since then the solution would not be unique in regards to the stars in the red areas (see image). If you dislike relying on uniqueness, we are also unable to put two stars in C5.

F)

There cannot be stars in both C4R5 and C4R7, since then we can't place two stars in the shape containing C1R8, keeping in mind that there should be one star in R8 and one star in R9 for that shape. Combined with point E, this means that there cannot be a star in C4R5 at all. This further allows us to determine that there has to be a star in C5R5/C6R5, which allows us to eliminate the squares above and below.

G)

We can also eliminate the possibility of a star in C8R1 (see image). This further makes C7R3 not have a star either.

H)

C2R2 also cannot contain a star, since this would not leave space for two stars in the shape containing that cell.

I)

We can also rule out a star in C8R9 (green), since this would lead to no possibility for two stars in R2 (red), following the same argumentation as Trenin already made in their answer. This further makes it clear that C10R10 contains no star. [This step needs a lot of deductive steps, and as such doesn't really fit with the question prompt. I am leaving this in to not cause confusion in regards to the later images, which do include the crossed out cells based on this. For the later steps, these are actually not necessary.]

J)

We can also deduce that there cannot be a star in C4R4 (green), since then we would end up with two stars in C10 within the shape containing C10R1 (red), which we have earlier deduced not to be possible. This also makes it such that there has to be a star in C4R8/C4R9, which eliminates the squares on their sides.

K)

We can also determine that there cannot be stars in both C3R1 and C3R3 (green), since we then cannot place two stars in R8 (red). This also allows us to place a star, since now C3R5 has to contain one!

And our first star allows us to fully complete the puzzle!

• Ooh, bifurcation and reasoning from uniqueness, you're really into the deadly sins, aren't you :-)
– Bass
Aug 18, 2022 at 18:28
• (: Well, the uniqueness is not necessary (see edit for point E), and I would argue that there is not an awful amount of bifurcation going on in most of the points. The main exception would be point I, which is not actually necessary, I found out. Aug 19, 2022 at 10:19