Tetriling Puzzle

2017. Individual Project.

Greedy algorithm that fits Tetris pieces into a tiled surface by prioritising tiles with the most free edges.

Algorithm Design & Iterative Implementation •  Coding  •  Problem Solving  •  Data Structures  •  Python

I developed an algorithm that could tile a randomly generated surface with Tetris pieces (tetrominoes) as part of the Computing 2 second year Design Engineering module.

 

My algorithm had an accuracy (missing plus excess tiles as a proportion of total tiles in target) of around 90% for most target surfaces, and a reasonably fast running time.

 

The target surface filled a set proportion of a grid of specified size and was itself made up of a random selection of tetrominoes. The grid size could be up to 1000 by 1000.

Technical Features

Through iterations, starting with a brute force method that placed any shape that fit, I developed a greedy algorithm as it could enable a similar strategy to the one I would naturally use to solve the problem by hand: to start placing pieces from the ‘outside’ of the target surface, or along tiles with few neighbouring ones first.

 

My final algorithm would find and continually update the number of free edges of each tile in the target and would select ones with the most free edges as the first places to fit tetrominoes.

 

When multiple tetrominoes could fit, the algorithm would sum the free edges for each tile covered and select the tetromino with the highest sum. This would ensure outer parts of the target were tiled first.

Though the strategy was effective, the nature of greedy algorithms to make the best immediate decision would sometimes adversely impact the solution at a later stage. To improve the algorithm’s performance, my final iteration also searched for ‘trominoes’ (shapes of 3 squares) and where possible tiled these areas with a tetromino resulting in one excess tile as opposed to three exposed ones.