Complete row and column symmetry breaking in constraint satisfaction problems using the lex leader method is generally prohibitively costly. Double lex, which is derived from lex leader, is commonly used in practice as an incomplete symmetry-breaking method for row and column symmetries. This technique uses a row-wise ordering to construct the lex leader. For this reason, it is generally counterproductive to choose a search ordering that is not also row-wise. It seems logical that the search order should be used to pick the symmetry breaking technique, rather than the other way around. This paper surveys other possible orderings and investigates one particular ordering, snake ordering. From this we derive a corresponding incomplete set of symmetry breaking constraints, snake lex. We present experimental data comparing double lex and the snake lex, showing that snake lex is substantially faster than double lex in many cases.

The lex leader method for breaking symmetry in CSPs typically produces a large set of lexicographic ordering constraints. Several rules have been proposed to reduce such sets whilst preserving logical equivalence. These reduction rules are not generally confuent: they may reach more than one xpoint, depending on the order of application. These fixpoints vary in size. Smaller sets of lex constraints are desirable so ensuring reduction to a global minimum is essential. We characterise the systems of constraints for which the reduction rules are confluent in terms of a simple feature of the input, and define an algorithm to determine whether a set of lex constraints reduce confuently.