Tetriling Reassembly

/portfolio

THE TETRILING REASSEMBLY

The goal for this project was to design a program that could find a tiling solution to a random target shape by using a given set of tetris pieces. The algorithm would be tested based on time performance and accuracy.

The final algorithm scored within the Top 10 in the class for accuracy. It is a greedy solution which works by calculating a neighbours matrix for the target shape and placing the tetrominoes where they would encapsulate the lowest sum of neighbours.

READ THE FULL REPORT

GITHUB REPOSITORY

TYPE

MEng Design Engineering

SKILLS

Programing

Python, Visual Studio Code

FIELDS

Programming

STATUS

Finished

2018

HOW IT WORKS

My final algorithm works by calculating a neighbours matrix from the target shape. It then creates a score matrix for all the possible placements for each shape, obtained by summing the total value of neighbours that the shape would contain when placed in each square of the neighbours matrix. Once the score matrix is generated for each shape, the algorithm will start placing the tetrominoes that encapsulate the lowest sum of neighbours.

Example of a target shape and its neighbours matrix.

Example of a perfect solution and a low accuracy solution. It is shown that pieces with a lower sum of neighbors fit more perfectly (look at the yellow L in this case).

RESULTS

The average running time for a 1000×1000 target shape with a 0.8 density was of 2.9 minutes, keeping a consistent accuracy of about 95% for the biggest target sizes and about 90% for very small instances of the problem. Considering that the algorithm was being tested based on accuracy and time performance, we can conclude that this was a successful project. To learn more about the methods used to make these calculations, previous attempts and optimisations made to reduce the running time, you can read the four page report or take a look at the code on GitHub.