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?
CodePudding user response：
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.
CodePudding user response：
Overview
Let me adapt my answer from Lights Out - finding worst initial state, you can read the details there.
Basically, you can just interpret your problem as a shortest path problem and then run any shortest path algorithms on it.
The nodes of the graph are your game states, i.e. the board (states of all holes and moles). Edges between the states represent the valid moves.
The graph is a subgraph of the lights-out graph, where you just skip any edge that represent clicking a hole instead of a mole.
Answers
For simplicity, let me assume a 3x3 board, you can adapt this to any dimensions if you want.
Is there an algorithm in polynomial time that solves this?
For example Dijkstra, which definitely runs in polynomial time.
Are all initial configurations solvable?
No, only 285 of 512 initial configurations are solvable.
For example the configuration
1 1 0
1 1 0
1 0 0
is not solvable (true means mole, false means hole). You can find the full list here.
Code
The full code (Java) to compute all of this would be this:
import io.github.zabuzard.maglev.external.algorithms.ShortestPathComputationBuilder;
import io.github.zabuzard.maglev.external.graph.Edge;
import io.github.zabuzard.maglev.external.graph.Graph;
import io.github.zabuzard.maglev.external.graph.simple.ReversedConsumer;
import io.github.zabuzard.maglev.external.graph.simple.ReversedProvider;
import io.github.zabuzard.maglev.external.graph.simple.SimpleGraph;
import java.util.*;
public final class WhackAMoleSolver {
public static void main(String[] args) {
Graph<GameState, ClickEdge<GameState>> graph = generateGraph();
var algo = new ShortestPathComputationBuilder<>(graph).resetOrdinaryDijkstra()
.addModuleIgnoreEdgeIf(edge -> {
int x = edge.getX();
int y = edge.getY();
boolean[][] destination = edge.getDestination()
.getBoard();
return destination[x][y]; // Ignore if clicking a hole
})
.build();
GameState solvedState =
new GameState(new boolean[][] { { true, true, true }, { true, true, true }, { true, true, true } });
var pathTree = algo.shortestPathReachable(solvedState);
System.out.println("Reached " pathTree.getLeaves()
.size() " leaves.");
System.out.println("Graph has " graph.size() " nodes.");
Collection<GameState> nodes = new HashSet<>(graph.getNodes());
nodes.removeAll(pathTree.getLeaves());
System.out.println("Unreached nodes are: ");
for (GameState state : nodes) {
System.out.println(state);
System.out.println("--------");
}
}
private static Graph<GameState, ClickEdge<GameState>> generateGraph() {
SimpleGraph<GameState, ClickEdge<GameState>> graph = new SimpleGraph<>();
generateNodes(graph);
generateEdges(graph);
return graph;
}
private static void generateNodes(Graph<GameState, ClickEdge<GameState>> graph) {
for (int i = 0; i < 1 << 9; i ) {
String boardString = String.format(" d", Integer.parseInt(Integer.toBinaryString(i)));
graph.addNode(GameState.of(boardString, 3, 3));
}
}
private static void generateEdges(Graph<GameState, ClickEdge<GameState>> graph) {
for (GameState source : graph.getNodes()) {
// Click on each field
boolean[][] board = source.getBoard();
for (int x = 0; x < board.length; x ) {
for (int y = 0; y < board[x].length; y ) {
GameState destination = new GameState(board);
destination.click(x, y);
graph.addEdge(new ClickEdge<>(source, destination, 1, x, y));
}
}
}
}
private static final class ClickEdge<N> implements Edge<N>, ReversedConsumer {
private final double cost;
private final N destination;
private final N source;
private ReversedProvider reversedProvider;
private final int x;
private final int y;
private ClickEdge(final N source, final N destination, final double cost, final int x, final int y) {
if (cost < 0) {
throw new IllegalArgumentException("Cost must not be negative");
}
this.source = Objects.requireNonNull(source);
this.destination = Objects.requireNonNull(destination);
this.cost = cost;
this.x = x;
this.y = y;
}
private int getX() {
return x;
}
private int getY() {
return y;
}
@Override
public double getCost() {
return cost;
}
@Override
public N getDestination() {
if (reversedProvider != null && reversedProvider.isReversed()) {
return source;
}
return destination;
}
@Override
public N getSource() {
if (reversedProvider != null && reversedProvider.isReversed()) {
return destination;
}
return source;
}
@Override
public void setReversedProvider(final ReversedProvider provider) {
reversedProvider = Objects.requireNonNull(provider);
}
}
private static class GameState {
public static GameState of(String boardString, int rows, int columns) {
boolean[][] board = new boolean[rows][columns];
int i = 0;
for (int x = 0; x < rows; x ) {
for (int y = 0; y < columns; y ) {
board[x][y] = boardString.charAt(i) == '1';
i ;
}
}
return new GameState(board);
}
private final boolean[][] board;
private GameState(boolean[][] board) {
this.board = new boolean[board.length][];
for (int x = 0; x < board.length; x ) {
this.board[x] = new boolean[board[x].length];
for (int y = 0; y < board[x].length; y ) {
this.board[x][y] = board[x][y];
}
}
}
public boolean[][] getBoard() {
return board;
}
@Override
public String toString() {
StringJoiner rowJoiner = new StringJoiner("\n");
for (int x = 0; x < board.length; x ) {
StringJoiner row = new StringJoiner(" ");
for (int y = 0; y < board[x].length; y ) {
row.add(board[x][y] ? "1" : "0");
}
rowJoiner.add(row.toString());
}
return rowJoiner.toString();
}
@Override
public boolean equals(final Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final GameState gameState = (GameState) o;
return Arrays.deepEquals(board, gameState.board);
}
@Override
public int hashCode() {
return Arrays.deepHashCode(board);
}
private void click(int x, int y) {
toggle(x, y);
toggle(x, y - 1);
toggle(x, y 1);
toggle(x - 1, y);
toggle(x 1, y);
}
private void toggle(int x, int y) {
if (x < 0 || y < 0 || x >= board.length || y >= board[x].length) {
return;
}
board[x][y] = !board[x][y];
}
}
}
Output:
Reached 258 leaves.
Graph has 512 nodes.
Unreached nodes are:
1 1 0
1 0 0
0 1 0
--------
...
The code to double check that a configuration is not solveable is this:
Graph<GameState, ClickEdge<GameState>> graph = generateGraph();
var algo = new ShortestPathComputationBuilder<>(graph).resetOrdinaryDijkstra()
.addModuleIgnoreEdgeIf(edge -> {
int x = edge.getX();
int y = edge.getY();
boolean[][] source = edge.getSource()
.getBoard();
return source[x][y]; // Ignore if clicking a hole
})
.build();
GameState source =
new GameState(new boolean[][] { { true, true, false }, { true, true, false }, { true, false, false } });
GameState destination = new GameState(
new boolean[][] { { false, false, false }, { false, false, false }, { false, false, false } });
System.out.println(algo.shortestPath(source, destination));
which outputs
Optional.empty
The code requires the external framework Maglev. See the linked SO answer which this answer is based on for details.