TANTRIX^TM rotation puzzles are intractable

DOI10.1016/J.DAM.2003.11.011zbMATH Open1156.68391OpenAlexW2161957859MaRDI QIDQ1765243FDOQ1765243

Authors: Markus Holzer, Waltraud Holzer 

Publication date: 23 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.11.011

Recommendations

• The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• Satisfiability Parsimoniously Reduces to the Tantrix™ Rotation Puzzle Problem
• Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem
• An integer programming approach to solving Tantrix on fixed boards

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• The complexity of theorem-proving procedures
• Title not available (Why is that?)
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• GO Is Polynomial-Space Hard
• Title not available (Why is that?)
• Minesweeper is NP-complete.
• On the complexity of chess
• Planar Crossovers
• Domino Games and Complexity

Cited In (9)

• An integer programming approach to solving Tantrix on fixed boards
• How to solve the torus puzzle
• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem
• Open questions on Tantrix graphs
• Satisfiability Parsimoniously Reduces to the Tantrix™ Rotation Puzzle Problem
• The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
• Variations on instant insanity
• Tetris and decidability

This page was built for publication: TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1765243)