Interesting. I am going to have a look at this. In the past year, I have been working at an algorithm on how many paper cubes one can make out of a rectangle sheet of paper. There are 11 polyomino's that can be folded into a cube. It is impossible to exactly fill a rectangle (with integer size) completely with those polyomino's. So, you also will need some holes, squares that are not covered.
