
| # n            | S    | B1                      | B3         | B    | R     | ezcsp clingcon gecode   |       |     |
|----------------|------|-------------------------|------------|------|-------|-------------------------|-------|-----|
| 1 7            | 1.7  | 1.7                     | 1.7        | 1.7  | 1.6   | 65.0                    | 189.8 | 0.6 |
| 1 8 19.0       | 5.9  | 4.7                     | 19.8       | 4.7  | -     | -                       | -     |     |
| 1 9            | -    | 139.4 152.0 234.6 466.9 | -          | -    | -     |                         |       |     |
| 2 7            | 1.7  | 1.7                     | 1.7        | 1.8  | 1.8   | 46.1                    | 1.5   | 1.2 |
| 2 8 46.6       | 9.6  | 10.6                    | 37.7       | 14.8 | -     | -                       | -     |     |
| 2 9            | -    | 246.0 55.7              | 88.3 213.4 | -    | -     | -                       |       |     |
| 3 7            | 0.2  | 0.2                     | 0.2        | 0.3  | 0.3   | 3.2                     | 1.0   | 0.0 |
| 3 8            | 0.4  | 0.4                     | 0.5        | 0.5  | 0.5   | 4.3                     | 9.0   | 0.2 |
| 3 9 10.2       | 7.4  | 9.5                     | 16.5       | 12.8 | -     | -                       | 18.2  |     |
| 4 7            | 0.2  | 0.2                     | 0.2        | 0.3  | 0.3   | 2.8                     | 0.7   | 0.1 |
| 4 8            | 0.5  | 0.6                     | 0.7        | 0.9  | 0.7   | 27.9                    | 36.8  | 0.3 |
| 4 9            | 1.3  | 1.0                     | 2.1        | 3.0  | 0.9   | 442.1                   | 288.8 | 3.7 |
| 5 10 1.6       | 1.5  | 1.6                     | 1.9        | 1.6  | -     | -                       | 0.2   |     |
| 5 11 2.1       | 2.2  | 2.4                     | 3.4        | 2.4  | -     | -                       | 0.8   |     |
| 5 12 27.0      | 6.2  | 9.1                     | 12.4       | 10.4 | -     | -                       | 16.4  |     |
| 6 10 1.2       | 1.4  | 1.5                     | 1.8        | 1.5  | 10.5  | -                       | 0.1   |     |
| 6 11 2.7       | 2.8  | 4.0                     | 4.2        | 4.8  | 125.5 | -                       | 1.2   |     |
| 6 12 32.0 12.9 | 25.6 | 36.4                    | 50.6       | -    | -     | 24.6                    |       |     |
| 7 8            | 0.4  | 0.4                     | 0.4        | 0.6  | 0.5   | 1.1                     | -     | 0.1 |
| 7 9            | 0.7  | 1.0                     | 1.2        | 1.7  | 1.4   | 9.1                     | -     | 0.9 |
| 7 10 6.7       | 3.2  | 5.2                     | 8.0        | 4.6  | -     | -                       | 22.0  |     |

Table 3: Results in seconds for quasigroup existence.

| n                                    | S    | B1   | B3          | B    | R     | ezcsp clingcon gecode   |     |     |
|--------------------------------------|------|------|-------------|------|-------|-------------------------|-----|-----|
| 4                                    | 1.3  | 2.0  | 1.5         | 3.2  | 2.5   | 0.6                     | 0.1 | 0.1 |
| 5                                    | 4.5  | 5.0  | 4.5         | 13.5 | 31.4  | 1.0                     | 2.0 | 0.1 |
| 6                                    | 7.2  | 11.0 | 17.6        | 47.7 | 110.2 | 1.2                     | -   | 7.2 |
| 7 23.8                               | 28.3 | 67.9 | 227.9 432.9 | 18.0 | -     | -                       |     |     |
| 8 48.4                               | 68.4 | -    | 207.8 356.8 | 4.3  | -     | -                       |     |     |
| 9 82.8 106.5 200.4 486.6 227.4 390.5 | -    | -    |             |      |       |                         |     |     |

