---
abstract: 'Symmetry can be used to help solve many problems. For instance, Einstein’s famous 1905 paper (“On the Electrodynamics of Moving Bodies”) uses symmetry to help derive the laws of special relativity. In artificial intelligence, symmetry has played an important role in both problem representation and reasoning. I describe recent work on using symmetry to help solve constraint satisfaction problems. Symmetries occur within individual solutions of problems as well as between different solutions of the same problem. Symmetry can also be applied to the constraints in a problem to give new symmetric constraints. Reasoning about symmetry can speed up problem solving, and has led to the discovery of new results in both graph and number theory.'
author:
- Toby Walsh
title: 'Symmetry within and between solutions[^1]'
---

Introduction
============

Symmetry occurs in many combinatorial search problems. For example, in the magic squares problem (prob019 in CSPLib [@csplib]), we have the symmetries that rotate and reflect the square. Eliminating such symmetry from the search space is often critical when trying to solve large instances of a problem. Symmetry can occur both [*within*]{} a single solution as well as [*between*]{} different solutions of a problem. We can also [*apply*]{} symmetry to the constraints in a problem. We focus here on constraint satisfaction problems, though there has been interesting work on symmetry in other types of problems (e.g. planning, and model checking). We summarize recent work appearing in [@hwaaai10; @kwecai10; @knwcp10].

Symmetry between solutions
==========================

A symmetry $\sigma$ is a bijection on assignments. Given a set of assignments $A$ and a symmetry $\sigma$, we write $\sigma(A)$ for $\{ \sigma(a) \ | \ a \in A\}$. A special type of symmetry, called *solution symmetry* is a symmetry *between* the solutions of a problem. More formally, we say that a problem has the *solution symmetry* $\sigma$ iff $\sigma$ of any solution is itself a solution [@cjjpsconstraints06].

The *magic squares* problem is to label a $n$ by $n$ square so that the sum of every row, column and diagonal are equal (prob019 in CSPLib [@csplib]). A *normal* magic square contains the integers 1 to $n^2$. We model this with $n^2$ variables $X_{i,j}$ where $X_{i,j}=k$ iff the $i$th column and $j$th row is labelled with the integer $k$.

“Lo Shu”, the smallest non-trivial normal magic square has been known for over four thousand years and is an important object in ancient Chinese mathematics: $$\begin{aligned}
 \label{loshu}
&
\begin{tabular}{|c|c|c|} \hline
4 & 9 & 2 \\ \hline
3 & 5 & 7 \\ \hline
8 & 1 & 6 \\ \hline
\end{tabular}
&\end{aligned}$$

The magic squares problem has a number of solution symmetries. For example, consider the symmetry $\sigma_d$ that reflects a solution in the leading diagonal. This map “Lo Shu” onto a symmetric solution: $$\begin{aligned}
 \label{loshu2}
&
\begin{tabular}{|c|c|c|} \hline
6 & 7 & 2 \\ \hline
1 & 5 & 9 \\ \hline
8 & 3 & 4 \\ \hline
\end{tabular}
&\end{aligned}$$ Any other rotation or reflection of the square maps one solution onto another. The 8 symmetries of the square are thus all solution symmetries of this problem. In fact, there are only 8 different magic square of order 3, and all are in the same symmetry class.

One way to factor solution symmetry out of the search space is to post symmetry breaking constraints. See, for instance, [@puget:Sym; @clgrkr96; @ffhkmpwcp2002; @fhkmwcp2002; @fhkmwaij2005; @wcp06; @wecai2006; @llwycp07; @wcp07]. For example, we can eliminate $\sigma_d$ by posting a constraint which ensures that the top left corner is smaller than its symmetry, the bottom right corner. This selects (\[loshu\]) and eliminates (\[loshu2\]). Symmetry can be used to transform such symmetry breaking constraints [@hwaaai10]. For example, if we apply $\sigma_d$ to the constraint which ensures that the top left corner is smaller than the bottom right, we get a new symmetry breaking constraints which ensures that the bottom right is smaller than the top left. This selects (\[loshu2\]) and eliminates (\[loshu\]).

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 $\sigma$ (or equivalently $\sigma$ is a internal symmetry *within* this solution) iff $\sigma(A)=A$.

