# Symmetry Within Solutions

Marijn Heule TU Delft The Netherlands marijn@heule.nl

## Abstract

We define the concept of an internal symmetry. This is a symmety within a solution of a constraint satisfaction problem. We compare this to solution symmetry, which is a mapping between different solutions of the same problem. We argue that we may be able to exploit both types of symmetry when finding solutions. We illustrate the potential of exploiting internal symmetries on two benchmark domains: Van der Waerden numbers and graceful graphs. By identifying internal symmetries we are able to extend the state of the art in both cases.

## Introduction

Symmetry is an important feature of many combinatorial search problems. To be able to solve such problems, we often need to take account of symmetry. For example, when finding magic squares (prob019 in CSPLib
(Gent and Walsh 1999)), we have the symmetries that rotate and reflect the square. Factoring such symmetry out of the search space is often critical when trying to solve large instances of a problem. Up till now, research on symmetry has mostly focused on symmetries *between* different solutions of the same problem. In this paper, we propose considering in addition the internal symmetries (that is, symmetries *within* each solution). Whilst it appears to be challenging to identify useful internal symmetries, such symmetries are easy to exploit. We simply add constraints that restrict search to those solutions with the required internal symmetry and limit branching to the subset of decisions that generate a complete solution. We will demonstrate the value of exploiting internal symmetries within solutions with experimental results on two benchmark domains: Van der Waerden numbers and graceful graphs.

## Symmetry Between Solutions

A symmetry σ is a bijection on assignments. Given a set of assignments A and a symmetry σ, we write σ(A) for
{σ(a) | a ∈ A}. Similarly, given a set of symmetries Σ, we write Σ(A) for {σ(a) | a ∈ **A, σ** ∈ Σ}. A special type of symmetry, called *solution symmetry* is a symmetry *between* the solutions of a problem. Such a symmetry maps Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Toby Walsh NICTA and UNSW
Sydney, Australia toby.walsh@nicta.com.au solutions onto solutions. A solution is simply a set of assignments that satisfy every constraint in the problem. More formally, we say that a problem has the *solution symmetry* σ iff σ of any solution is itself a solution (Cohen et al. 2006).

As such mappings are associativity, and the inverse of a solution symmetry and the identity mapping are solution symmetries, the set of solution symmetries Σ of a problem forms a group under composition. We say that two sets of assignments A and B are in the same *symmetry class* of Σ iff there exists σ ∈ Σ such that σ(A) = B.

Running example. 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 (Gent and Walsh 1999)).*
A normal *magic square contains the integers 1 to* n 2. We model this with n 2*variables* Xi,j *where* Xi,j = k iff the ith 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:

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

$$(1)$$

The magic squares problem has a number of solution symmetries. For example, consider the symmetry σd that reflects a solution in the leading diagonal. This map "Lo Shu" onto a symmetric solution:

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

$$(2)^{\frac{1}{2}}$$

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 1993; Crawford et al. 1996; Flener et al. 2002; Frisch et al. 2002; Walsh 2006a; Walsh 2006b; Law et al. 2007; Walsh 2007). For example, we can eliminate σd by posting a constraint which ensures that the top left corner is smaller than its symmetry, the bottom right corner. This selects (1) and eliminates (2).