Penalty theory for dynasty genres


I'll clean this up for better presentation later. Old Twitter thread.

The penalty equation for dynasty genres, on any subset of the grid, is as follows:

(3 × number of black squares)
+ (number of primitive loops)
+ Σ (ceiling(perimeter segment length / 2) - number of black squares on this segment)

=

(grid size)
+ (number of odd-length perimeter segments / 2)
+ (number of white components)


The idea is to count pairs of (cell, a side of that cell), and then categorize them depending on how the side looks. Note that for each color of cells, there are exactly 4 × number of squares of that color. Also, there are only a few kinds of sides: white-white (between two white squares), white-black (between a white and a black), white-edge (a white square on the perimeter), black-edge (a black square on the perimeter). There is no black-black because this is a dynasty genre, and there is no edge-edge since it's meaningless.

For white cells, each white-white contributes two pairs, so:

(4 × number of black cells) = (number of black-white sides) + (number of black-edge sides)

For black cells, there is no black-black, so:

(4 × number of white cells) = (2 × number of white-white sides) + (number of white-black sides) + (number of white-edge sides)

We also have other equations. For example, the following is straightforward:

(number of black cells) + (number of white cells) = (grid size)

Meanwhile, the following is not at all obvious. This can be proven using graph theory; treating white squares as vertices and adjacent white squares as edges, by Euler's characteristic the number of edges is at least (number of vertices - number of components). Each extra edge is given by a "primitive loop"; essentially, a set of primitive loops has the property that no loop can be "obtained" from the other.

As an example, consider a 2×3 rectangle. There are 3 loops (two small squares and one the whole rectangle), but only 2 primitive ones: whichever 2 you take, the last one follows from the two.

(number of white-white sides) = (number of white cells) - (number of white components) + (number of primitive loops)

Finally, for each segment of perimeter,

(number of white-edge sides on this segment) - (number of black-edge sides on this segment)
=
(length of this segment) - (2 × number of black squares on this segment)
=
2 × (ceiling(length of segment) / 2 - number of black squares on this segment)
- (1 if the segment is odd length, 0 otherwise)

Note that we design the equation this way because the number of black edges is at most ceiling(length of segment) / 2, so the bracketed expression in the second-to-last line is nonnegative. Therefore, adding over all perimeter segments,

(number of white-edge sides) - (number of black-edge sides)
=
2 × Σ (ceiling(length of segment) / 2 - number of black squares on this segment)
- (number of odd-length perimeter segments)


We subtract the first two equations (counting white and black sides) to get

(4 × number of black cells)
- (4 × number of white cells)
=
(number of black-edge sides - number of white-edge sides)
- (2 × number of white-white sides)

Using the white-white side equation,

(4 × number of black cells)
- (4 × number of white cells)
=
(number of black-edge sides - number of white-edge sides)
- (2 × number of white cells)
+ (2 × number of white components)
- (2 × number of primitive loops)

Using the grid size equation and simplifying the common term,

(6 × number of black cells)
- (2 × grid size)
=
(number of black-edge sides - number of white-edge sides)
+ (2 × number of white components)
- (2 × number of primitive loops)

Using the perimeter equation,

(6 × number of black cells)
- (2 × grid size)
=
2 × Σ (ceiling(perimeter segment length) / 2 - number of black squares on this segment)
- (number of odd-length perimeter segments) / 2 + (2 × number of white components)
- (2 × number of primitive loops)

Dividing by 2 and rearranging gives the penalty equation above:

(3 × number of black squares)
+ (number of primitive loops)
+ Σ (ceiling(perimeter segment length / 2) - number of black squares on this segment)
=
(grid size)
+ (number of odd-length perimeter segments / 2)
+ (number of white components)

Note that two of three terms of the bottom side is constant (grid size and number of odd-length perimeter segments). When applied to the whole grid, the number of white components is 1, so the entire bottom side is constant.

If you're applying penalty theory, you usually have a very large number of black squares, and usually a known number of them too (or at least a lower bound). Note that the other two terms of the top side are also nonnegative, so they must be very small; this is what lets you count penalties.