1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the smallest square consists of a single square piece. $\endgroup$ – Christian Blatter Feb 25 '18 at 15:12
  • $\begingroup$ 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. $\endgroup$ – Robin Feb 25 '18 at 15:27
  • $\begingroup$ Are you looking for the size of the smallest square or for an algorithm that places the pieces in that square? $\endgroup$ – krirkrirk Feb 25 '18 at 15:32
  • $\begingroup$ 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. $\endgroup$ – Robin Feb 25 '18 at 15:34
0
$\begingroup$

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:

enter image description here

  1. N=5, K=6:

enter image description here

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
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 . $\endgroup$ – Robin Mar 2 '18 at 19:11
  • $\begingroup$ 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? $\endgroup$ – Jens Mar 2 '18 at 20:09
  • $\begingroup$ I would only know Github, or else can you attach the file in your post? $\endgroup$ – Robin Mar 2 '18 at 20:18
  • $\begingroup$ 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? $\endgroup$ – Robin Mar 2 '18 at 20:46
  • 1
    $\begingroup$ Yea kind of, but I mean like a neat mathematical way, that is fast $\endgroup$ – Robin Mar 2 '18 at 21:55
1
$\begingroup$

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.

enter image description here

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.