Consider again “Lo Shu”. This contains an internal symmetry. To see this, consider the solution symmetry $\sigma_{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 $\sigma_{180}$ that rotates the square $180^\circ$, we map back onto the original solution: $$\begin{aligned}
\begin{tabular}{|c|c|c|} \hline
4 & 9 & 2 \\ \hline
3 & 5 & 7 \\ \hline
8 & 1 & 6 \\ \hline
\end{tabular}
& 
\begin{array}{c}
\sigma_{inv} \\
\Rightarrow \\
\Leftarrow \\
\sigma_{180}
\end{array}
&
\begin{tabular}{|c|c|c|} \hline
6 & 1 & 8 \\ \hline
7 & 5 & 3 \\ \hline
2 & 9 & 4 \\ \hline
\end{tabular}\end{aligned}$$

Consider the composition of these two symmetries: $\sigma_{inv} \circ \sigma_{180}$. As this maps “Lo Shu” onto itself, the solution “Lo Shu” contains the internal symmetry $\sigma_{inv} \circ \sigma_{180}$.

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. However, 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. The exploitation of internal symmetries involves two steps: finding internal symmetries, and then restricting search to solutions containing just these internal symmetries. We have explored this idea in two applications where we have been able to extend the state of the art. In the first, we found new lower bound certificates for Van der Waerden numbers. Such numbers are an important concept in Ramsey theory. In the second application, we increased the size of graceful labellings known for a family of graphs. Graceful labelling has practical applications in areas like communication theory. Before our work, the largest double wheel graph that we found graceful labelled in the literature had size 10. Using our method, we constructed the first known labelling for a double wheel of size $24$.

[10]{}

Gent, I., Walsh, T.: : a benchmark library for constraints. Technical report APES-09-1999 (1999). A shorter version appears in CP-99.

Heule, M., Walsh, T.: Symmetry within solutions. In: Proc. of 24th National Conf. on AI, AAAI (2010)

Katsirelos, G., Walsh, T.: Symmetries of symmetry breaking constraints. In: Proc. of 19th ECAI, (2010)

Katsirelos, G.,Narodytska, N., Walsh, T.: Static constraints for breaking row and column symmetry. In: 16th Int. Conf. on Principles and Practices of Constraint Programming (CP-2010), (2010). Under review.

Cohen, D., Jeavons, P., Jefferson, C., Petrie, K., Smith, B.: Symmetry definitions for constraint satisfaction problems. Constraints **11** (2006) 115–137

Puget, J.F.: On the satisfiability of symmetrical constrained satisfaction problems. In Proc. of ISMIS’93. (1993) 350–361

Crawford, J., Ginsberg, M., Luks, G., Roy, A.: Symmetry breaking predicates for search problems. In: Proc. of the 5th Int. Conf. on Knowledge Representation and Reasoning, (KR ’96). (1996) 148–159

Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking row and column symmetry in matrix models. In: 8th Int. Conf on Principles and Practices of Constraint Programming (CP-2002), (2002)

Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Global constraints for lexicographic orderings. In: 8th Int. Conf. on Principles and Practices of Constraint Programming (CP-2002), (2002)

Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Propagation algorithms for lexicographic ordering constraints. Artificial Intelligence (2006).

Walsh, T.: General symmetry breaking constraints. In: 12 Int. Conf. on Principles and Practice of Constraint Programming (CP-2006), (2006)

Walsh, T.: Symmetry breaking using value precedence. In: 17th ECAI, (2006)

Law, Y.-C., Lee, J., Walsh, T, Yip, J.: Breaking symmetry of interchangeable variables and values. In: 13th Int. Conf. on Principles and Practices of Constraint Programming (CP-2007), (2007)

Walsh, T.: Breaking value symmetry. In: 13th Int. Conf. on Principles and Practices of Constraint Programming (CP-2007), (2007)

Walsh, T.: Breaking value symmetry. In: Proc. of 22nd National Conf. on AI, AAAI (2008)

[^1]: Supported by the Australian Government’s Department of Broadband, Communications and the Digital Economy and the ARC. Thanks to the co-authors of the work summarized here: Marijn Heule, George Katsirelos and Nina Narodytska.
