Proposition 2. *If all solutions of a problem contain an internal symmetry then this is a solution symmetry.*
Proof: Consider any solution A. As all solutions of the problem contain the internal symmetry σ, σ(A) = A. Hence σ maps A onto itself, and σ(A) is also a solution. ✷
By modus tollens, it follows that if σ is not a solution symmetry of a problem then there exists at least one solution which does not contain the internal symmetry σ.

## Symmetries Of Symmetric Solutions

We next consider internal symmetries contained within symmetric solutions. In general, the symmetry of a solution contains the conjugate of any internal symmetry contained within the original solution.

Proposition 3. If the solution A contains the internal symmetry σ and τ is any (other) symmetry then τ(A) contains the internal symmetry τ ◦ σ ◦ τ
−1.

Proof: Consider the action of τ ◦ σ ◦ τ
−1 on τ(A). Now τ(σ(τ
−1(τ(A**)))) =** τ(σ(A)). But as A contains the internal symmetry σ, σ(A) = A. Hence τ(σ(A**)) =** τ(A). Thus τ ◦ σ ◦ τ
−1 maps τ(A) onto itself. ✷
In the special case that symmetries commute, the symmetry of a solution contains the same internal symmetries as the original problem. Two symmetries σ and τ *commute* iff σ ◦ τ = τ ◦ σ.

Proposition 4. If the solution A contains the internal symmetry σ and τ commutes with σ then τ(A) *also contains the* internal symmetry σ.

Proof: By Proposition 3, τ(A) contains the internal symmetry τ
◦σ ◦ τ
−1. But τ ◦ σ ◦ τ
−1 = τ ◦ τ
−1 ◦ σ = σ.

✷

## Symmetry Breaking

Finally, we consider the compatibility of eliminating symmetric solutions and focusing search on those solutions that contain particular internal symmetries. In general, the two techniques are incompatible. Symmetric breaking may eliminate all those solutions which contain a given internal symmetry.

Running example. Consider again the solution (3). This contains the internal symmetry σv ◦ σinv *that inverts all values and reflects the square in the vertical axis:*

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

1 4 13 16

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

14 15 2 3 8 5 12 9 11 10 7 6
Note that this internal symmetry can only occur within magic squares of even order or of order 1.

Suppose symmetry breaking eliminates all solutions in the same symmetry class as (3) except for a symmetric solution which is a 90◦clockwise rotation of (3). This solution does not contain the internal symmetry σv ◦ σinv. In fact, this rotation of (3) contains the internal symmetry that inverts all values and reflects the square in the horizontal *axis.*

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

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

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

σinv
⇒ ⇐
σv
We can identify a special case where symmetry breaking does not change any internal symmetry within solutions. Suppose symmetry breaking only eliminates symmetries which commute with the internal symmetry contained within a particular solution. In this case, whilst symmetry breaking may eliminate the given solution, it must leave a symmetric solution containing the given internal symmetry.

Given a set of constraints C with solution symmetries Σ, we say that a set of symmetry breaking constraints S is *sound* iff for every solution of C there exists at least one solution of C ∪ S in the same symmetry class.

Proposition 5. Given a set of constraints C with solution symmetries Σ, a sound set of symmetry breaking constraints S, and a solution A containing the internal symmetry σ*, if* σ commutes with every symmetry in Σ then there exists a solution of C ∪ S in the same symmetry class as A also containing the internal symmetry σ.

Proof: As S is sound, there exists a solution B of C ∪S and τ ∈ Σ with B = τ(A). Now τ commutes with σ. Therefore by Proposition 4, B contains the internal symmetry σ. ✷
Running example. *Consider the internal symmetry* σinv ◦
σ180 *contained within some (but not all) normal magic* squares. This particular symmetry commutes with every rotation, reflection and inversion solution symmetry of the problem. Hence, if there is a solution with the internal symmetry σinv ◦ σ180, this remains true after breaking the rotational, reflection and inversion symmetries. However, as in the last example, there are internal symmetries contained within some solutions (like reflection in the vertical axis) which do not commute with all symmetries of the square.

## Exploiting Symmetries Within Solutions

The exploitation of internal symmetries involves two steps:
finding internal symmetries, and then restricting search to solutions containing just these internal symmetries. The first step appears challenging. The definition of an internal symmetry is rather weak. There will be many uninteresting internal symmetries contained within a solution. We want to find internal symmetries that are likely to be contained within as yet unsolved instances of our problem. Although we do not yet have an efficient set of automated methods to do this, we can focus on simple symmetries (like the solution symmetries of the problem) and on small and already solved instances of a problem. This may suggest internal symmetries which might be contained in solutions of larger
(perhaps open) problems.

Once we have identified an internal symmetry which we conjecture may be contained in solutions of other (perhaps larger) instances of the problem, it is a simple matter to restrict search of a constraint solver to solutions of this form.

In general, if we want to find solutions containing the internal symmetry σ, we post symmetry constraints of the form:
Zi = j ⇒ σ(Zi = j)