Portal de Periódicos da CAPES

The three-color and two-color Tantrix™ rotation puzzle problems are NP-complete via parsimonious reductions

2009; Elsevier BV; Volume: 207; Issue: 11 Linguagem: Inglês

10.1016/j.ic.2009.03.001

1090-2651

Dorothea Baumeister, Jörg Rothe,

Digital Image Processing Techniques

Holzer and Holzer [M. Holzer, W. Holzer, Tantrix™ rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] proved that the Tantrix™ rotation puzzle problem with four colors is NP-complete, and they showed that the infinite variant of this problem is undecidable. In this paper, we study the three-color and two-color Tantrix™ rotation puzzle problems (3-TRP and 2-TRP) and their variants. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix™ tiles from 56 to 14 (respectively, to 8). We prove that 3-TRP and 2-TRP are NP-complete, which answers a question raised by Holzer and Holzer [M. Holzer, W. Holzer, Tantrix™ rotation puzzles are intractable, Discrete Applied Mathematics 144(3) (2004) 345–358] in the affirmative. Since our reductions are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. We also show that the another-solution problems associated with 4-TRP, 3-TRP, and 2-TRP are NP-complete. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.