8
$\begingroup$

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is the rule:

1: The light of the lamps spread only in 4 directions: up, down, left and right.

2: The light can spread to any distance unless it meets an obstacle or the boundary of this matrix.

3: Obstacle is a kind of elements in this matrix that any light can't spread through it.

4: The location of a lamp is illuminated by itself.

Now the task is to establish an algorithm that can illuminate the whole matrix with the least lamps.

The problem seems to be a variant of Art Gallery Problem, but it's not easy to apply the solution for Art Gallery Problem to this one.

I tried Greedy algorithm: Compuate $I_{ij}:=$ #{ blocks can be illuminated by putting a lamp at $a_{ij}$}, then put a lamp at $a_{i_0j_0}$, which $I_{i_0j_0}=\max{I_{ij}}$. Repeat this step, until all the empty blocks( the non-obstacle blocks).

It turn out to be that my method can't provide the number I need. It's not strong enough to get the minimal number of lamps.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I would be amazed if this problem (specifically, the threshold version 'is there a lamplighting of this grid with $k$ or fewer lamps?') isn't NP-complete. It seems like it would be pretty straightforward to craft 'gadgets' for doing signal propagation and boolean operations analagous to the ones that are used in many NP-completeness proofs (e.g. Minesweeper's), and contrariwise the question is clearly in NP. $\endgroup$
    – Steven Stadnicki
    Commented Apr 1, 2016 at 16:18
  • 1
    $\begingroup$ nikoli.com has a puzzle series called Akari. Doubtless there are discussion boards and some analysis on this puzzle type that may shed light (pun intended) on your problem. Gerhard "Be Glad For So Few" Paseman, 2016.04.01. $\endgroup$
    – Gerhard Paseman
    Commented Apr 1, 2016 at 16:53

3 Answers 3

Reset to default
3
$\begingroup$

If the set of obstacles forms a checkerboard, then $\lceil \frac{mn}{2} \rceil$ lamps are required. On the other hand, $\lceil \frac{mn}{2} \rceil$ lamps always suffice. This is clear if $m$ is even. If $m=2k+1$, we group the rows into $k$ $2 \times n$ blocks and one $1 \times n$ block. Each $2 \times n$ block requires at most $n$ lamps, and the $1 \times n$ block requires at most $\lceil \frac{n}{2} \rceil$ lamps.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You have got a very rough upper bound, but it seems to be helpless for finding the accurate number. $\endgroup$
    – Yijun Yuan
    Commented Apr 1, 2016 at 13:34
1
$\begingroup$

This problem seems related to rook polynomials.

Perhaps something enlightening can come from studying $$\sum_{p:lamp-placement} t^{|p|} q^{area(p)} $$ where the area is number of squares not lit, and $|p|$ is the number of lamps...

Improve this answer
$\endgroup$
2
1
$\begingroup$

This problem, it seems to me anyway, is a variant of the domination-separation problem on the $m \times n$ rooks graph, if not the problem itself. Your obstacles can be thought of as blocking pawns. If the obstacles aren't set, and are free to be placed anywhere on our $m\times n$ board, then it is the domination-separation problem. If the obstacles are fixed in their position then the minimum number of rooks needed to dominate changes depending upon where the pawns are placed.

Some work has been done for the case where $m=n$ for the domination-separation problem on the $m \times n$ rook's graph. In Proposition 9 in the paper below, it is shown that in order to decrease the domination number from $n$ to $n-k$ it takes exactly $k^2$ pawns. As far as I know, the case for which $m \neq n$ is an open question.

R. D. Chatham, M. Doyle, G. H. Fricke, J. Reitmann, R. D. Skaggs, and M. Wolff, Independence and Domination Separation in Chessboard Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 68 (2009), pp. 3--17.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .