How to find the smallest square possible, out of Tetris pieces?

Question

I need to arrange an uncertain number of Tetris pieces, into the smallest possible square. The pieces I get are static, so I am not allowed to turn them and the square is allowed to have holes inside.

I am supposed to write a program to do this, but I think this is more of a mathematical problem.

In total, there are 19 different possible pieces. I thought of starting to create the minimal square, in case all the pieces fit in perfectly.

The equation would be: $m = \sqrt{n\cdot 4}$ rounded up, with m being the minimal size and n being the number of pieces you have. All the pieces are typical Tetris pieces made out of 4 combined blocks.

My idea now was to try to fit all pieces into this square, and enlarge it by 1 if it doesn't fit. The obvious problem now is the algorithm, to place the pieces in the best way possible. For doing that I only came up with the idea to define certain pieces, which combine to a rectangle together. I the program would find all the pieces needed for this rectangle, it would know how to continue with those pieces.

This would actually work with some examples, but there are also a lot of possible combinations, where the smallest square possible wouldn't even contain one rectangle inside.

If anyone has an idea how to solve this, I'd really appreciate the help.

Edit: I am looking for an algorithm that actually places the pieces in the square.

Answer 1

A simple algorithm, which I have just now implemented, is the following:

1. Define the 19 pieces

I defined each piece as beginning with the coordinates of the topmost and leftmost part of the piece and then giving the relative coordinates of the 3 remaining "parts" of that piece in an array. An "L" piece, lying down with its "head" to the right, would then have coordinates (2,0), (2,1), (1,1), (0,1).

2. Given a square size N and given K Tetris pieces, find all possible positions of each Tetris piece in the square

For each piece, find the coordinates at which its topmost and leftmost part could be located. For the above piece, in a square of size 4, the possible positions would be (2,0), (3,0), (2,1), (3,1), (2,2), (3,2). This assumes the square starts at (0,0).

3. Make a recursive function which attempts to place piece k at the first possible position where it doesn't overlap an existing piece.

At each moment, the function must know which positions in the square have already been taken.

4. If piece k can be placed, place it and attempt to place the next piece. If piece k cannot be placed, return and see if the previous piece can be moved to its next position.

5. If all K pieces have been placed, you are done. Otherwise (i.e. if the first piece has no other possible positions left to move to), no solution is possible.

The above algorithm is very simple but it does manage to solve N=7 cases within 5 seconds. When N=8, it can take over an hour. And the algorithm is done in Visual Basic for Excel, so other implementations could be much faster.

Below are some examples of its solutions:

1. N=7, K=12:

2. N=5, K=6:

If you are interested, I can post the code.

EDIT

Below is my attempt at pasting my code. I would appreciate any help in making it look better.

Dim Tetra(19, 6) As Integer
Dim N As Integer
Dim Pieces As Integer
Dim Piece(19) As Integer
Dim PosOfPiece(19, 49, 2) As Integer
Dim Positions(19) As Integer
Dim Grid1() As Boolean, Found As Boolean
Dim PiecePositioned(19) As Integer
Dim GridPosTrue(4, 2) As Integer


Sub Macro1()
'
' Macro1 Macro
'
' Keyboard Shortcut: Ctrl+a
'
Init
Init2
End Sub

