Algorithm for solving Whack-A-Mole

Question

The problem is as follows:

• Imagine a "Whack a Mole" game in an n x n board.
• It has a random initial condition in which random moles are popped-up.
• In this problem, when you hit a mole, that mole and the adjacent ones change (Eg: if the adjacent ones are moles, they become holes, and if they are wholes, they become moles). You can only hit moles, you can't hit holes (this is the difference from "Lights Out" game).

The goal is to clear the whole board, i.e. to have no moles left anymore.

My questions are:

• Is there an algorithm in polynomial time that solves this?
• Are all initial configurations solvable?

Answer 1

In traditional Lights Out, we can use linear algebra over GF(2) to find the optimal set of moves (I say set because we never repeat a move, and it doesn’t matter what order we do them in).

Here we can find this set, but it may be impossible to actuate without modification. For example, on the board

..@@..
.@..@.
..@@..

we want to hit the middle two squares but can’t because they’re both off. Instead we can hit one of the on squares, hit the middle square that that enables, hit the first square again, and then hit the other middle square.

In general, given the set of moves that we would make in Lights Out, we can find the shortest path from an on square to a move, hit the shortest path in order and then in reverse (but hitting the move only once). This algorithm is polynomial time and shows both that every configuration that is solvable in Lights Out is solvable here.

For example, to solve

@@.
@@.
@..

we have to find a set of moves for Lights Out (using, for example, the light chasing method)

@@. ...
@@. ...
@.. ...

.@. ...
... 1..
... ...

... ...
@@@ 12.
.@. ...

... ...
.@@ 12.
@.. 3..

... ...
..@ 12.
.@@ 34.

... ...
... 12.
... 345

then reorder and add steps around the moves that hit a hole

@@. ...
@@. 12.
@.. 345

.@. ...
... .2.
... 345

@.@ .X.
.@. .2.
... 345

@@@ .X.
@.@ ...
.@. 345

... ...
@@@ ...
.@. 345

... ...
@.@ ...
@.@ 3.5

... ...
..@ ...
.@@ ..5

... ...
... ...
... ...

I’m using the right boards here to track what needs to be done (numbers for the Lights Out moves, X for the temporary moves).

I’m not sure how hard it is to find the shortest solution.