Brute force side by side by "splitting" the box into two halves

packing.py

def side_by_side_brute(items):
    # can all the books fit?
    if max_height(items) > MAX_HEIGHT or max_width(items) > MAX_WIDTH:
        return False

    # is the volume ok?
    if total_volume(items) >= MAX_HEIGHT * MAX_WIDTH * MAX_DEPTH:
        return False

    # we are dealing with factorials here... 10! is 3.6 mio options
    if len(items) >= 10:
        print "Too many items:", len(items)
        return False

    # is normal stacking ok?
    if total_depth(items) <= MAX_DEPTH:
        return True

    # all possible orderings of items
    options = permutations(items)

    # depths for different stackings
    depths = []

    for option in options:
        # "Reset the box"
        bottom_depth = 0
        top_depth = 0

        used_height = 0

        # Try to place each item
        for item in option:

            if item.width <= item.height and item.height <= MAX_WIDTH:
                # it is better to turn it sideways, swap width and height
                item.width, item.height = item.height, item.width

            # at this point we know the book fits overall, and we've turned it if advantageous
            if item.height <= MAX_HEIGHT - used_height and item.width <= MAX_WIDTH:
                # the book fits next to the one below it
                # we should place it where we have the most room
                if bottom_depth > top_depth:
                    top_depth += item.depth
                else:
                    bottom_depth += item.depth

                # adjust the used height
                used_height = max(used_height, item.height)
            else:
                # the book does not fit next to the one below it, just throw it on top
                used_height = item.height
                top_depth = bottom_depth = max(top_depth + item.depth, bottom_depth + item.depth)

        # add the final depth to the list of depths
        depths.append(max(top_depth, bottom_depth))

    return min(depths) <= MAX_DEPTH