Some information about task BLOCK A lower bound on the number of blocks in a decomposition is V/4 rounded up. 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 + W/4 rounded up, where W is the volume remaining to be decomposed. Thus, the recursion can be stopped when T + W/4 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. # V M 1 2 3 4 5 6 Kind of data -- -- -- -- -- -- - - - ------------ 1 4 1 . 4 . . . . Single 2x2 block 2 22 6 4 2 10 6 . . Manual, a "chair" 3 19 6 6 7 4 . . 2 Manual, a "tree" 4 18 5 6 3 6 3 . . The example (a "horse") 5 30 8 2 28 . . . . Manual, medium size 6 30 8 . 20 8 2 . . Manual, medium size 7 50 13 10 25 6 7 2 . Manual, largest size 8 33 12 11 17 1 4 . . Manual, large size 9 37 13 13 13 11 . . . Manual, large size 10 28 11 12 5 10 1 . . Manual, medium size where V = volume (input) M = minimum number of blocks in decomposition 1 = number of unit cubes with 1 neighbors (. means 0) 2,3,4,5,6 = same for indicated number of neighbors