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 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.
|
---|