| Meno: | Barbora
|
|---|
| Priezvisko: | Klembarová
|
|---|
| Názov: | Complexity of solving puzzles
|
|---|
| Vedúci: | RNDr. Michal Forišek, PhD.
|
|---|
| Rok: | 2018
|
|---|
| Kľúčové slová: | puzzle, human problem solving, computational complexity
|
|---|
| Abstrakt: | How is the complexity of solving puzzles by a human connected to computational complexity?
In this thesis we study two games Tilt maze and Sokoban.
From a computational point of view Tilt maze belongs to P and Sokoban belongs to PSPACE-complete problems.
We design different syntactic attributes of these puzzles and recognize those influencing difficulty in human problem solving.
We conclude this thesis by discussing how are these different aspects of problem complexity related, regarding specific attributes identified during human problem solving analysis.
|
|---|