Solving the Partridge Packing Problem Using MiniZinc

The page details the process of modeling and solving the Partridge Packing Problem, a square packing puzzle, using the MiniZinc constraint programming language. The problem involves packing $i$ squares of size $i \times i$ for $i=1$ to $n$ into a larger square of side length equal to the $n$-th triangular number.

The initial base model, defining variables for square positions and applying the essential diffn (no-overlap) constraint, is computationally very slow, requiring hours for the $n=8$ case. Significant performance improvements are achieved through incremental model strengthening. Key enhancements include adding "exact fill" implied constraints, which ensure that the sum of overlapping part sizes exactly matches the dimension length for every row and column, drastically reducing the solve time for $n=8$ to minutes. Further substantial speedup is gained by incorporating symmetry-breaking constraints to enforce a lexicographical order among the placements of indistinguishable squares of the same size.

Performance comparisons across various solvers show that OR-Tools CP-SAT is the most effective among those tested for this generic model, achieving solutions up to size $n=11$ relatively quickly. Specialized solvers like SICStus, using its built-in, problem-specific propagator (geost), outperforms the generic MiniZinc model, solving up to $n=12$.