From the Foxger’s Den #14: Star Battle (Corrupted Regions)
or solve online (using our beta test of Penpa-Edit tools)
This is a “Franken-Friday” puzzle variation.
Theme: Corrupted Regions
Rules: Variation of standard Star Battle rules. Two stars per row and column, but no region has exactly two stars. Each region must contain some number of stars other than 2, including possibly no stars at all.
Answer String: For each row from top to bottom, enter the number of the first column from the left where a star appears. Enter these numbers as a single string with no separators.
Time Standards (highlight to view): Grandmaster = 2:30, Master = 4:30, Expert = 9:00
Solution: PDF
When I first read the rules on this one, my immediate reaction was “How can that even be solvable?” Stared it for a minute before the first step hit me, then it fell without too much strain. Interesting variant; thanks!
I had a similar reaction to FireFox; in my case, I spent a few minutes trying to think of what deductions would even be valid under the rules, and I was pleased to see that the first one I came up with was indeed in the puzzle (and, I suspect, the intended break-in).
I ended up needing to bifurcate a few times (I blame my lack of skill with Star Battles in general), but I did like how much of the end game came down to trying to work out how one particular region could possibly not have two stars.
There’s no need to bifurcate. Just have to count very often how many stars are left in certain sets of rows or columns.
I should have been more clear. I have no doubt that bifurcation isn’t actually required by the puzzle; I just meant that I ended up stuck a few times and had to test guesses to make progress. As mentioned, I’m not particularly strong at even regular Star Battles, and I feel like I’m less able to “see” ahead multiple steps than other solvers to identify why a particular placement is unworkable. It certainly wasn’t meant as a criticism of the puzzle as much as an acknowledgement that the difficulty was a little ahead of where I’m comfortable (which of course also made finally cracking it that much more enjoyable).
I’m not very good at Star Battle, but I found this solve very smooth. One thing that helped me out was a technique that I borrowed from Heyawake: In a 2×2 box, there can only be one star. This was really useful here, because it allowed me to quickly put upper bounds on how many stars could be in a particular region, or given that I already knew that there were 3 stars in a region, and I could cover all but one square of that region with 2 2×2 boxes, that remaining square must contain a star. This technique isn’t as useful in regular Star Battle since every region contains 2 stars. But once you allow more than 2 stars in a region, covering becomes very useful.
Visualizing star placements as belonging to 2×2 boxes is a key thing to do in most Star Battles — either inside regions or just along pairs of rows and columns — and it is certainly unavoidable here.
I really am not sure why you say this is a Heyawake technique though. Without diagonal touching restricted there, I don’t see the connection. Its mostly no-touch puzzles where I have encountered the 2×2 rule, like the “submarines” type similar to Battleships.
Oh, I figured you’d knew that. I was more saying it as a suggestion to try to work out how it solvess, as this is a pretty nice solve. I didn’t have any need to look ahead, as I did all placements through direct deduction.
I would more say the 2×2 trick is a Tents technique. I use it the most there.
>> I really am not sure why you say this is a Heyawake technique though.
Well, it’s an application of the pigeon hole theorem: a region of shape S can only have N objects. Region R needs kN + r objects, and I can cover Region R with k copies of S and r 1×1 squares. Therefore, those r 1×1 squares all contain objects. I frequently use it in Heyawake usually with Nx2 shapes having at most N objects, so I associate it with Heyawake.
>> Visualizing star placements as belonging to 2×2 boxes is a key thing to do in most Star Battles
Maybe, but not in quite the way that I used it here. Or maybe its just that there were more opportunities to use it because of the increased number of stars in certain regions. In a standard 2-star Star Battle, unless you look at multiple cages, k (in my equation above) can be at most 1 (1 less than the number of Stars known to be in the region). In this puzzle, k can have larger values, allowing larger blank regions to be covered.
When I’ve looked at 2×2 regions in Star Battles, it tends to be along the lines of I know there’s a star in one of these 2 squares, so the other 2 squares in this 2×2 region must not be stars. I see that as somewhat different from accounting for possible stars by covering an area with 2×2 regions and looking for leftovers.
Beautiful Puzzle!
I delayed myself at first because I thought every region should contain a different number of stars…
Nice solve path ! I only had to guess if the smallest region would be empty or not, but maybe even there guessing would nog be required.
Fantastic Star Battle variation! I would love to see more of these.
So … when I transcribed this puzzle into Crossword Compiler — don’t laugh, it’s surprisingly good at being adaptable for electronic solving of most of the puzzle types here — … when I transcribed this puzzle into Crossword Compiler for solving, I managed to leave out the 1×5 cage completely. Unsurprisingly, that solve went completely nowhere. So I put the 1×5 cage in and started over, and sat down to solve the puzzle again.
When I entered my solution string confidently into the answer checker, it told me I was incorrect. I confirmed that I had correctly read the answer string off and that there were appropriate numbers of stars everywhere, and was thoroughly confused… until I noticed that the little downward notch that is at row 4, column 4 in the grid above had been moved over to row 4 column 5 in my transcribed grid. I fixed that error and then went on to solve the puzzle correctly on my third try. It’s a good thing I don’t time myself.
As it turns out, the alternate grid configuration I mention is also uniquely solvable (if somewhat more difficult than Grant’s version, and assuming I solved it correctly during my second solving pass), if you’d like to give it a try. I’d estimate that between half and two thirds of the solution path is different.
It took me *forever* (approximately) to get through this. I take comfort in knowing that I don’t need trial and error here, but eventually I made one guess that took me smoothly to the end. When I got the ol’ “incorrect”, I quickly saw that I had, very early on, put two stars in one region. Paint couldn’t undo that far so I started over and glided through in a few minutes.
15:27
The lower left quadrant took one third of the time.Very nice puzzle