Sub Init()
Tetra(1, 1) = 0: Tetra(1, 2) = 1: Tetra(1, 3) = 0: Tetra(1, 4) = 2: Tetra(1, 5) = 0: Tetra(1, 6) = 3
Tetra(2, 1) = 1: Tetra(2, 2) = 0: Tetra(2, 3) = 2: Tetra(2, 4) = 0: Tetra(2, 5) = 3: Tetra(2, 6) = 0
Tetra(3, 1) = 1: Tetra(3, 2) = 0: Tetra(3, 3) = 1: Tetra(3, 4) = 1: Tetra(3, 5) = 2: Tetra(3, 6) = 1
Tetra(4, 1) = 0: Tetra(4, 2) = 1: Tetra(4, 3) = -1: Tetra(4, 4) = 1: Tetra(4, 5) = -1: Tetra(4, 6) = 2
Tetra(5, 1) = 1: Tetra(5, 2) = 0: Tetra(5, 3) = 0: Tetra(5, 4) = 1: Tetra(5, 5) = -1: Tetra(5, 6) = 1
Tetra(6, 1) = 0: Tetra(6, 2) = 1: Tetra(6, 3) = 1: Tetra(6, 4) = 1: Tetra(6, 5) = 1: Tetra(6, 6) = 2
Tetra(7, 1) = 1: Tetra(7, 2) = 0: Tetra(7, 3) = 1: Tetra(7, 4) = 1: Tetra(7, 5) = 0: Tetra(7, 6) = 1
Tetra(8, 1) = 0: Tetra(8, 2) = 1: Tetra(8, 3) = 1: Tetra(8, 4) = 1: Tetra(8, 5) = 0: Tetra(8, 6) = 2
Tetra(9, 1) = 0: Tetra(9, 2) = 1: Tetra(9, 3) = 1: Tetra(9, 4) = 1: Tetra(9, 5) = -1: Tetra(9, 6) = 1
Tetra(10, 1) = 0: Tetra(10, 2) = 1: Tetra(10, 3) = 0: Tetra(10, 4) = 2: Tetra(10, 5) = -1: Tetra(10, 6) = 1
Tetra(11, 1) = 1: Tetra(11, 2) = 0: Tetra(11, 3) = 2: Tetra(11, 4) = 0: Tetra(11, 5) = 1: Tetra(11, 6) = 1
Tetra(12, 1) = 0: Tetra(12, 2) = 1: Tetra(12, 3) = 0: Tetra(12, 4) = 2: Tetra(12, 5) = 1: Tetra(12, 6) = 2
Tetra(13, 1) = 0: Tetra(13, 2) = 1: Tetra(13, 3) = -1: Tetra(13, 4) = 1: Tetra(13, 5) = -2: Tetra(13, 6) = 1
Tetra(14, 1) = 1: Tetra(14, 2) = 0: Tetra(14, 3) = 1: Tetra(14, 4) = 1: Tetra(14, 5) = 1: Tetra(14, 6) = 2
Tetra(15, 1) = 0: Tetra(15, 2) = 1: Tetra(15, 3) = 1: Tetra(15, 4) = 0: Tetra(15, 5) = 2: Tetra(15, 6) = 0
Tetra(16, 1) = 0: Tetra(16, 2) = 1: Tetra(16, 3) = 0: Tetra(16, 4) = 2: Tetra(16, 5) = -1: Tetra(16, 6) = 2
Tetra(17, 1) = 0: Tetra(17, 2) = 1: Tetra(17, 3) = 1: Tetra(17, 4) = 1: Tetra(17, 5) = 2: Tetra(17, 6) = 1
Tetra(18, 1) = 1: Tetra(18, 2) = 0: Tetra(18, 3) = 0: Tetra(18, 4) = 1: Tetra(18, 5) = 0: Tetra(18, 6) = 2
Tetra(19, 1) = 1: Tetra(19, 2) = 0: Tetra(19, 3) = 2: Tetra(19, 4) = 0: Tetra(19, 5) = 2: Tetra(19, 6) = 1
End Sub

Sub Init2()
Dim i As Integer
  N = Cells(6, 2).Value
  Pieces = Cells(7, 2).Value
  For i = 1 To Pieces
    Piece(i) = Cells(7 + i, 2)
  Next i
  AllocatePositions
  ReDim Grid1(N, N)
  Found = False
  PlacePiece 1, Grid1, Found
  If Not Found Then
    MsgBox "No solution found"
  End If
End Sub

