A solution of three-dimensional polyomino packing problems

The objective of our research is to develop a new method for solving three-dimensional (3D) polyomino packing problems. As a first step, we have devised a game-theoretic solution for two-dimensional (2D) cases, which were treated as rectilinear jigsaw puzzles, i.e., specialized 2D polyomino packing problems such that there is at least one placement solution. In this paper, as the next step, algorithms for the original 2D polyomino packing problem are extended so as to solve 3D polyomino packing problems. The resulting has no precedent in previous work and its biggest feature is efficiently to find a solution path as in the 2D cases. Numerical experiments prove that the algorithm works well with good efficiency.