
| Occs                | Occsgcc                  | P yramidBC       | P yramidRC        |                  |                                           |          |              |       |      |    |       |     |
|---------------------|--------------------------|------------------|-------------------|------------------|-------------------------------------------|----------|--------------|-------|------|----|-------|-----|
| Class               | #solved                  | #bt              | time #solved      | #bt              | time #solved                              | #bt      | time #solved | #bt   | time |    |       |     |
| A                   | total solved 453 139,120 | 111.2            | 79                | 8,960            | 302.8 463 168,929 101.8 462 148,673 105.7 |          |              |       |      |    |       |     |
| solved by all       | 79                       | 8,960            | 7.1               | 79               | 8,960                                     | 302.8    | 79           | 9,104 | 5.7  | 79 | 8,739 | 6.3 |
| B                   | total solved 473 228,757 | 113.5 125 37,377 | 292.9 492 224,862 | 89.0 491 235,715 | 94.9                                      |          |              |       |      |    |       |     |
| solved by all 125   | 7,377                    | 17.6 125 37,377  | 292.9 125         | 32,810           | 10.9 125                                  | 32,110   | 12.2         |       |      |    |       |     |
| C                   | total solved 479 233,341 | 110.3 156 37,242 | 290.3 492 234,915 | 79.5 490 224,802 | 84.2                                      |          |              |       |      |    |       |     |
| solved by all 156   | 37242                    | 16.4 156 37,242  | 290.3 156         | 32,184           | 9.7 156                                   | 31,715   | 11.1         |       |      |    |       |     |
| D                   | total solved 482         | 8,306            | 6.0 456           | 207              | 14.9 416 168,021                          | 24.2 489 | 13,776       | 9.0   |      |    |       |     |
| solved by all 391   | 195                      | 0.2 391          | 195               | 13.1 391 145,534 | 14.9 391                                  | 690      | 0.4          |       |      |    |       |     |
| E                   | total solved 500         | 331              | 0.3 500           | 331              | 5.1 500                                   | 4,252    | 0.4 500      | 174   | 0.1  |    |       |     |
| solved by all 500   | 331                      | 0.3 500          | 331               | 5.1 500          | 4,252                                     | 0.4 500  | 174          | 0.1   |      |    |       |     |
| TOTALS              |                          |                  |                   |                  |                                           |          |              |       |      |    |       |     |
| Total solved/tried  | 2,387/2,500              | 1,316/2,500      | 2,363 /2,500      | 2,432/2,500      |                                           |          |              |       |      |    |       |     |
| Avg time for solved | 67.0                     | 87.5             | 59.364            | 58.0             |                                           |          |              |       |      |    |       |     |
| Avg bts for solved  | 120,303                  | 8,700            | 163,473           | 123,931          |                                           |          |              |       |      |    |       |     |

propagation [11]. As a second example, many global constraints can be decomposed using ROOTS and RANGE which can themselves often be propagated effectively using simple decompositions [12–14]. As a third example, the REGULAR and CFG constraints can be decomposed without hindering propagation [15–17]. As a fourth example, decompositions of the SEQUENCE constraint have been shown to be effective [18]. Most recently, we demonstrated that the ALL-DIFFERENT and GCC constraint can be decomposed into simple primitive constraints without hindering bound consistency propagation [6]. These decompositions also introduced variables to count variables using values in an interval. For example, the decomposition of ALL-DIFFERENT ensures that no interval has more variables taking values in the interval than the number of values in the interval. Using a circuit complexity lower bound, we also proved that there is no polynomial sized SAT decomposition of the ALL-DIFFERENT constraint (and therefore of its generalizations like NVALUE) on which unit propagation achieves domain consistency [19].

## 9 Conclusions

We have shown that the NVALUE constraint can be decomposed into simple arithmetic constraints. This decomposition permits a global view to be maintained that achieves bound consistency. Our experiments demonstrate that this decomposition is a relatively efficient and effective means to propagate the global NVALUE constraint. Decomposi-