Fillit: Solving for the Smallest Square of Tetrominoes

It’s nearing the end of my first month at 42USA, where I am working towards becoming a software developer. For our first algorithms project, we were tasked with the problem:

“Given a set of Tetrominoes, find a way to assemble them in the smallest possible square”

My project partner, Jacob, and I decided to use recursive backtracking to solve this challenge. We chose this approach because fillit requires repeating actions like placing a tetromino, removing a tetromino and increasing the solution square size over and over again until a solutions is found. Although our solution wasn’t the fastest, we were able to solve the challenge within the timeframe required while keeping our code readable and easy to debug. Since many of my peers have been asking about our solution, I decided to write this blog post to explain our approach. For ease of reading, I’ve split the parts of the project into understanding the problem, validating the input, choosing a data structure and finding a solution. Perhaps you’ll find this interesting or useful in your own work.

The Problem

A Tetrimino block is a shape made up of 4 consecutive characters. You’ve probably seen Tetrominoes in the popular game, Tetris. For the purpose of this puzzle, Tetrominoes are considered fixed, meaning that they cannot be rotated and there are a total of 19 possible pieces that can be provided as input, as pictured below:

The goal of the puzzle is to find the smallest possible square board that the tetrominoes can fit in. Below is an examples of input and the desired solutions:

Note that when there are multiple solutions possible within the same size square, the solution with the pieces placed in the order they are provided at their top-most left-most positions is correct.

Validating the Input

The first step was to validate the input. Tetrominoes needed to be passed into our program as a file in the following format.

After writing the basic validation such as checking if the newlines were in the right place, we moved on to the more difficult checks. Specifically, we needed to validate the individual tetromino pieces:

Although we had a complete list of all 19 valid tetrominoes, checking every piece against that list isn’t efficient so we had to come up with a way to validate blocks. After discussing several different ideas, we decided the easiest implementation was to count the total number of sides touching:

If we find a single character with zero adjacent blocks, we can discard the tetromino input immediately. However, a more complicated case is the invalid piece pictured in dark purple above. Each piece is touching another piece, and yet it is does not fit the definition of a tetromino. As long as there are 6 sides total touching between the characters, we can be sure that the input piece is, in fact, a valid tetromino.

Once we validated the tetrominoes, we were ready to start placing them on a board.

Choosing Data Structures

The elements we needed to solve this problem were a list of tetrominoes and a square board to try and place the tetrominoes on. We chose to represent each tetrimino as a structure that contained a height, width and character array and we stored the tetrominoes in a linked list to keep track of their input order. We knew we could use recursion while placing the pieces so a singly linked list was ok, as there was no need to traverse backwards in the list.

Since we chose to store the shape of the tetromino pieces as an array of strings within the tetromino structure, we decided to also represent the square solution board as an array of strings. We found this was especially useful while debugging as at any point we could easily print tetromino pieces and the current state of the solution on the board.

Solving the Puzzle

To come up with an algorithm to solve the board, we tried manually solving a few simple boards with small pieces. We broke the overall problem down into three smaller problems:

1. Check if a single piece fits on a board, and if so, place that piece on the first available spot on the board. Repeat until the board is full.

2. If the board is full and a solution has not been found, undo the last piece placed on the board and try a different position for it. Repeat until all possible positions for all tetromino pieces have been tried.

3. If all possible solutions on a board have been tried, increase the size of the board and start over with placing the first tetromino. Note that the smallest possible board size is 2x2 as defined by the square tetromino by itself.

Future Opportunities & Optimizations

While our solution could solve 1–8 tetromino shapes in 0.00 seconds, it got exponentially slower with each additional piece and became unwieldy long with 10+ pieces.

One possible optimization is to calculate the starting board size, based on the number of individual cells that would be filled by the tetromino pieces, using the formula:

board starting size = sqrt(# of tetrominoes * 4 characters per tetromino)

Another possible optimization is to use a simper data structure to represent the tetromino pieces and the tetromino board, to avoid looping through each tetromino to place the piece. Some of the other students at 42USA were able to get significant improvements in time by using a bitfield to represent the board and bitwise operators to place the individual pieces.

The End!

Phew, we did it! So there you have a fairly simple solution for placing fixed tetromino pieces in the smallest possible square. Feel free to leave a comment with potential improvements to our solution, or check out our working solution in C on github.