Názov:Computational approaches to polyomino tiling problems
Vedúci:doc. RNDr. Ján Mazák, PhD.
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 search-based 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 command-line tool Tiler that integrates the solving algorithms with state-of-the-art 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.

Súbory bakalárskej práce:


Súbory prezentácie na obhajobe: