solo

TETRILLING REASSEMBLY

Coding challenge to design an algorithm to solve a Tetris puzzle

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. Tetrominoes are polyominoes of four squares; they are popular for their use in the video game Tetris. Tetris pieces can have 19 types of shapes and can only be used a predetermined number of times

I was tasked with designing an algorithm to find a perfect tiling solution of an arbitrary finite polyomino region given a set number of Tetris pieces. The tiling should be performed as fast as possible whilst the number of uncovered squares is minimized as much as possible

Figure_1.png

10 x 10 target and calculated solution, completed in 0.00390 seconds with an accuracy of 100%

Figure_2.png

100 x 100 target and calculated solution, completed in 2.576 seconds with an accuracy of 88%

My algorithm operates using two different methods. 

Method 1 uses a greedy approach. It first orders all the pieces by the number used in the target and then places the first piece the fits in the solution. This system of making short term decisions without considering future implications is why this algorithm is greedy

Method 2 starts with a similar approach to method 1, however this time, once a piece is placed a check is done to see if any pieces can fit in the remaining space around it. If no pieces can be placed then the recently placed piece is removed and a new piece is tested. This continues until all the pieces have been placed, thus ensuring 100% accuracy.

Method 2 is only used on small sized targets as it would take too long on medium or large sizes, it is, however, extremely fast on small-sized targets.