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

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.

• I think the smallest square consists of a single square piece. – Christian Blatter Feb 25 '18 at 15:12
• In case of 1 piece that is true, and would fit my equation, but my program would have to deal with any number of pieces. Maybe 3, maybe 5, maybe 10 etc. – Robin Feb 25 '18 at 15:27
• Are you looking for the size of the smallest square or for an algorithm that places the pieces in that square? – krirkrirk Feb 25 '18 at 15:32
• Sorry if I was not clear enough on that, I am looking for an algorithm that places the pieces in that square. I just think finding out about the size of the smallest possible square would be the first step, but then they need to be placed there. – Robin Feb 25 '18 at 15:34

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).

1. 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).

1. 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.

1. 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.

2. 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: 1. 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
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

• Hey Jens, that actually sounds quite similar to what I did now. I'd really like to see your code, and here is mine if you are interested: github.com/Robinbux/Fillit-42-Challenge/blob/master/fillit.c . – Robin Mar 2 '18 at 19:11
• Just tried to paste my code into my post and it looked terrible. Any ideas on how this can be done in a nice way? – Jens Mar 2 '18 at 20:09
• I would only know Github, or else can you attach the file in your post? – Robin Mar 2 '18 at 20:18
• Just trying to understand your code :D I don't really know the language, but you also classify the single blocks here, and try to brute force through all possibilities, till they fit, correct? – Robin Mar 2 '18 at 20:46
• Yea kind of, but I mean like a neat mathematical way, that is fast – Robin Mar 2 '18 at 21:55

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. 