LaserTank is NP-complete

DOI10.1007/978-3-030-43120-4_26MaRDI QIDQ6323765arXivFDO

Authors Per Alexandersson, Petter Restadh

Publication date 16 August 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-43120-4_26

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

arXiv classification

cs.CCmath.CO

Abstract: We show that the classical game LaserTank is $mathrmNP$-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.

This page was built for publication: LaserTank is NP-complete

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