Portal de Periódicos da CAPES

Satisfiability Parsimoniously Reduces to the Tantrix™ Rotation Puzzle Problem

2009; IOS Press; Volume: 91; Issue: 1 Linguagem: Inglês

10.3233/fi-2009-0032

1875-8681

Dorothea Baumeister, Jörg Rothe,

Computational Geometry and Mesh Generation

Holzer and Holzer [10] proved that the Tantrix™ rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We pr