A lower bound on the number of blocks in a decomposition is ~\left\lceil \frac V 4 \right\rceil~. Finding a minimal decomposition by simple backtracking is slow because there are so many solutions with small blocks. The technique of branch-and-bound can be used to reduce the running time drastically. When a partial decomposition with ~T~ blocks has been obtained, a lower bound for the number of blocks in the complete decomposition is ~T + \left\lceil \frac W 4 \right\rceil~, where ~W~ is the volume remaining to be decomposed. Thus, the recursion can be stopped when ~T + \left\lceil \frac W 4 \right\rceil~ exceeds the minimum obtained so far.

Each block type consists of at most ~24~ rotated blocks (the actual number depends on the symmetries of the block). These rotations can be precomputed (based on the rotation group of the cube, which can be generated by two permutations). The translations can be done on-the-fly during backtracking.

It can be expected that programs for this task are somewhat longer than for the other tasks.