Penalty theory in wall puzzles

2024-07-27 23:45 -0400 puzzles logic puzzles math

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.

Wait, it feels like I've written this intro before...

On July 27, 2022, I published a blog post (linked above) about a graph-theoretic argument often referred to as "penalty theory" applied to a Nikoli logic puzzle.

Now, on July 27, 2024, I am publishing a blog post about a graph-theoretic argument often referred to as "penalty theory" applied to a Nikoli logic puzzle.

Obviously, I have just copied and pasted the entire post and changed the date, so there's really no point in reading this one. But in case you still want to anyway, this post is about the "gridpoint counting argument" briefly described here by chaotic_iak, which I'll again try to explain as intuitively as possible.

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.

wall puzzles

This version of "penalty theory" applies to puzzles with these rules:

Shade some cells in the grid.
No 2×2 region can be fully shaded.
All of the shaded cells must form a single orthogonally connected group.

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

There are many kinds of wall puzzles, but the one most conducive to this style of deduction is Nurikabe. In Nurikabe, in addition to the rules above, there are also numbers on the grid. Every orthogonally connected unshaded group must contain exactly one number, which must be the number of unshaded cells it has.

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

use-case

In general, these kinds of global counting arguments work on puzzles that are "extreme" in some sense. If you read the post about Heyawake penalty theory, for example, you know it only applies to puzzles which are extreme in a specific direction: it works when the number of shaded cells required by the clues is really big, making it hard to fit that many shaded cells while following the rules of Heyawake.

One cool aspect of Nurikabe penalty theory is that it works in both directions. There's one version that works when the numbers are really big, and it's hard to fit that many unshaded cells while following the rules, but there's also another version that works when the numbers are really small, and it's hard to cover enough area with unshaded cells while following the rules.

I'll call these "minimization" and "maximization" respectively. The second version is easier to get started with, so I'll talk about it first.

part 1: gridpoint maximization

As mentioned, this version of penalty theory is about how to cover as much space as possible with a small number of unshaded 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 gridpoints

Just like in the Heyawake post, the main thing we'll be thinking about is the gridpoints in the grid, which are all the places the grid lines intersect.

However, for Nurikabe, we'll also care about what you get if you extend these to the edge of the puzzle.

I'll call the first kind internal gridpoints, and the ones on the edge external gridpoints.

Now you can look at the gridpoints that every island (group of unshaded cells) touches. Here, the island with the "3" touches the starred gridpoints, including 6 internal gridpoints and 2 external gridpoints.

We're going to need to know the total number of internal gridpoints, which is easy to count: just multiply (width−1) by (height−1). For example, this puzzle is 8 cells wide and 4 cells tall, so it has 7 × 3 = 21 internal gridpoints.

touching gridpoints

The reason we care about these gridpoints is that the rule "No 2×2 region can be fully shaded" can actually be rephrased as "Every internal gridpoint must be touched by at least one island".

The solution shown on this puzzle breaks the "no 2×2" rule because it has a fully shaded 2×2 region on the right. But another way of seeing this is that no island touches the triangular gridpoint.

These two versions of the rule are the same because if you shade a 2×2 region, no island can reach the gridpoint at its center; and in the other direction, if you have a gridpoint touched by no islands, the four cells surrounding it are shaded, creating a 2×2.

At first, this version of the rule might seem unnecessarily more complicated. But notice that most gridpoints can only be touched by one island in the first place. The only way to touch a gridpoint twice is to have diagonally touching islands, like with the gridpoint marked with a diamond here.

Okay, so now we know we can count the total number of gridpoints touched by just adding up the number each individual island touches, and we'll only be off by however many diagonally-touching islands there are. We'll come back to that later. But how many gridpoints does each island touch?

Well, a 1-size island touches 4 gridpoints, its four corners. A 2-size island touches 6 gridpoints, and a 3-size island touches 8 gridpoints. So it looks like an island of size n touches (2 + 2×n) gridpoints. This is mostly true, because usually when you add a new unshaded cell, you add 2 more gridpoints being touched.

→

But it's possible to add an unshaded cell to an island and only touch 1 more new gridpoint:

→

