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