Framework and algorithm for solving a specific set of bin packing problems.
Specifically, the goal is to put pieces into a box. Pieces are polycubes. Typically, there is no extra room in the box after placing all of the pieces.
The particular puzzle I'm trying to solve is placing 25 pentacube pieces into a 5x5x5 box. Each piece is different: they enumerate many different ways to make a piece from 5 connected unit cubes.
The first attempt was done in Python. Blender can be used to visualize things. Specifically, both the algorithm in action as it places pieces and the solved puzzle. See bpi.py for directions on how to do this (bpi: Blender Puzzle Interface).
The following is a live preview of the puzzle as it is being solved:
The following is a render of all 25 pieces layed out:
The C algorithm was written because the Python one wasn't fast enough: would run and run without solving the 5x5x5 puzzle. At first, the C algorithm would also run forever without solving the puzzle but with some major algorithm improvements, it now solves the problem quickly. It would be interesting to update the Python version with these changes and see how it behaves. It has not been proven that C was actually necessary to achieve the required speed.
The C algorithm can print a representation of the pieces/space to the terminal:
