brief

Design an algorithm to solve the tetriling with missing pieces problem. This problem consists of finding a tiling of an arbitrary finite polyomino region by using Tetris pieces, with the exception of the O tetris piece and the I tetris pieces (shapeIDs = 1, 2, and 3 in image) - these are forbidden pieces. The objective is to perform the tiling as fast as possible while minimizing the sum of uncovered and added squares in the target region.

outcomes

The final algorithm was coded in python and utilises reduction in order to fill puzzle. It consists of multiple sub functions focused on individual tasks called in the main loop to iteratively find the best solution based on connected node traversal and greedy principles. Data was stored in dictionary structures and matrices were used to represent the puzzle grid, Final performance reached average 90% accuracy in 5 seconds for a puzzle of 1000x1000 blocks.