David Cohen, Peter Jeavons, Christopher Jefferson, Karen E. Petrie, Barbara M. Smith
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 reﬂect these two views, we deﬁne solution symmetry and constraint symmetry. We discuss how these concepts are related and show that some CSP instances have many more solution symmetries than constraint symmetries.
Subjects: 15.2 Constraint Satisfaction; 9.3 Mathematical Foundations