Solve a Tetris Puzzle (pack predefined shapes into optimal form)

Question

The challenge is about finding an optimal solution on how to place a number of given shapes. It is oriented on the principle of Tetris, where it is optimal to pack the given pieces as tight as possible.

An optimal solution means that all shapes could be placed in one rectangle block filling the width of the playground. If there is no optimal solution possible, the code should find a solution where holes are placed as high as possible (thus allowing to have a subpart of the solution being optimal). Empty spaces on top of the solution are also counted as holes (see example at the bottom).

Rules

• There are predefined Tetris shapes: I J L S Z O T
• There could be multiple shapes of the same type available
• There is a playground with a certain width X
• The minimum width is 4, there is no maximum width
• There is no limitation for the height of the playground
• It is possible to rotate the shapes in 4 directions (Up, Left, Right, Down)
• It is NOT possible to mirror the shapes (Turning L into J or S into Z)

Possible shapes:

T:      T
       TTT

I:     IIII

J:     JJJ
         J

L:       L
       LLL

S:      SS
       SS

Z:     ZZ
        ZZ

O:     OO
       OO

A bit of imagination is needed, but everyone who played Tetris should be familiar with the shapes.

Example

A call to a solution using Python could look like the following:

tetrissolver.py <Width> <Shape1> <Shape2> <ShapeN>

tetrissolver.py 4 S S T T L

The result would be some kind of output which shows the optimal solution (tightest possible packaging). Bonus points if the solution also returns if the found solution is optimal.

Possible output of the above input in a text format:

LLLT
LSTT
SSST
STSS
TTTS

The found solution is optimal

If there is no optimal solution available, the code should find a solution with the least amount of holes in it. Empty spaces on top of the package are counted as holes. The above example with an additional T element could look like the following in the solution (holes marked with X):

XTXX
TTTX
LLLT
LSTT
SSST
STSS
TTTS

The found solution is NOT optimal

Solution

The solution should find the most optimal package. Holes should be placed as high as possible. If two solutions generate the same quality of packages (optimal packages if possible, same amount of holes), the smallest solution wins.

Answer 1

Java - Theoretically Optimal Solution

I needed one of these anyway, so...

Code is viewable here.

The routine should theoretically produce an optimal solution for any input. It typically runs on the order of milliseconds or seconds for < 100 shapes, and the complexity appears to be roughly O(n log² n) for random inputs. Packing hundreds or even thousands of random shapes should complete in a reasonable amount of time.

The worst case performance grows as O(nⁿ w^w), where n is the number of shapes to pack and w is the packing width. Thus this program earns the dubious distinction of having the worst worst case performance of any (non-busy-beaver) algorithm I've ever programmed. :P

Sample I/O

java TetPack 10 J T Z I I J Z O O J T S S O I

IIIIJOOTTT
IIIIJOOSTI
OOSJJZTSSI
OOSSZZTTSI
OOJSZJTZZI
OOJJJJJJZZ

Displayed solution is optimal.

java TetPack 3 T

XTX
TTT

9 J S I O S T T I I I S

XIIIIIIII
TTTSSIIII
TTSSJJJOO
TTSSSSJOO
TSSSSIIII

java TetPack 15 L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L J J J J J J J J J J J J J J J J J J J J J J J J J J J J J J

JJJJLLLLJLJJJJJ
JJJJLLJJJLJJJJJ
LLLLLLJJJLLLJJJ
LLLLLLJJLLLLJJJ
LLLLJJJJLLJLLLL
LLLLJJJJJLJJJLL
LLJJJJJJJLLLLLL
LLJJJJJJJLLLLLL
LLJJJJJLJLLLLLL
JJJJJJLLJJJLJLL
JJJJJJLLLLLLJLL
JJJJJLLLJJLJJLL
LLLJJLLLJJLJJJJ
LLLLLLLLJJLLLJJ
JLLLLLJLJJLLJJJ
JJJLLLJJJLLLJJJ

Displayed solution is optimal.

java TetPack 4 Z T

XZXX
ZZTX
ZTTT

java TetPack 30 J I O J J L T T T I O Z Z S I I O Z T O L L J I I L S Z Z I J I O S L L L L J J J I I O Z L J I L S I S Z I L I J I O J J L T T T I O Z Z S I I O Z T O L L J I I L S Z Z I J I O S L L L L J J J I I O Z L J I L S I S Z I L I

XXIIIIIIIIIIIIIIIIIIIIIIIIIIII
LIIIILIIIILIIIILIIIIJLIIIIJLOO
LIIIILJJJLLIIIILLLJJJLIIIIJLOO
LLJLJLLIJLLLZLJLLLJJJLLZZJJLLI
JJJLJJJILLLZZLJJJLJZZLLIZZZOOI
JJJLLILILZZZJLLSSOOIZZLILZZOOI
JJJJJILILLZZJSSSZOOIOOLILZTLLI
IJJJJILLSSZJJSSZZOOIOOTILLTTLI
IJJJJILSSZZSSZSZTOOIITTTOOTSLI
IJJJJLLZZZSSZZTTTTOOIIJJOOLSSI
ISSZILLLZZOOZTTTTJOOIIJLLLLTSI
SSZZILLOOJOOTZZTTJJJIIJLZZTTOO
LSZLIZZOOJJJTTZZTIIIIIJLLZZTOO
LSSLIJZZOOOOTSSSSSSTZZJJJLIIII
LLSLLJJJOOOOSSSSSSTTTZZLLLIIII