# Does this grid puzzle with a symmetry-breaking condition have a solution?

Since challenge questions are up in the air, what better time to pose a puzzle-building question that's intrigued me for some time.

## Preamble

Consider an infinite square grid made up of nodes and edges as shown in the following figure:

Each node connects to four edges, which are labeled top, left, right, and bottom as one would intuitively expect. Likewise, every square in the grid has four labeled edges. These labels are depicted in the two figures below.

Every edge in the grid has a parity label, which is either $A$ or $B$. Parity labels obey the following two symmetry rules:

1. At every node, the multiset of parity labels of the top and right edges must equal the multiset of parity labels on the bottom and left edges.

For example, if both the top and right edges have a parity label of $A$, then both the bottom and left edges must have a parity label of $A$. If the top and right edges have parity labels of $A$ and $B$ respectively, then then parity labels for the bottom and left edges must either be $A,B$ or $B,A$, respectively.

2. For every grid square, the multiset of parity labels of the top and left edges must equal the multiset of parity labels on the bottom and right edges.

The idea of the puzzle is to find a rule (or rules) for assigning a parity label to each edge in the grid that satisfies rule 1 at every node and rule 2 for every grid square.

There are several trivial ways to do this, such as assigning $A$'s to all edges, assigning $B$'s to all edges, etc., but one additional complication exists. The grid must start in either of the following two states:

Note that rule 2 is satisfied for the fully-assigned grid square in both grids, but rule 1 is not satisfied for the two fully-assigned nodes. This broken symmetry is by design for these particular nodes in these grids.

None of the existing parity labels may be changed, and rule 1 applies everywhere except at the two symmetry-breaking nodes.

The amended goal of the puzzle is therefore to find a rule (or rules) for assigning a parity label to each edge in the grid that satisfies rule 1 at every node except at the two symmetry-breaking nodes, and satisfies rule 2 for every grid square.

# Question

It's not intuitively obvious that the puzzle as stated above even has a solution. And indeed, all of my attempts to find a rule to populate the grid have lead to what I'll call "gridlock"—the inability to extend labels further in any direction without violating at least one of the two symmetry rules.

Unfortunately, "COTO gets consistently stuck" is far from a rigorous proof of non-existence of a solution, hence I shall commit the puzzle to the enterprising minds of puzzling.SE.

Does this puzzle have a solution? If so, what is it? If not, is there an elegant proof of this fact?

• Have you been able to accomplish this for finite grids? If so, any particular shapes that stood out? – jscs Dec 4 '14 at 2:16
• @JoshCaswell: None that were rectangular. My approach was generally to extend the grid as far as possible, and grids where edges are assigned iff they fall inside a rectangle are easily extended. The grid is inevitably quite irregular-looking when no more opportunities for extension exist. As for your second question: absolutely no patterns stood out for me, which is one of the reasons I strongly believe the puzzle isn't solvable. It's like the antisymmetry in the two nodes ripples outwards, ultimately ruining any attempt to restore symmetry. The madding thing is that I just can't prove it. – COTO Dec 4 '14 at 2:21
• Yeah, I was thinking that non-rectangular shapes would be it. I'm wondering if there's a connection that can be made with aperiodic tilings. I'll see what I can come up with. – jscs Dec 4 '14 at 2:25
• @JoshCaswell: If it helps, the motivation for this problem derives from trying to compute the resistance between two nodes in an infinite resistor network. There are several false proofs that give values, but it turns out that if you apply Kirchhoff's laws directly (rather than Z transforms, etc.), it's easy to show that the resistance of an infinite R network is ill-defined (it can take on any finite value). If the above problem is solvable, it implies the resistance of an infinite resistor network is ill-defined even if we impose the additional constraint of finite energy dissipation. – COTO Dec 4 '14 at 2:30
• I think that each line (horizontal or vertical) of edges must all have the same parity label, unless it contains an exceptional node. This means that without the exceptional nodes, the solutions are given by assigning a parity label to each line. Or am I missing something? – xnor Dec 4 '14 at 2:30

I wouldn't call this 'elegant', but here's an argument that there can be no solution starting with Grid 1.

In the first diagram, edges 1-6 must all have the same label: edges 1 and 2 because of the square they share, then edges 3 and 4 because of the vertex they share with 1 and 2, and finally 5 and 6 because of the square they share with 2 and 4. Looking at the orange vertex shows that the common label for edges 1-6 must be A.

In the second diagram, edge 1 must get the label A (it is adjacent to a vertex with 3 A's), then edge 2 must also get the label A (it is adjacent two a square with 3 A's). But now we're stuck, as there is no way to make the symmetry rule hold at the green vertex.

I drew something similar for Grid 2. It was a slightly more complicated, but I again found that there could be no solution.

• It's elegant enough. This is exactly what I was looking for. +1 – COTO Dec 4 '14 at 15:28
• @COTO Apologies for the bump, but this is incorrect, as the locations 1 and 2 would not transpose in that way according to rule 2 across a square. – theREALyumdub May 22 '18 at 20:36

This is an extremely late bump so feel free to ignore me, but I found this mathematically interesting, and if it has theoretical implications then what the heck. Also, I take it you mean with rule 1 and 2 that it actually goes both ways, and not merely one way. I'll do a general case first, and then explain how it solves your case.

## All Nodes and Boxes Follow The Rules

I claim the following:

Suppose every node and box in the grid follows rules 1 and 2 of symmetry, and two edges connecting to the same node at right angles have the same letter. Then the entire grid is that letter.

This requires two important observations. The first is that any two edges with the same letter like this will either be copied by a single box or a single node. Therefore, they are actually going to make two other right angled edges the same, their partner multi-set (I guess). From there, you can take the other two adjacent right-angled pairs, whether across a box or a node, and extend them using the other rule. Keep alternating rules and extending your rectangle, and you have the whole grid.

One way to think how this works is with a transformation. Draw lines in a square grid 45° off from yours, that pass through every box to make Xs. Then every edge is in one box, so you can draw a totally different type of grid, where the edges' letter is drawn in a box, and the boxes and nodes are just two different types of nodes on the grid. If you prefer, rotate the grid counterclockwise, and every node will have one of rule 1 (the upper right and upper left boxes adjacent to this node must have the same letter as the bottom boxes, a top-bottom rule) or 2 (the upper left and lower left boxes adjacent to this node must have the same letter as the right boxes, a left-right rule). Personally, I find this grid easier to understand, or at least to draw, since nodes and boxes are of the same type (rule nodes), and the edges just fill a box.

From this infinite grid result, we derive the only four solutions for the transformed infinite grid with symmetry at all nodes: all A, alternating A and B, or flip the letters on the previous two to get two more. To see why the alternating grids are the only other solutions, consider what would happen if two adjacent boxes (right-angled edges in the normal grid) were the same letter. If no adjacent boxes are the same letter on a square grid, you have a checkerboard pattern, and a specific, "fixed" box should be either white or black, giving the two solutions for a fixed position.