The Theory Behind Tetris

U of G researcher is reassembling real-world puzzles using the theory behind Tetris.

The puzzle-based video game Tetris was released in 1984 and took the world by storm. The basic idea of the game is to move different shaped tiles as they descend on a screen, to form complete lines, subsequently earning points and advancing levels in the game. The shapes used in Tetris are called polyominoes, which are generalizations of the domino. Each tile is constructed by putting several squares edge-to-edge to create shapes. The game ends when the entire playing field is filled, and no further moves are possible.

Tetris can be understood using tiling theory, which covers many different types of puzzle problems. The goal of tiling theory is to attempt to reassemble a region that has been broken into smaller pieces, which has implications beyond games: It can be used to create decorative patterns, computer generate texture in images and even reassemble shattered priceless artifacts.

The larger a puzzle problem becomes, the more difficult it is to solve. The traditional tactic to solve these puzzles uses a brute-force computer science algorithmic approach called backtracking. Backtracking incrementally creates solutions and then discards the ones that do solve the puzzle or problem. This approach is often time consuming and data-intensive.

University of Guelph Department of Mathematics and Statistics professor, Dr. Marcus Garvie, and a collaborator at the University of Pittsburgh Dr. John Burkardt have focused on developing the field of linear programming to tackle these large and difficult puzzles. In their recent paper furthering the study of tiling theory, Garvie and Burkardt combine checkerboard colouring techniques and integer linear programming to more efficiently solve large tiling problems with polyominoes. The checkerboard colouring technique allows the large tiling problem to be split into multiple smaller independently solvable tiling problems, which can be solved in parallel. An integer linear programming problem is a mathematical optimization problem in which some or all of the variables are restricted to be integers (integers are whole numbers, for example, 21 is an integer, while 9.75 is not).

Putting the puzzle back together

Garvie and Burkardt aim to gain mathematical insights into tiling problems and streamline solutions with their approach, which is very flexible. For example, it can be used to solve a puzzle with an arbitrary number of pieces and an arbitrary shaped region to be filled. The technique is also applicable to puzzles that are not based on squares, instead using puzzle pieces that are constructed from placing triangles or hexagons edge-to-edge. Garvie and Burkardt have been able to apply their approach to puzzle problems with missing pieces or where only an approximate solutions is possible, thus obtaining the best possible tiling solution.

Tiling theory has also been used to re-construct broken pots or vases from antiquity. For example, the Portland vase was a Roman glass vase, dated between AD 1 and AD 25, which was shattered and had to be re-constructed.

Left: Shatterned Portland Vase. Right: Reconstructed Portland Vase.

  Dr. Marcus Garvie is an Associate Professor in the Department of Mathematics and Statistics. Here he is seen playing Eternity, a puzzle marketed as practically unsolveable. 

Garvie M Burkardt J. A Parallelizable Integer Linear Programming Approach for Tiling Finite Regions of the Plane with Polyominoes. Algorithms. 2022 May 12. doi: 10.3390/a15050164.

Garvie M Burkardt J. A new algorithm based on colouring arguments for identifying impossible polyomino tiling problems. Algorithms. 2022 Feb 17. doi: 10.3390/a15020065.

Garvie M Burkardt J. A new mathematical model for tiling finite regions of the plane with polyominoes. Contrib. Discrete Math. 2020 July 30. doi: 10.11575/cdm.v15i2.62866.