Light Up (Akari)

A single player game in which the player places light bulbs in rectangular black and white grid to light up all white cells.

Description

Light Up is a single player game played on a rectangular grid. Initially, the cells of the grid are either white or black, where black cells can optionally be labeled with an integer between $0$ and $4$ (inclusive).

The player can place light bulbs into white cells. Specifically, a light bulb $b$ lights a white cell $c$ if $b$ lies on the same row or column as $c$ (or both, i.e., $b$ is placed on $c$) and the portion of the row/column between by $b$ and $c$ contains no black cells. The goal is to find an arrangement of light bulbs such that:

The figure shows an instance of Light Up (left) and a possible solution (right).

Computational complexity

The problem of deciding whether an instance of Light Up admits a solution is NP-Complete [1].

References

[1] B. McPhail, “Light Up is NP-complete”.