Tetranominoes Tiling Algorithm
The "tetranominoes tiling problem" is a well-known problem with no recognised optimum solution yet. It involve solving a puzzle generated using random combinations of Tetris pieces .
In this individual project, I designed an efficient and accurate algorithm to solve the puzzle. Which utilised various classic algorithm and computing concepts, and went through optimisation after running time analysis.
The algorithm breaks down the problem by first finding the connectivity of each node using graph theory concepts. By applying greedy algorithm method, shapes that cover the least connected nodes are found and placed, preventing those nodes from disconnecting to the rest of the graph. It resulted in an efficient algorithm that has a linear running time with an average of 95% accuracy, ranked as the second-best performing algorithm in my year.
The break-down of the algorithm:
Details and documentation of the project can be found on my Github.