Top

Published in:

2020 | OriginalPaper | Chapter

LaserTank is NP-Complete

Authors : Per Alexandersson, Petter Restadh

Published in: Mathematical Aspects of Computer and Information Sciences

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We show that the classical game LaserTank is \(\mathrm {NP}\)-complete, even when the tank movement is restricted to a single column and the only blocks appearing on the board are mirrors and solid blocks. We show this by reducing 3-SAT instances to LaserTank puzzles.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Fast Counting Method for 6-Motifs with Low Connectivity

next chapter Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness

https://en.wikipedia.org/wiki/LaserTank.

https://www.ticalc.org/archives/files/fileinfo/95/9532.html.

For a complete list of pieces available in the official game, see https://lasertanksolutions.blogspot.com/p/in-my-opinionlaser-tank-is-best-logic.html.

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151–158. ACM, New York (1971). https://doi.org/10.1145/800157.805047

Demaine, E.D., Hohenberger, S., Liben-Nowell, D.: Tetris is hard, even to approximate. Technical report, MIT-LCS-TR-865. MIT, Cambridge (2002). https://arxiv.org/abs/cs/0210020

Dor, D., Zwick, U.: SOKOBAN and other motion planning problems. Comput. Geom. 13(4), 215–228 (1999). https://doi.org/10.1016/s0925-7721(99)00017-6CrossRefMathSciNetMATH

Flake, G.W., Baum, E.B.: Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theor. Comput. Sci. 270(1–2), 895–911 (2002). https://doi.org/10.1016/s0304-3975(01)00173-6CrossRefMathSciNetMATH

Kaye, R.: Minesweeper is NP-complete. Math. Intell. 22(2), 9–15 (2000). https://doi.org/10.1007/bf03025367CrossRefMathSciNetMATH

Scott, A., Stege, U., van Rooij, I.: Minesweeper may not be NP-complete but is hard nonetheless. Math. Intell. 33(4), 5–17 (2011). https://doi.org/10.1007/s00283-011-9256-xCrossRefMathSciNetMATH

Viglietta, G.: Gaming is a hard job, but someone has to do it! Theory Comput. Syst. 54(4), 595–621 (2013). https://doi.org/10.1007/s00224-013-9497-5

Title: LaserTank is NP-Complete
Authors: Per Alexandersson
Petter Restadh
Publisher: Springer International Publishing
Book: Mathematical Aspects of Computer and Information Sciences
Print ISBN: 978-3-030-43119-8

Electronic ISBN: 978-3-030-43120-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-43120-4_26

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner