combinatorics - Holo-puzzle (2)

The first Holo-puzzle was not all too difficult. Let's increase the challenge:

A boundary of red and blue squares is given. Can you extend the square grid into the interior with red and blue squares (84 of them) such that each 5-square pattern, consisting of an interior cell plus its four nearest neighbours, always contains an even number of red squares?

In a holo-puzzle each boundary coloring maps to a single valid interior coloring: amongst the 2^84 total number of colorings, only one valid solution is hiding...

Answer

Here's the solution:

Now how would you solve this type of problem by hand in reasonable time? Checking the $2^{84}$ possible interior colorings one by one is rather out of the question. We need to be a bit cleverer.

From a mathematical viewpoint, this is a simple problem though. Each free tile is a $\mathbb{F}_2$-valued variable (red is 1, blue is 0), and each cross is a $\mathbb{F}_2$-linear equation. We have 84 equations in 84 variables, and the coefficient matrix of the equation system formed by this particular shape of problem happens to be regular, so we are guaranteed a unique solution, no matter the coloring of the outer tiles. So yeah, the first method is to simply solve a linear equation system in 84 variables. If you have an evening or ten to spare, you can technically do this by hand.

Let us this actually gives us a map $s$ from the space $P \cong \mathbb{F}_2^{28}$ of colorings of the outer squares (I'll call this the problem space) to the space $S \cong \mathbb{F}_2^{84}$ of colorings of the inner squares (the solution space). This map is $\mathbb{F}_2$-linear!

What does this help? Well, first of all any linear map from $P$ to $S$ maps $0_P$ to $0_S$, so if the outside squares are all blue, the inside squares will all be blue too (which is rather obvious anyway). Second, the solution of the sum (Adding in $\mathbb{F}_2$ looks like XORing) of two problems will be the sum of the solutions of these problems. Third, reflections of a solution solve reflections of any corresponding problem, so a solution always has at least the same symmetries as the problem it solves.

Now we can represent any problem in $P$ as a linear combination of these four basic problems and their reflections and rotations:

Here are the solutions to these four basic problems:

Memorizing these four solutions lets you solve any problem of the same shape without the need of a computer: To solve any problem $p$, we simply add rotations and reflections of these four basic grids together until the border looks like $p$. Then the interior will automatically be the solution of $p$.

Let's say you don't want to memorize those wacky-looking basic solutions though, and you also don't want to solve a LES in 84 variables. You're in luck! There is a third method! This method does not require you to memorize anything, it does not require you to XOR huge solutions lots of times. You just need to solve a LES in just 12 variables (actually 6 due to symmetry), which is way more manageable.

This is the shape of puzzle we are currently dealing with (let's call it Type A):

Here's a similar shape that looks so much easier though (let's call it Type B):

You can solve any puzzle of this shape just by filling in the blanks row by row, no thinking involved. So why not just solve this one instead? Here's what we're gonna look at:

Let $p$ be the Type A problem we need to solve (in this case it's OP's problem, note the top half visible in the image). If we pick the colors of the yellow-marked squares randomly, we can solve the Type B problem to get a coloring of the dark gray squares. Now all we need to do is pick the colors of the yellow squares such that the dark gray squares get exactly those colors that are in the bottom half of $p$!

We saw that any coloring of the yellow squares induces a coloring of the dark gray squares. This induces a map $r$ from the space $G \cong \mathbb{F}_2^{12}$ of yellow colorings (the "guess space") to the space $R \cong \mathbb{F}_2^{12}$ of colorings of the dark gray squares (the "result space"). This map is $\mathbb{F}_2$-affine!

So here's our strategy: First we choose the guess $g_0 = 0_G$ with twelve blue squares. This produces a result $r(g_0) =: r_0$ which may or (more likely) may not be the desired result $r_p$. Now we try some more guesses $g_1, \ldots, g_{12}$ which have exactly one red square each ($g_i$ has it in the $i$-th place). These produce results $r_1, \ldots, r_{12}$. We are now looking for the $x_1, \ldots, x_{12}$ in $\mathbb{F}_2$ which satisfy

$$ r_0 + x_1(r_1-r_0) + \ldots + x_{12}(r_{12}-r_0) = r_p. $$

This is a $\mathbb{F}_2$-LES in 12 variables, and it necessarily has a unique solution (as we've seen in the other approaches). Now we have

$$ r(g_0 + x_1(g_1-g_0) + \ldots + x_{12}(g_{12}-g_0)) = r_p, $$

the guess we're looking for is therefore

$$ g_p := g_0 + x_1(g_1-g_0) + \ldots + x_{12}(g_{12}-g_0). $$

By choice of the $g_i$, this is exactly the guess which has the color $x_i$ in the $g_i$-th square for all $i$.

Now we solve the Type B problem one last time, this time initialized with the guess $g_p$. The resulting valid coloring has the border $p$. We're done!