11
$\begingroup$

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?

enter image description here

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...

$\endgroup$
  • $\begingroup$ What exactly is a 5-square pattern? Is it a square with all its horizontally/vertically adjacent neighbours? What about the ones at the boundaries? $\endgroup$ – Shuri2060 Mar 27 '16 at 17:14
  • $\begingroup$ A five-square pattern consists of an interior cell together with its four (left, right, up, down) neighbors. Each such five-square pattern should contain 0, 2, or 4 red squares. $\endgroup$ – Johannes Mar 27 '16 at 17:20
  • $\begingroup$ What about the boundary ones? $\endgroup$ – Shuri2060 Mar 27 '16 at 17:20
  • $\begingroup$ The boundary squares have given colors... $\endgroup$ – Johannes Mar 27 '16 at 17:21
  • $\begingroup$ But they don't have to satisfy the rule? $\endgroup$ – Shuri2060 Mar 27 '16 at 17:26
4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

First I'm going to rotate the grid by $\pi/4$, to make things a little easier:

enter image description here

I've shown how the 4-neighbors (green) of a cell (orange) are transformed as well. Note that only half of the cells in the resulting grid are occupied (only ones where the sum of the indices are odd).

Note that each group must have an even number of red cells; since every group has an odd number of total cells, it must therefore have an odd number of blue cells. The xor function:

$$ x_1 \oplus x_2 \oplus x_3 \oplus \cdots \oplus x_n $$

is true iff an odd number of the $x_i$ are True; therefore I'll represent blue cells as True and red cells as False.

This turns the condition on the group centered at $i,j$ into:

$$ f_{i,j} \oplus f_{i-1,j} \oplus f_{i,j-1} \oplus f_{i+1,j} \oplus f_{i,j+1} \iff \top $$

(Where $f_{i,j}$ is the truth value of the cell in position $i,j$.) Now the question is a straightforward boolean satisfiability problem:

With[{n = 13},
 (* define the conditions on the grid *)
 grid = Apply[And, Array[
    Or[
      (* either the cell is empty... *)
      EvenQ @ Plus[##],
      (* or the xor of it and its neighbors is True *)
      Xor[f[##], Sequence @@ f @@@ Tuples[Outer[Plus, {##}, {-1, +1}]]]
      ] &,
    {n, n}
    ], {0, 1}];
 (* define the boundary conditions *)
 boundary = {
      f[0, 1] | f[1, 0] | f[n, n + 1] | f[n + 1, n] -> True, 
      f[___, 0 | (n + 1), ___] -> False
    };
 (* apply the boundary conditions *)
 grid = grid /. boundary;
 (* find the free variables *)
 vars = Union@Cases[grid, _f, ∞];
 (* find all solutions to the problem >=) *)
 soln = SatisfiabilityInstances[grid, vars, All];
 (* display the solutions *)
 Column @ Table[
   MatrixPlot[
     (* set up the grid, filling empty cells with None *)
     Array[If[OddQ @ Plus[##], f[##], None] &, {n + 2, n + 2}, 0]
     (* apply the boundary conditions and solution *)
     /. boundary /. Thread[vars -> s]
     (* color the grid *)
     /. {True -> Darker@Cyan, False -> Pink}
   ],
   {s, soln}
 ]
]

enter image description here

This code returns one solution, so the answer is yes.

$\endgroup$
  • $\begingroup$ Well done. But the question remains: would you be able to solve the problem without the help of a computer? $\endgroup$ – Johannes Mar 29 '16 at 17:49
  • $\begingroup$ @Johannes No, since I wouldn't have been able to see the puzzle in the first place =) $\endgroup$ – 2012rcampion Mar 29 '16 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.