On the NP-completeness of the logic puzzle irasuto

Abstract

This thesis investigates the computational complexity of the Japanese pen-and-paper puzzle irasuto. We show that the problem is NP-complete by presenting a polynomial time reduction from Planar Circuit SAT containing only NOR gates to irasuto.