In the Japanese logic puzzle Akari, you're presented with a grid of black and white squares.

The goal is to place light bulbs into white cells such that no two bulbs shine on one another and such that the whole grid is illuminated.

Each light bulb sends out rays of light horizontally and vertically, illuminating its row and column unless a black cell blocks the rays.

Assignment

To refer to the cells in the rectangular grid of an Akari puzzle, the rows are numbered from top to bottom, and the columns from left to right, starting from zero. As such, the position of a cell can be represented as a tuple $$(r, c)$$, where $$r \in \mathbb{N}$$ (int) indicates the row number and $$c \in \mathbb{N}$$ (int) the column number.

Define a class Akari that can be used to represent the grid of Akari puzzles. Three arguments must be passed when creating an Akari puzzle (Akari): i) the number of rows (int) in the grid, ii) the number of columns (int) in the grid, and iii) a collection (list, tuple or set) containing the positions of all black cells in the grid. Each Akari puzzle (Akari) must have at least the following properties:

• black_cells: a set containing the positions of all black cells in the grid

• light_bulbs: a set containing the positions of all light bulbs in the grid

In addition, Akari puzzles (Akari) must also support at least the following methods:

• A method add_light_bulb that takes the row number $$r$$ (int) and the column number $$c$$ (int) of a position in the grid. The method must check whether a light bulb can be placed at position $$(r, c)$$. This is the case if the following conditions are met

• position $$(r, c)$$ is inside the grid

• the cell at position $$(r, c)$$ is white

• the cell at position $$(r, c)$$ is not occupied by another light bulb

• the cell at position $$(r, c)$$ is not illuminated by another light bulb

If at least one of these conditions fails, an AssertionError must be raised with the message invalid position. Otherwise, the object must keep track of the fact that a lamp has been placed at position $$(r, c)$$.

• A method remove_light_bulb that takes the row number $$r$$ (int) and the column number $$c$$ (int) of a position in the grid. The method must remove the light bulb at position $$(r, c)$$. If there is no light bulb at position $$(r, c)$$, an AssertionError must be raised with the message invalid position.

• A method rays that takes the row number $$r$$ (int) and the column number $$c$$ (int) of the position of a white cell in the grid (the method must not check explicitly that the given position indicates a white cell). The method must return a set containing all positions that would be illuminated if there were only one light bulb on the grid at position $$(r, c)$$ (the method thus ignores any light bulbs that may already have been placed on the grid). The position $$(r, c)$$ may not be included in the set (the light bulb is placed on the cell and therefore the cell itself is not illuminated by the light bulb).

• A method illuminated that takes no arguments. The method must return a set containing the positions of all free white cells in the grid that are illuminated by at least one light bulb.

• A method issolved that takes no arguments. The method must return a Boolean value (bool) that indicates if the Akari puzzle has been solved. This is the case if all free white cells are illuminated by at least one light bulb.

If an Akari puzzle (Akari) is passed to the built-in function str, a string representation (str) of the grid must be returned. Each row forms a separate line, black cells are represented by a hash sign (#), white cells with a light bulb by an uppercase letter L, white cells that are illuminated by at least one light bulb by an asterisk (*) and all other white cells by an underscore (_).

Example

>>> puzzle = Akari(6, 6, [(1, 1), (2, 3), (2, 5), (3, 0), (3, 2), (4, 4)])
>>> puzzle.black_cells
{(3, 2), (3, 0), (4, 4), (2, 3), (2, 5), (1, 1)}
>>> puzzle.light_bulbs
set()
>>> puzzle.illuminated()
set()
>>> print(puzzle)
______
_#____
___#_#
#_#___
____#_
______
>>> puzzle.issolved()
False
>>> puzzle.rays(1, 1)
{(0, 1), (1, 2), (1, 3), (3, 1), (2, 1), (1, 4), (1, 5), (5, 1), (1, 0), (4, 1)}
>>> puzzle.rays(2, 1)
{(3, 1), (2, 0), (2, 2), (5, 1), (4, 1)}
>>> puzzle.add_light_bulb(2, 1)
>>> puzzle.light_bulbs
{(2, 1)}
>>> puzzle.illuminated()
{(2, 0), (2, 2), (5, 1), (3, 1), (4, 1)}
>>> print(puzzle)
______
_#____
*L*#_#
#*#___
_*__#_
_*____
>>> puzzle.issolved()
False
>>> puzzle.add_light_bulb(3, 6)      # outside grid
Traceback (most recent call last):
AssertionError: invalid position
>>> puzzle.add_light_bulb(1, 1)      # not on white cell
Traceback (most recent call last):
AssertionError: invalid position
>>> puzzle.add_light_bulb(2, 1)      # cell already contains a light bulb
Traceback (most recent call last):
AssertionError: invalid position
>>> puzzle.add_light_bulb(5, 1)      # cell is illuminated by another light bulb
Traceback (most recent call last):
AssertionError: invalid position
>>> puzzle.add_light_bulb(0, 1)
>>> puzzle.add_light_bulb(1, 0)
>>> puzzle.add_light_bulb(1, 2)
>>> puzzle.light_bulbs
{(0, 1), (1, 0), (2, 1), (1, 2)}
>>> puzzle.illuminated()
{(0, 0), (1, 3), (2, 2), (3, 1), (1, 4), (2, 0), (1, 5), (0, 5), (0, 4), (5, 1), (0, 3), (4, 1), (0, 2)}
>>> print(puzzle)
*L****
L#L***
*L*#_#
#*#___
_*__#_
_*____
>>> puzzle.issolved()
False
>>> puzzle.remove_light_bulb(1, 2)
>>> puzzle.light_bulbs
{(0, 1), (1, 0), (2, 1)}
>>> print(puzzle)
*L****
L#____
*L*#_#
#*#___
_*__#_
_*____
>>> puzzle.add_light_bulb(1, 2)
>>> print(puzzle)
*L****
L#L***
*L*#_#
#*#___
_*__#_
_*____
>>> puzzle.remove_light_bulb(2, 2)
Traceback (most recent call last):
AssertionError: invalid position
>>> puzzle.add_light_bulb(2, 4)
>>> puzzle.add_light_bulb(3, 3)
>>> puzzle.add_light_bulb(4, 0)
>>> puzzle.add_light_bulb(5, 5)
>>> puzzle.light_bulbs
{(0, 1), (1, 2), (3, 3), (5, 5), (2, 1), (1, 0), (2, 4), (4, 0)}
>>> puzzle.illuminated()
{(5, 4), (0, 0), (1, 3), (4, 1), (4, 5), (5, 2), (1, 4), (0, 5), (5, 1), (0, 3), (4, 2), (5, 3), (3, 5), (3, 1), (1, 5), (2, 0), (0, 4), (4, 3), (2, 2), (5, 0), (3, 4), (0, 2)}
>>> print(puzzle)
*L****
L#L***
*L*#L#
#*#L**
L***#*
*****L
>>> puzzle.issolved()
True

Epilogue

In an extension of the puzzle, some black cells may have a number on it from 0 to 4, indicating how many bulbs must be placed adjacent to its four sides. For example, a cell with a 4 must have four bulbs around it, one on each side, and a cell with a 0 cannot have a bulb next to any of its sides. An unnumbered black cell may have any number of light bulbs adjacent to it, or none. Bulbs placed diagonally adjacent to a numbered cell do not contribute to the bulb count.

Here's a moderately difficult puzzle that makes use of this extension. Can you solve it?

 Show answer