Tetrominoes
python
algorithm design
The TETROMINOES task was to tile a grid of various sizes and automatically generated tetris solutions, to the best accuracy possible and in the least amount of time possible.
This task was coded in python and used a depth first search, tetris piece prioritising, greedy algorithm which was recursive but has a running time of Θ(n), tiling a 1000x1000 grid in less than 12 seconds.
Each tetris block is specified and can be rotated in 4 orientations just like normal tetris games, and to complete the task with the best accuracy, I decided to check the grid from top left to bottom right, seeing if more ‘horizontal’ pieces fit, and prioritising them first into the grid. ie. the first priority would be checking for a free space a block to the left, meaning the most prioritised piece would be the flat 4 block piece. After all the horizontal pieces have been placed and scanned, the algorithm then started to check for more vertical pieces which could be placed as there would be no more available horizontal pieces. This resulted in more of a horizontal piece dominant top half of the grid and vertical piece dominant bottom half of the grid.
def CHECK(new_tar, a, b, z, randset, pieceset, pred, remove): randset1 = [] #making sure code is checking within the boundary if b - 1 >= 0: #b is the x coordinate of currently checking point if new_tar[z][b-1] == 1: #checking solution for 1s - places which need to be filled new_tar[z][b-1] -= 1 #updating copy of solution remove.append((z,b-1)) #outlining tetris piece randset1.append(z) #appending coordinates randset1.append(b) #appending coordinates pieceset.append('left') #the tetris piece can extend to the left pred = [z, b-1] #declaring predecessor return new_tar, pred, pieceset, randset1, remove if b + 1 <= len(a) - 1: if new_tar[z][b+1] == 1: .#same as before but checking right hand side pieceset.append('right') return new_tar, pred, pieceset, randset1, remove if z + 1 <= len(new_tar) - 1: #b is the z coordinate of currently checking point if new_tar[z+1][b] == 1: new_tar[z+1][b] -= 1 .#same as before but checking bottom piece pieceset.append('bot') return new_tar, pred, pieceset, randset1, remove
Example code checking and locating pieces within the solution. There is no function for checking for spaces above as the algorithm moves from top to bottom filling in all possible gaps.
This produced a large gap between blocks in the bottom half of the grid and therefore, a filling piece of code was used to tile the grid with the remaining pieces, this was rather successful and bumped up the accuracy by around 15-30% depending on density of the proposed problem.
The added code was checking pieces to available spaces instead of spaces to allocate pieces. This was a simple addition with a linear running time.
Have a look at the report for the proposed solution by clicking here!
