Tetris Cube and n-dimensional Tetris
Recently I attempted to solve the Tetris Cube I found in a box under my bed. Just like normal Tetris but extended to 3D in a 4x4x4 cube. How hard can it be to to fit 12 pieces into this cube? Well by my rough estimates it’d be on the order of trillions of (very) naive brute force attempts to find just one solution. Tetris in 2D is already NP-complete; this is definitely not any easier.
In the spirit of completing the puzzle (and also to prove to my brother), I decided to solve the puzzle with progrmaming. It took a bit of time to realise that the problem reduces to an instance of the set-cover problem. Once it becomes a set-cover problem everything becomes rather trivial and just a matter of coding. To solve the set-cover problem, I converted it to an ILP problem and just solved with a LP package in python.
But what about n-dimensional Tetris? Well the program deals with that as well. Things get a bit hard to conceptualise after 3D but nothing really complicated is going on since pieces. Everything can be generalised to n-dimensions–it might just take some more thinking.