Constraint Symmetry and Solution Symmetry∗

Symmetry in constraint satisfaction problems (CSPs) has been considered in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or as an operation preserving the constraints. To reflect these two views, we define solution symmetry and constraint symme-try. We discuss how these concepts are related and show that some CSP instances have many more solution symme-tries than constraint symmetries