LaserTank is NP-complete

DOI10.1007/978-3-030-43120-4_26arXiv1908.05966MaRDI QIDQ6323765FDOQ6323765

Authors: Per Alexandersson, Petter Restadh 

Publication date: 16 August 2019

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.

Mathematics Subject Classification ID

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

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)