Penalty theory in dynasty puzzles

Nikoli-style pencil-and-paper logic puzzles, like Sudoku, Yajilin, and many more, have very simple rules. But you can often build puzzles that require thinking in really cool ways, seemingly totally unrelated to what the rules literally say.

One example is commonly called penalty theory, which has been written about before in e.g. this Twitter thread by agnomy (Japanese), this blog post by chaotic_iak (English), or this blog post by redstonerodent (English). However, the way penalty theory is usually explained still seems to leave some people confused.

So here's a different description of penalty theory, which I personally find to be the most intuitive.

Note: This post is long! But don't worry: lots of space is taken up by pictures, and you only need to read about half of the post to understand basic penalty theory.

dynasty puzzles

The standard "penalty theory" applies to puzzles with these rules:

• Shade some cells in the grid.
• No two shaded cells can touch orthogonally (horizontally or vertically).
• All of the unshaded cells must form a single orthogonally connected group.

Puzzle types which include all of these rules are sometimes called dynasty puzzles.

There are many kinds of dynasty puzzles, but the one most conducive to penalty deductions is Heyawake. In Heyawake, in addition to the rules above, there are also "rooms" with numbers in them, which are required to contain that many shaded cells.

You can click the first image to try the puzzle, or click the second image to see the solution.

Heyawake also has one more rule, which we won't worry about for the purposes of this post. (But if you want to solve other Heyawake puzzles, make sure you learn the full rules!)

use-case

Penalty theory is about how to fit as many shaded cells as you can into a given space.

You may notice that both of the dynasty rules are restrictions on how the shaded cells can be placed. So penalty theory can only apply when there is some other constraint, like the rooms in Heyawake, that forces you to shade a large number of cells.

Here's an example. Like all logic puzzles, there's only one possible solution, so you probably can't solve it by guessing. But once you've learned penalty theory, it will suddenly go from basically impossible to fairly easy!

(This puzzle was created by @agnomy on Twitter.)

counting pools

To talk about penalty theory, I'm going to introduce the concept of a pool.

Consider all of the gridpoints in the grid. These are all the places the grid lines intersect.

You can think of shaded cells as connecting all the gridpoints they touch together. In the example below, the starred gridpoints are connected.

Also, some shaded cells connect gridpoints to the edge of the grid, like the triangular gridpoints in the example below.

A "pool" is just a group of connected gridpoints which does not connect to the edge. In the example below, there are 8 pools, all marked with their own shape.

To continue the metaphor, you could think of the edge of the grid and everything connected to it as "the ocean".

It's easy to count the number of pools when there are no shaded cells: just multiply (width−1) by (height−1). For example, this puzzle is 8 cells wide and 4 cells tall, so it starts with 7 × 3 = 21 pools.

consuming pools

The reason we care about these pools is that shading a cell changes the number of pools in a completely predictable way.

In particular, when you shade a cell, the pools corresponding to its four corners are combined to become a single pool. Some of them might be the ocean, like if you shade a corner:

→

Or an edge:

→

Or they might all be different:

→

In the corner example, whichever pool the starred gridpoint belongs to becomes part of the ocean. So the number of pools decreases by 1.

In the edge example, both the star and triangle pools become connected to the ocean. So the number of pools decreases by 2.

In the interior example, the four pools on each of the four corners are all joined into a single pool. So the number of pools decreases by 3.

You might be suspicious that I'm assuming different symbols belong to different pools – and rightfully so! But remember that the dynasty rules say that the unshaded cells must form a single connected group. If any of the different symbols drawn were actually the same, then you could draw a line of shaded cells through whatever connected them. This would "rope off" an area of unshaded cells, disconnecting it from the rest of the puzzle.

→

→

To summarize,

• Corner cells decrease the number of pools by 1.
• Edge cells decrease the number of pools by 2.
• Interior cells decrease the number of pools by 3.

But there's another way of thinking about this, which I personally like more.

• Placing a shaded cell costs 3 pools.
• Every edge of a shaded cell touching the border of the puzzle gives a discount of 1 pool.

