Meno:  Dávid


Priezvisko:  Mišiak


Názov:  Computational approaches to polyomino tiling problems


Vedúci:  doc. RNDr. Ján Mazák, PhD.


Rok:  2022


Kľúčové slová:  polyomino tiling, SAT, linear programming, coloring invariants


Abstrakt:  The problem of tiling a board by polyominoes is a typical example of a searchbased problem. Our work explores several suitable approaches to solving the tiling problem: simple backtracking, using Algorithm X proposed by Donald Knuth, translating the tiling problem to the boolean satisfiability problem, translating it to integer linear programming, and using a constraint satisfaction solver. We describe useful implementation techniques for these approaches and create a commandline tool Tiler that integrates the solving algorithms with stateoftheart solvers. Finally, we prepare a detailed comparison of their performance on a collection of problem instances and identify classes of tiling instances that are better suited for one algorithm or another.

