Will Meyer – Lights Out, Advisor Dr. Nastase
The Lights Out game is played on an n x n rectangular grid with an on/off light at each vertex. When a light is toggled, the lights adjacent non-diagonal neighbors and itself changes to its opposite state. An NP-complete problem arises from this game. Given a starting configuration (with m lights in the on state) on an n x n grid, G. By using a sequence of toggle operations, can G be transformed to a grid with at least k switches in the off position. We propose a new algorithm, called Wave Cancellation, which seemingly reduces the search space for this problem to significantly smaller exponentially sized set of states to be examined and leads into more research opportunities.