(There's actually a good reason this works: every edge of a shaded cell touching the border of the puzzle corresponds to allowing two of the pools it joins to be the same.)

I'll give explanations with both styles of counting; you can use whichever one you like better.

but how do I actually solve a puzzle?

From all that, we get a nice formula:

remaining pools = (width−1)×(height−1) − (# corners) − 2×(# edges) − 3×(# interior)

or, with the other counting method,

remaining pools = (width−1)×(height−1) − 3×(# shaded)
  + # shaded on top edge
  + # shaded on bottom edge
  + # shaded on left edge
  + # shaded on right edge

At first, this might not seem very useful for solving puzzles, because you don't know how many corner and edge cells you're going to end up shading. But remember that penalty theory applies to puzzles where you're trying to shade as many cells as possible.

You have a limited supply of pools. So since corners and edges consume fewer pools, you had better shade as many of them as possible to avoid running out of pools.

This is confusing without an example. I'll demonstrate the technique on this puzzle (created by me).

(Click the image to open the puzzle in a new tab if you want to try it yourself or follow along.)

How do I start? Well, here are all the facts I know:

• There are 9 × 7 = 63 pools to start with.

• I have to place 19 + 2 + 2 + 2 + 2 = 27 shaded cells.

• Using the first counting method:

  • If I'm trying to spend as few pools as possible, I should shade as many corners as possible, since they're the cheapest. There are 4 of those.

  • If all the corners are shaded, I can only fit 10 more shaded cells on the edges: three on the top, three on the bottom, two on the left, and two on the right. (Remember, shaded cells can't touch.)

  • If I shade as many corners and edges as possible, the remaining 27 − 4 − 10 = 13 shaded cells must be interior.

  • Shading 4 corners, 10 edges, and 13 interior cells costs 4 + 2×10 + 3×13 = 63 pools.

• Alternatively, using the second counting method:

  • Shading 27 cells costs 3×27 = 81 pools without any discounts.

  • The biggest discount I can get is 5 from the top edge, 5 from the bottom edge, 4 from the left edge, and 4 from the right edge.

  • Therefore, shading 27 cells on this grid costs at least 81 − 5 − 5 − 4 − 4 = 63 pools.

So there are 63 pools available, and shading 27 cells on this grid costs at least 63 pools! That means I must shade as many corners and edges as possible, and there will be no pools left over (in other words, every gridpoint will be part of the ocean).

Great! Concretely, I can now start by shading all the corners.

I need to shade 2 cells in the top right room, and then some more cells will be unshaded because of the dynasty rules.

Now there's only one way to fit enough shaded cells on the top and right edges.

Both the star and the triangle have to connect to the ocean somehow. But I can only shade one more cell in the 2 room. So it has to be the middle one, so that both the star and the triangle can escape.

Now there are some nearly-trapped pools, marked above, which only have one way to escape. Also, shading the corresponding cell will create another nearly-trapped pool next to it, resulting in a chain of similar deductions.

The remaining 2 rooms both already have one shaded cell in them, and to fit enough shaded cells on the edges, one of them has to go in each of the 2 rooms. So I can mark all the non-edge cells in the 2 rooms as unshaded.

Again, there are a bunch of marked pools that only have one escape route, and again they will lead to more of the same:

Solved!

optional: deeper down the rabbit pool

So that's how to apply penalty theory to the whole puzzle. But what if you only want to use it on a certain part?

This puzzle has a big number in it, but if you try to apply penalty theory to the whole thing, you'll find that there's a lot of wiggle room. Is it possible to use penalty theory on just the big number?

It turns out it is! Consider just the 14 room, and pretend the rest of the puzzle doesn't exist.

Let's count:

• There are 35 pools.

• I have to place 14 shaded cells.

• The best I can do is 1 corner, 5 edges, and 8 interior. This consumes 1 + 2×5 + 3×8 = 35 pools.

• Alternatively, the base cost is 3×14 = 42 pools, and the best discount is 3 pools from the top edge and 4 pools from the left edge. This consumes at least 42 − 3 − 4 = 35 pools.

Nice! Again, I need as many corners and edges as possible, and all pools must connect to the ocean.

Some pools (namely 24, 32, 34, and 35) are already almost trapped, so I'll start by placing the shaded cells that let them escape.

Now some more pools (marked on the grid) are almost trapped, and I can also fill in the left edge.

The rest is straightforward.

Now it's time to look at the 10. Notice that some of its gridpoints are already part of the ocean.

Counting again:

• There are 25 pools.

• I have to place 10 shaded cells.

• The best I can do is 1 corner, 4 edges, and 5 interior. This consumes 1 + 2×4 + 3×5 = 24 pools.

• Alternatively, the base cost is 3×10 = 30 pools, and the best discount is 3 pools from the bottom edge and 3 pools from the right edge. This consumes at least 30 − 3 − 3 = 24 pools.

Hmm, there's one extra pool left over. That could mean one of two things: either I won't be able to shade as many corners and edges as I thought, or there'll be a pool that doesn't connect to the ocean.

In this case, the answer is a little tricky. Because of the 3 room, there will be another shaded cell touching the top of the 10 room. This shaded cell will touch either pools 1 and 2 or pools 2 and 3.

Hypothetically, let's say it touches 2 and 3. Then, pools 2 and 3 will be connected from the outside. But remember, I'm only looking at this subregion of the puzzle, and I'm pretending the rest of the puzzle doesn't exist. So from the perspective of the penalty computation, 2 and 3 aren't actually connected yet, and connecting them from inside the subregion would be illegal! (That would create a closed-off area of unshaded cells, for the same reason as described in the counting pools section.)

Therefore, pools 2 and 3 will remain separate pools within this region. And since I know there's only room for one pool left over, that means everything else has to connect to either 2 or 3, one of which will end up connecting to the ocean.

Now all the pools are accounted for, so I know that all pools must connect to the ocean or the remaining pool, and corners and edges are maximal.

The next step is a bit tricky, and you might find it easiest to just proceed by trial and error. But here's one reasonable argument: all of the starred gridpoints have to touch a shaded cell within the 10 room (either to fit enough edges or to let pools escape), which accounts for all 6 remaining shaded cells in the 10 room. So the 7th cell in the 5th row must be unshaded.

Now the cell marked in gray must be shaded to avoid trapping too many pools, and you should be able to solve the puzzle from there!

As promised, the original pool 2 does not connect to the ocean through the 10 region, showing where the inefficiency of 1 pool comes from.

comments

There are no comments yet.