Reading Difficulty: 2-3/5
Prerequisites: Some graph theory would be nice. Read the previous post here if you do not know the rules of Heyawake.

Last time, we left off looking at this very challenging Heyawake puzzle:



https://puzz.link/p?heyawake/10/10/00000112244000000000003s00003s000000-1f2

I think it's safe to say that this is basically impossible to solve using basic logic alone, without a ton of guessing and/or trial and error. In this post, I will discuss a mathematical methodology for solving puzzles like the above that fundamentally changes the feel of this puzzle genre.

Credit: Heyawake Penalty Theory was originally discovered by "まり餡" (@agnomy on Twitter). The methodology was then generalized and propogated by Ivan Koswara.

If you don't care about the math and just want the method, scroll down to the section "Summary of the Penalty Method".

---

The Math

The key to these puzzles is that there are so many black squares that the number of ways to fit them all is extremely small (hopefully just one way, otherwise the puzzle has no unique solution, which is considered bad). This leads to the following natural questions:

• What is the maximum number of black squares you can fit in a region, such that no two are adjacent and the white squares are connected? (We do not consider the essential rule and/or the interaction between multiple regions/rooms, it's hard to reason about them mathematically.)
• By examining the equality case in the maximum bound obtained, what restrictions does this imply on the configuration of black squares, if the number of black squares were indeed maximal?

The grand scheme will be to use the conditions to obtain three different bounds on some variables that relate to the total number of black squares. Figuring out what those variables should be is motivated by looking at...

The Connectedness Condition

The key to thinking about this condition mathematically is to draw a graph whose vertices are the white squares, such that there is an edge exactly when two vertices are orthogonally adjacent.



As you can see, the connectedness of the white squares is equivalent to the connectedness of the graph. That is, the graph is in one piece. Let's call this graph .

Adding in a black square is identical to deleting a vertex (and all of its edges) from .



Now it's disconnected. In theory, adding too many black squares (deleting too many vertices) would have to eventually disconnect the graph. We can capitalize on this intuition via the following theorem:

Theorem: Let be a graph with vertices and edges. If is connected then we must have .

Proof

To use this, we first compute , the number of edges. Suppose that the board is . If there are no black squares, then is an square lattice. So, an easy argument will give the starting number of edges as .

Now let's start adding in black squares. Shading a square black removes a vertex and its edges. How many edges? Well, that depends. Is it a corner square? A square on the edge? Or, is the square in the middle/center?



The number of edges removed is different for each of these cases, and this is what motivates dividing the total number of black squares into a sum of three variables:

• 
• 
• 

This gives as the total number of black squares.

With this, we can now compute the number of edges. Observe that a corner black square will delete edges, an edge square deletes edges, and a center will delete edges. It follows that:
A possible issue to keep in mind, however: Couldn't deleting a vertex delete less edges than what is listed above? For example, this "center vertex" deletes only edges:



Fortunately, this situation can never happen, because two black squares cannot be adjacent!

In sum, we may conclude that the number of edges in the graph must be . Next, we need to compute the number of vertices. This is really easy: Every black square deletes exactly one vertex. Hence . Plugging this into the theorem, we obtain the following bound:
This rearranges to:
This is the first bound we need. Note that this is not quite a bound on , so we need to find some other inequalities.

Important Exercise: Prove or convince yourself that is the most number of edges that can be deleted from without disconnecting . (Hint: The expression is , now extend the Theorem.)

Bounds Along the Boundary

is the number of black squares along the boundary. What is the maximum value of for an board?

The trick is to subdivide the boundary squares into the following pieces:



Essentially, we put an L-tromino piece over each corner, and then fill the rest of the boundary with dominoes. Key Point: Each of these pieces can contain at most one black square! To count the number of these pieces:

• There are L-trominos
• Along the bottom edge, the tetronimoes take up squares, so the rest of the squares are taken up by dominoes. Hence dominoes on the bottom edge. Doing the same for the other three edges, we get dominoes in total.
• In total, this is pieces, so .

There's a bit of a gap in this logic though: We can only tile the sides cleanly with dominoes if and are both even. If either are odd, then we'd need a lone piece somewhere, so the pieces could look like this:



It doesn't really matter where the is. All that matters is that each region can have at most one black square. Now, to fix the above math to account for both the odd and even cases, we can just introduce the ceiling function. That is, there are dominoes and pieces. Altogether, we find the bound:

Exercise: Convince yourself that this bound is tight. That is, it is always possible to obtain black squares on the boundary of the grid.

Now we have two inequalities, but it's not enough. We need one more inequality. The next inequality we get is absolutely ingenious. Buckle your seatbelts and steel yourself, because the logic is absolutely wild. Prepare for the greatest piece of mathematics you have ever seen.

The Final Inequality

because there are four corners.

Putting it All Together

We have the inequalities:
We need a bound on . Fortunately this is really easy: Just add all the inequalities! This gives:
The RHS might not be divisible by , so we'll leave it as this. Our first goal is essentially done! We've found some sort of bound for .

Now, for the second goal: Define to be the score of a configuration of black squares, and define to be the upper bound we got. How can we use the "closeness" of the score to the "theoretically maximum" score to deduce properties of the configuration?

Penalty Theory

Suppose the score was equal to the theoretical maximum, i.e. . What would that mean? Looking back at the three inequalities we got earlier, that would have to imply that each of those inequalities were, in turn, equalities. This means that:

• We deleted the maximum possible number of edges from the white-square graph .
• Every piece along the boundary of the grid has a black square.
• Every corner square is black.

If instead the score was strictly less than the theoretical maximum , then certain factors, called penalties, must be causing this. Penalties decrease the counts , , and , widening the gaps between these values and their corresponding theoretical maximums. Evidently, the sum of these gaps must be .

More precisely, these gaps are given by the following counts of penalties:

• , which (by an Exercise) is the most number of edges we may delete from the white-square adjacency graph without disconnecting it.
• , which (quite directly) is the deviation from the maximum of the number of black squares on the boundary.
• , which is the number of corner squares that aren't black.

Some notes on how to spot/count these easily:

• If , that means that there can't be any loops that can be formed by traversing white squares. For instance, there cannot exist a pool of white squares. More generally, can be determined by counting the number of such white-square loops, with the caveat that you cannot count a loop that is formed by the loop segments of previously counted loops. For example, a pool of white squares will form only loops of white squares, not .
• can be computed by first dividing the boundary into pieces in the way we did before. Then, count the number of pieces that are empty.
• can be counted by using your fingers.

Example

To reiterate, the importance of these quantities is that they must satisfy:
In certain specially-constructed "penalty Heyawakes", the RHS would, ideally, be a low number. If the LHS is low, this can set some major restrictions in how the black squares can be arranged, especially if you can spot some obvious instances of penalties right off the bat.

---

Summary of the Penalty Method

1. When a Heyawake puzzle seems difficult, and the total number of squares seems more or less known and near-maximal, consider Penalty Theory.
2. Count the number of black squares and triple it. This is the score of the puzzle.
3. If the board is , compute . Then, subtract the score obtained from the previous step. The resulting number is the total penalty, .
4. must be equal to the sum of the following three quantities:
   • , the number of corner squares that are not shaded black.
   • , how far away the number of black squares along the boundary (including corners) is from the theoretical maximum.
   • , the number of loops you can form by traversing white squares. In counting this, do not count loops that can be formed by segments from previously counted loops. More Formally
     is the maximum number of edges that can be removed from the white-square adjacency graph without disconnecting it.
   We call these the "penalties".
5. Look for easy-to-spot instances of penalties. If you can find penalties, then you have found all penalties, meaning that the rest of the grid cannot have any penalties (this is a TON of information!).

Example Solve

Let us solve the following Heyawake: https://puzz.link/p?heyawake/6/6/00c011021020b10



Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Your Turn!

1. Solve my "Floating orb": https://puzz.link/p?heyawake/6/6/000c0i0010gsb10
   Hint
   As before, there is exactly one penalty. The penalty should be caused by the region.
2. Solve my "P-Pentomino": https://puzz.link/p?heyawake/6/6/00k4000643g0c0
   Hint
   The pentomino creates a loop. Also, don't forget standard Heyawake rules!
3. Solve my extremely sus puzzle: https://puzz.link/p?heyawake/14/12/000000000000c450pnj72cop105k0000000000000041u71oa02g070e10803c0-310051
   Hint
   and so the total penalty is . The existing shapes should reveal all penalty locations off the bat.
4. Solve this puzzle by @agnomy: https://puzz.link/p?heyawake/10/10/04080g1020490i14280000000000vv000000f5526
   Hint
   Total penalty is . Think about which room is likely to contain penalties. You won't know exactly where the penalties are, but identifying the general location is a huge step.
5. Solve this puzzle by Ivan Koswara: https://puzz.link/p?heyawake/8/7/060o00000081g2000000-121g
   Hint
   Total penalty is . Observe that if the top-left corner were not shaded black, then this would contribute both a penalty and a penalty.
6. Solve another one by @agnomy:
   https://puzz.link/p?heyawake/12/12/00000o0003063cc0o00030000000008020080a4a92a02008020000-2811111111
7. Solve this puzzle by Plurmorant:
   https://puzz.link/p?heyawake/10/10/00000112244000000000003s00003s000000-1f2
   Hint
   Total penalty is . This should let you completely solve the room. To continue, look carefully at how the right edge can be filled in order to prevent creation of any more penalty.
8. Solve my variant Heyawake, in which the board is a rotated diamond shape rather than a rectangle. Ignore the outer region when solving. Answer check will not work, you should verify correctness manually. https://puzz.link/p?heyawake/v:/23/23/0000006000280011000g40080g040202508118p0g0048000k0k02g5012180g8a0812g4040200g10020g00880014000600000000080002g000h0004200104008080260g0g09043121000481g0900012000840020800g0hg401010020800420008g000k0001000g-56h1Ok Hint
   First, rederive the penalty theory for boards of this shape.

---

...and that's all I have for you in terms of Heyawake penalty theory! I hope this was fun to read. It's a remarkable application of math!

Have a merry new year.