Tetriling Reassembly Algorithm
(Award for highest performing algorithm in department)
This was an algorithm design and optimisation assignment in which we had to create a python program to find the optimum solution to the Tetriling reassembly problem in the shortest time possible.
The algorithm I created achieved the highest performance in our department for all grid sizes and densities.
//What's The Problem?
The task was to make an algorithm to fill a randomly generated target grid with tetromino puzzle pieces. The algorithm had to complete this task while leaving as few gaps as possible and taking as short of an amount of time as possible to achieve a high-performance score.
Tetromino pieces are shapes made up of all the possible arrangements of 4 squares. When a target grid is provided, for the algorithm to solve, a dictionary containing the number of each of these pieces is also provided. These are the pieces from which the target grid was generated meaning that there must always be at least one perfect solution. The challenge was to get as close to the perfect solution as possible.
The algorithm I created achieved the highest performance in our department for all grid sizes and densities.
//What's The Problem?
The task was to make an algorithm to fill a randomly generated target grid with tetromino puzzle pieces. The algorithm had to complete this task while leaving as few gaps as possible and taking as short of an amount of time as possible to achieve a high-performance score.
Tetromino pieces are shapes made up of all the possible arrangements of 4 squares. When a target grid is provided, for the algorithm to solve, a dictionary containing the number of each of these pieces is also provided. These are the pieces from which the target grid was generated meaning that there must always be at least one perfect solution. The challenge was to get as close to the perfect solution as possible.
//Algorithm Overview
The overall idea of my algorithm was initially inspired by Suduko where possibilities are gradually removed as new sections are filled in. All the scanning to see what pieces will fit at each point is only done one time when the code first runs. As the code places each piece, possibilities for other tiles are removed as these pieces would have intersected with the piece that was newly placed down. This can be seen in the visual representation shown here where the number represents how many possible pieces there are which could be used to cover each tile.
This method combined with a ranking algorithm which chooses the optimum coordinate on the grid to solve on each iteration, as well as a method for selecting the best choice of piece to fill in at that coordinate means that the solution has a very high accuracy reaching up to 98.89% for 0.8 density grids and averaging over 97% for 0.5 density grids.
For an in-depth explanation of the methodology and algorithm I created please see the full report linked below. Also, the full code is published on GitHub at the link bellow so you can test it out yourself.
︎Report Available Here
︎Code Available Here
The overall idea of my algorithm was initially inspired by Suduko where possibilities are gradually removed as new sections are filled in. All the scanning to see what pieces will fit at each point is only done one time when the code first runs. As the code places each piece, possibilities for other tiles are removed as these pieces would have intersected with the piece that was newly placed down. This can be seen in the visual representation shown here where the number represents how many possible pieces there are which could be used to cover each tile.
This method combined with a ranking algorithm which chooses the optimum coordinate on the grid to solve on each iteration, as well as a method for selecting the best choice of piece to fill in at that coordinate means that the solution has a very high accuracy reaching up to 98.89% for 0.8 density grids and averaging over 97% for 0.5 density grids.
For an in-depth explanation of the methodology and algorithm I created please see the full report linked below. Also, the full code is published on GitHub at the link bellow so you can test it out yourself.
︎Report Available Here
︎Code Available Here
//Tools Used
+ Laptop
+ Visual Studio Code
+ Laptop
+ Visual Studio Code
//Materials
+ Python
+ Pygame Module
+ Numpy Module
+ Python
+ Pygame Module
+ Numpy Module
//Date
+ December 2018
+ December 2018