Sub AllocatePositions()
Dim p As Integer, W As Integer, H As Integer, StartX As Integer, NumX As Integer, NumY As Integer
Dim pos As Integer, X As Integer, Y As Integer

  For p = 1 To Pieces
    Select Case Piece(p)
    Case 1
      W = 1: H = 4: StartX = 0
    Case 2
      W = 4: H = 1: StartX = 0
    Case 3
      W = 3: H = 2: StartX = 0
    Case 4
      W = 2: H = 3: StartX = 1
    Case 5
      W = 3: H = 2: StartX = 1
    Case 6
      W = 2: H = 3: StartX = 0
    Case 7
      W = 2: H = 2: StartX = 0
    Case 8
      W = 2: H = 3: StartX = 0
    Case 9
      W = 3: H = 2: StartX = 1
    Case 10
      W = 2: H = 3: StartX = 1
    Case 11
      W = 3: H = 2: StartX = 0
    Case 12
      W = 2: H = 3: StartX = 0
    Case 13
      W = 3: H = 2: StartX = 2
    Case 14
      W = 2: H = 3: StartX = 0
    Case 15
      W = 3: H = 2: StartX = 0
    Case 16
      W = 2: H = 3: StartX = 1
    Case 17
      W = 3: H = 2: StartX = 0
    Case 18
      W = 2: H = 3: StartX = 0
    Case 19
      W = 3: H = 2: StartX = 0
    End Select
    NumX = N - W + 1: NumY = N - H + 1
    pos = 1
    For Y = 0 To NumY - 1
      For X = 0 To NumX - 1
        PosOfPiece(p, pos, 1) = StartX + X
        PosOfPiece(p, pos, 2) = Y
        pos = pos + 1
      Next X
    Next Y
    Positions(p) = pos - 1
  Next p
End Sub

Sub PlacePiece(ByVal pp As Integer, Grid() As Boolean, SolutionFound As Boolean)
Dim Grid2() As Boolean
Dim Fail As Boolean
Dim pos As Integer, StartX As Integer, StartY As Integer, BoxNo As Integer, i As Integer

  pos = 1
  ' Can piece pp be placed in position Pos?
  Do While Not SolutionFound And pos <= Positions(pp)
    StartX = PosOfPiece(pp, pos, 1): StartY = PosOfPiece(pp, pos, 2)
    If Grid(StartX, StartY) Then
      GoTo End1
    Else
      GridPosTrue(1, 1) = StartX: GridPosTrue(1, 2) = StartY
      BoxNo = 0
      Fail = False
      Do While Not Fail And BoxNo <= 2
        GridPosTrue(BoxNo + 2, 1) = StartX + Tetra(Piece(pp), 2 * BoxNo + 1): GridPosTrue(BoxNo + 2, 2) = StartY + Tetra(Piece(pp), 2 * BoxNo + 2)
        If Not Grid(StartX + Tetra(Piece(pp), 2 * BoxNo + 1), StartY + Tetra(Piece(pp), 2 * BoxNo + 2)) Then
          BoxNo = BoxNo + 1
        Else
          Fail = True
        End If
      Loop
      If Fail Then
        GoTo End1
      Else
        PiecePositioned(pp) = pos
        Grid2 = Grid
        'Update Grid2
        For i = 1 To 4
          Grid2(GridPosTrue(i, 1), GridPosTrue(i, 2)) = True
        Next i
        If pp < Pieces Then
          PlacePiece pp + 1, Grid2(), SolutionFound
        Else
          SolutionFound = True
          'MsgBox "Success!"
          For i = 1 To Pieces
            'MsgBox "Piece " & Piece(i) & " at (" & PosOfPiece(i, PiecePositioned(i), 1) & ", " & PosOfPiece(i, PiecePositioned(i), 2) & ")"
            DrawPiece i, PiecePositioned(i), 2 + i
          Next i
        End If
      End If
    End If
End1:
    pos = pos + 1
  Loop
End Sub

Sub DrawPiece(p As Integer, pos As Integer, C_Index As Integer)
Dim i As Integer, StartX As Integer, StartY As Integer
  StartX = 30: StartY = 10
  Cells(StartY + PosOfPiece(p, pos, 2), StartX + PosOfPiece(p, pos, 1)).Interior.ColorIndex = C_Index
  For i = 0 To 2
    Cells(StartY + PosOfPiece(p, pos, 2) + Tetra(Piece(p), 2 * i + 2), StartX + PosOfPiece(p, pos, 1) + Tetra(Piece(p), 2 * i + 1)).Interior.ColorIndex = C_Index
  Next i
End Sub

Answer 2

This is not an answer, just an illustration that the largest square necessary is $9$ x $9$ as it can enclose all $19$ Tetris pieces. Done manually, I'm afraid.