Fillomino puzzles

I work on the G12 constraint programming system. I've been putting together models for the forthcoming MiniZinc Constraint Solver Challenge; one of the most interesting was finding a model for fillomino puzzles. A fillomino puzzle looks like this (which I took from Vegard Hanssens' page to which I just linked):

1 . . . 1
. . . 1 .
2 4 . . .
1 . 2 1 .
3 . 1 . 2

The goal is to complete the grid by dividing it into "regions" (where a region is a maximally contiguous set of cells connected by their edges) where each cell in a region is labelled with the size of the region. Thus, a 1-region will contain a single 1 and have no bordering 1-regions; a 2-region will consist of two neighbouring cells containing 2s and have no bordering 2-regions; and so forth. Some regions may start with more than one cell filled in; some may have no clues filled in at the start. The solution to the problem above is

1 4 2 2 1
2 4 4 1 4
2 4 2 4 4
1 3 2 1 4
3 3 1 2 2

This is a surprisingly difficult puzzle to model due to the region contiguity constraints. My solution works as follows:

• each cell is a potential "root" of a region (and each region has a single root);
• neighbouring cells are either in the same region (and hence have the same number) or are in different regions (which must have different numbers);
• each cell has a time step at which we label it (region roots are labelled at step 1, all other cells are labelled later);
• any cell labelled at step t > 1 must be part of the region of a neighbouring cell labelled at step t;
• each region must be labelled with the size of the region.
  

The time step labelling and the unique roots constraints ensure that regions grow contiguously. The problem with this model is that it is hard to get decent propagation out of it (propagation is where the search tree is pruned as far as possible after each choice point). A human solver will recognise that there's no point trying to fill in a region of four cells with 5s; I have not yet found any good way of describing this information in the model.