When does this happen? It's exactly when adding that cell to the island creates a new unshaded 2×2 region. Intuitively, every unshaded 2×2 region represents a gridpoint (the one at its center) that the island touches more than it needs to. So the correct formula for number of gridpoints touched by an island with size n is:

2 × (1+n) − (# of unshaded 2×2s)

You already know all the island sizes when you look at a puzzle, since they're given by the clues. So you can get close to the total number of gridpoints touched by:

adding 1 to each clue,
adding them up,
and doubling the resulting number.

Nice! This is pretty easy, and you know it can only be off in two ways: it counts 1 extra for every pair of diagonally touching islands, and 1 extra for every unshaded 2×2.

Going way back to the reason we cared about this in the first place, remember that the rules say that every internal gridpoint must be touched. We know the number of internal gridpoints. Is it equal to the number we just calculated, after adjusting for the 2 things it's off by? Almost, but some islands might touch external gridpoints, which the rules don't care about.

Putting it all together, the number from the three steps above is almost the same as the number of gridpoints, except there are actually three ways it might be off:

it's 1 extra for every places islands touch
it's 1 extra for every unshaded 2×2
it's 1 extra for every touched external gridpoint

but how do I actually solve a puzzle?

From all that, we get a nice formula:

(width−1)×(height−1) = 2×(sum of (clues+1)) − (# of places islands touch) − (# of unshaded 2×2s) − (# of touched external gridpoints)

At first, this might not seem very useful for solving puzzles, because you don't know what any of the three "# of" values will end up being. But remember that this penalty theory applies to puzzles where the clue numbers are very small.

That means that 2×(sum of (clues+1)) is probably not that much bigger than the number of internal gridpoints. In fact, it might be exactly equal, in which case you can deduce that the three "# of" values must all be zero! In other words, the arrangement of islands has to be as "efficient" as possible at touching internal gridpoints – none of them can touch, they can't have 2×2s, and they can't touch the edge of the puzzle.

Even if the numbers are not exactly equal, they still give lots of useful information. Let's call each "inefficiency" a penalty. This simplifies the formula:

(width−1)×(height−1) = 2×(sum of (clues+1)) − (# penalties)

We can rearrange this to get

(# penalties) = 2×(sum of (clues+1)) − (width−1)×(height−1)

Now the right-hand side is entirely things you can calculate from the puzzle itself! If the resulting number of penalties is very small, you can get lots of useful information about what the solution must look like, especially if you can locate where the penalties are.

This is easiest to understand by example, so I'll demonstrate the technique on several puzzles (created by me).

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

This puzzle is easy to solve without using penalty theory if you're a Nurikabe expert, but it's still a good example of how the theory can be applied.

If you add 1 to each clue and add them up, you get 6 + 6 = 12. Doubling this gives you 24. How does this compare to the number of internal gridpoints? The puzzle is 7 by 5, so it has 6×4 = 24 internal gridpoints. That's exactly the same! That means the solution has no penalties.

The easiest thing to do first is to shade the entire border, since every external gridpoint touched is a penalty, and an island on the border would touch at least one external gridpoint.

Also, every place two islands touch is a penalty. That means neither of the two cells between the clues can be unshaded, since that would cause them to touch.

Now there's only one shape the leftmost 5 can be (noting that it has to include the cell below it, due to the no-shaded-2×2 rule), solving the puzzle!

Okay, that one was pretty easy, since there weren't any penalties. But what if there are?

Here, we first take 4 + 4 + 4 + 6 + 6 = 24 and double it to get 48. But the number of internal gridpoints, since the puzzle is 10 by 6, is 9×5 = 45. That means there are 3 penalties available to use anywhere in the solution.

However, the given arrangement of clues already forces 3 penalties in the solution. Specifically, the 3 in the top left is already touching two external gridpoints, which accounts for 2 penalties. And the other two 3s are touching diagonally, accounting for another penalty. So you can conclude that the solution can't contain any more penalties!

I've marked cells that we know are unshaded (by the rules of Nurikabe) with dots. Since there are no more penalties, we again know that any cell touching more than one existing island must be shaded.

This completely determines the top left 3 – but it also determines the leftmost 5. Since there are no more penalties, we can't make an unshaded 2×2 region, so the cell directly below the 5 must be shaded.