to node labels is represented in the direct encoding which weakens the overall consistency. Table 4 shows our results for *double wheel graphs*, i.e., graphs composed of two copies of a cycle with n nodes, each connected to a central hub.

Our encodings compete with *ezcsp* and outperform the other systems, whilst the support encoding performs better than bound and range encodings. We observe some variability in the results for Bk and Rk, e.g., for n = 8 the options B1 and B solve the problem within the time limit but B3 does not, although B3 contains B1. We explain this variability by the lookback-based branching heuristic used by *clingo* being misled by the extra variables introduced in Bk and Rk. This is inherent to a growing size of the encoding.

## 5 Related Work

Most previous work integrates CP techniques into ASP
to avoid huge ground instantiations given through logic programs with first-order variables over large domains.

An ASP system was extended in [Baselice *et al.*, 2005; Mellarkod and Gelfond, 2008; Mellarkod *et al.*, 2008] such that it does not require full grounding, since variables and limitations on their domains can be handled in the CP solver.

A similar approach presented in [Dal Pal`u *et al.*, 2009] employs the CP solver to compute also the answer sets. Although these hybrid strategies potentially eliminate the bottleneck that is inherent to the translation-based approach, they view ASP and CP solvers as blackboxes which do not match the performance of state-of-the-art SMT solvers. In particular, they do not make use of conflict-driven learning and backjumping techniques. This gap was closed by the approach taken in [Gebser *et al.*, 2009b] following the one by SMT
solvers in letting the ASP solver deal with the propositional structure of the logic program, while a CP solver addresses the constraints. Apart from extending the unit-propagation of an ASP solver through constraint propagation, it deals with the elaboration of reasons for atoms derived by constraint propagation within conflict resolution. The elaboration of conflict information from constraint propagators, however, is limited since constraint propagators lack support for this feature (they would have to keep an implication graph to record reasons for each propagation step). Hence, the conflict resolution process cannot exploit constraint interdependencies.

A different hybrid approach to solving CASP is presented in [Balduccini, 2009], where an answer set of a logic program with constraint atoms encodes a desired CSP which, in turn, is handled by a CP system. A more general framework using multiple declarative paradigms to specify CSP is proposed in [J¨arvisalo *et al.*, 2009]. Either approach, however, restricts communication between different solver types in order to compute solutions to the whole CASP model, e.g., they also do not incorporate conflict-driven learning and back-jumping techniques.

In a translation-based approach, all parts of the model are mapped into a single constraint language for which highly efficient off-the-shelf solvers are available. Hence, related work has mostly focussed on the translation of constraints to SAT (cf. [Walsh, 2000; Gent, 2002]). Translation into ASP, however, can be more general than translation into SAT:
Every nogood can be syntactically represented by a clause, but other ASP constructs are also possible, such as cardinality and weight constraints [Simons *et al.*, 2002]. ASP was put forward as a novel paradigm for modelling and solving CSP in [Niemel¨a, 1999], where straightforward encodings to represent generic constraints via either allowed or forbidden combination of values has been presented. Preliminary work on translating CASP into ASP was conducted in [Gebser *et al.*, 2009a], but they did not consider what level of consistency was achieved by their translation.

Decompositions of ALL-DIFFERENT into simple arithmetic constraints such that bound and range consistency can be achieved were proposed in [Bessi`ere *et al.*, 2009a]. There is no polynomial-sized decomposition that achieves domain consistency [Bessi`ere *et al.*, 2009b].

## 6 Conclusions

We have shown that constraint answer set programming is a promising approach to representing and solving combinatorial problems that naturally merges CP and ASP, while preserving the advantages of both paradigms. We have presented a translation-based approach to constraint answer set solv-