
## Symmetry Within A Solution

Symmetries can also be found within individual solutions of a constraint satisfaction problem. We say that a solution A *contains* the internal symmetry σ (or equivalently σ is a internal symmetry *within* this solution) iff σ(A) = A.

Running example. *Consider again "Lo Shu". This contains an internal symmetry. To see this, consider the solution* symmetry σinv that inverts labels, mapping k *onto* n 2+1−k.

This solution symmetry maps "Lo Shu" onto a different (but symmetric) solution. However, if we now apply the solution symmetry σ180 *that rotates the square* 180◦*, we map back* onto the original solution:

$$\begin{array}{r l}{{\boxed{\begin{array}{l l|l}{{\begin{array}{l l|l}{{\begin{array}{l l}{4}&{9}&{2}\\ {3}&{5}&{7}\end{array}}}\end{array}}}}&{{\begin{array}{l l}{\sigma_{i n v}}\\ {\Rightarrow}\\ {\vboxed{\begin{array}{l l|l}{{\begin{array}{l l}{7}&{5}&{3}\\ {2}&{9}&{4}\end{array}}}\end{array}}}\end{array}}}}\end{array}}}\end{array}$$

Consider the composition of these two symmetries: σinv ◦
σ180*. As this symmetry maps "Lo Shu" onto itself, the solution "Lo Shu" contains the internal symmetry* σinv ◦ σ180.

One significant difference between a solution symmetry and an internal symmetry is that a solution symmetry is a property of every solution whilst an internal symmetry is a property of just the given solution.

Running example. Consider the following magic square:

![0_image_4.png](0_image_4.png)

$$\frac{\frac{16}{3}}{\frac{9}{6}}$$

σinv ◦σ180 is not *an internal symmetry contained within this* solution:

![0_image_6.png](0_image_6.png)

$\begin{array}{|c|c|}\hline&{III}\\ \hline\sigma_{inv}\circ\sigma_{180}&{\boxed{\frac{I I}{8}}}\\ \hline\\ \text{is an interval around}\\ \hline\end{array}$

![0_image_7.png](0_image_7.png)

![0_image_5.png](0_image_5.png)

However, σinv ◦σ180 *is an internal symmetry found within* the following solution:

$$\quad(4)$$

Thus we can conclude that σinv ◦σ180 is an internal symmetry contained within some but not all solutions of the normal magic squares problem. In fact, 48 out of the 880 distinct normal magic squares of order 4 contain this internal symmetry. On the other hand, σinv ◦σ180 *is a solution symmetry* of normal magic square problems of every size.

A solution containing an internal symmetry can often be described by a subset of assignments and one or more symmetries acting on this subset that generate a complete set of assignments. Given a set of symmetries Σ, we write Σ
∗
for the closure of Σ. That is, Σ
0 = Σ, Σ
i = {σ1 ◦ σ2 | σ1 ∈
Σ, σ2 ∈ Σ
i−1}, Σ
∗ =Si Σ
i. Given a solution A, we say the subset B of A and the symmetries Σ *generate* A
iff A = B ∪ Σ
∗
(B). In this case, we also describe A as containing the internal symmetries Σ.

Running example. *Consider again the solution (4) which* contains the internal symmetry σinv ◦ σ180. Half this magic square and σinv ◦ σ180 *generate the whole solution:*

![0_image_0.png](0_image_0.png)

$$\begin{array}{r l}{{\boxed{\begin{array}{l}{{\frac{13}{2}}}\\ {{\vboxed{\begin{array}{l}{\Leftrightarrow}\\ {\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{\vboxed{\begin{array}{l l}{

![0_image_1.png](0_image_1.png)

In fact, (4) can be generated from just the first quadrant and two symmetries: σinv ◦ σ180 and a symmetry τ which constructs a 180◦*rotation of the first quadrant in the second quadrant, decrementing those squares on the leading* diagonal and incrementing those on the trailing diagonal (the same symmetry constructs the third quadrant from the fourth). More precisely, τ makes the following mappings:

$$\begin{array}{l l}{{\overline{{\begin{array}{l|l|l}{{\overline{{b}}}}&{{\overline{{\ddots}}}}\end{array}}}}\\ {{\overline{{\begin{array}{l|l|l}{{\overline{{d}}}}&{{\overline{{\ddots}}}}\end{array}}}}\\ {{\overline{{\begin{array}{l|l|l}{{\overline{{\ddots}}}}&{{\overline{{\ddots}}}}\end{array}}}}\end{array}}}}&{{\Rightarrow}}\\ {{\overline{{\begin{array}{l|l|l}{{\overline{{d}}}}&{{\overline{{\ddots}}}}\end{array}}}}}&{{\overline{{\begin{array}{l|l}{{\overline{{\ddots}}}}\end{array}}}}}\end{array}$$

![0_image_2.png](0_image_2.png)

![0_image_3.png](0_image_3.png)

The example hints at how we can exploit internal symmetries within solutions. We will limit search to a subset of the decision variables that generates a complete set of assignments and construct the rest of the solution using the generating symmetries.

## Theoretical Properties

We identify some properties of internal symmetries that will be used to help find solutions.

## Set Of Internal Symmetries Within A Solution

Like solution symmetries, the internal symmetries within a solution form a group. A solution A *contains* a set of internal symmetries Σ (or equivalently Σ are internal symmetries within the solution) iff A contains σ for every σ ∈ Σ.

Proposition 1. The set of internal symmetries Σ *within a* solution A *form a group under composition.*
Proof: The identity symmetry is trivially an internal symmetry. Internal symmetries are also trivially closed under composition, Finally, consider any σ ∈ Σ. As σ(A) = A,
σ
−1(σ(A**)) =** σ
−1(A). That is A = σ
−1(A). Hence, the inverse of σ is an internal symmetry. ✷

## Symmetries Within And Between Solutions

In general, there is no relationship between the solution symmetries of a problem and the internal symmetries within a solution of that problem. There are solution symmetries of a problem which are not internal symmetries within any solution of that problem, and vice versa. The problem Z1 6= Z2 has the solution symmetry that swaps Z1 with Z2, but no solutions of Z1 6= Z2 contain this internal symmetry. On the other hand, the solution Z1 = Z2 = 0 of Z1 ≤ Z2 contains the internal symmetry that swaps Z1 and Z2, but this is not a solution symmetry of Z1 ≤ Z2 (since Z1 = 0, Z2 = 1 is a solution but its symmetry is not). When all solutions of a problem contain the same internal symmetry, we can be sure that this is a solution symmetry of the problem itself.