The nine tails problem can be reduced to the shortest path problem.

The nine tails problem is as follows. Nine coins are placed in a three-by-three matrix with some face up and some face down. A legal move is to take a coin that is face up and reverse it, together with the coins adjacent to it (this does not include coins that are diagonally adjacent). Your task is to find the minimum number of moves that lead to all coins being face down. For example, start with the nine coins as shown in Figure below (a). After you flip the second coin in the last row, the nine coins are now as shown in Figure below (b). After you flip the second coin in the first row, the nine coins are all face down, as shown in Figure below (c).

We will write a program that prompts the user to enter an initial state of the nine coins and displays the solution, as shown in the following sample run.

`Enter the initial nine coins Hs and Ts: HHHTTTHHH`

The steps to flip the coins are

HHH

TTT

HHH

HHH

THT

TTT

TTT

TTT

TTT

Each state of the nine coins represents a node in the graph. For example, the three states in Figure above correspond to three nodes in the graph. For convenience, we use a 3 * 3 matrix to represent all nodes and use **0** for heads and **1** for tails. Since there are nine cells and each cell is either **0** or **1**, there are a total of 2^9 (512) nodes, labeled **0**, **1**, . . . , and **511**, as shown in Figure below.

We assign an edge from node **v** to **u** if there is a legal move from **u** to **v**. Figure below shows a partial graph. Note there is an edge from **511** to **47**, since you can flip a cell in node **47** to become node **511**.

The last node in Figure below represents the state of nine face-down coins. For convenience, we call this last node the *target node*. Thus, the target node is labeled **511**. Suppose the initial state of the nine tails problem corresponds to the node **s**. The problem is reduced to finding a shortest path from node **s** to the target node, which is equivalent to finding a shortest path from node **s** to the target node in a BFS tree rooted at the target node.

Now the task is to build a graph that consists of 512 nodes labeled **0**, **1**, **2**, . . . , **511**, and edges among the nodes. Once the graph is created, obtain a BFS tree rooted at node **511**. From the BFS tree, you can find a shortest path from the root to any vertex. We will create a class named **NineTailModel**, which contains the method to get a shortest path from the target node to any other node. The class UML diagram is shown in Figure below.

Visually, a node is represented in a 3 * 3 matrix with the letters **H** and **T**. In our program, we use a single-dimensional array of nine characters to represent a node. For example, the node for vertex **1** in Figure below is represented as {**'H'**, **'H'**, **'H'**, **'H'**, **'H'**, **'H'**, **'H'**, **'H'**, **'T'**} in the array.

The **getEdges()** method returns a list of **Edge** objects.

The **getNode(index)** method returns the node for the specified index. For example, **getNode(0)** returns the node that contains nine **H**s. **getNode(511)** returns the node that contains nine **T**s. The **getIndex(node)** method returns the index of the node.

Note that the data field **tree** is defined as protected so that it can be accessed from the **WeightedNineTail** subclass.

The **getFlippedNode(char[] node, int position)** method flips the node at the specified position and its adjacent positions. This method returns the index of the new node.

The position is a value from **0** to **8**, which points to a coin in the node, as shown in the following figure.

For example, for node **56** in Figure below, flip it at position **0**, and you will get node **51**. If you flip node **56** at position **1**, you will get node **47**.

The **flipACell(char[] node, int row, int column)** method flips a node at the specified row and column. For example, if you flip node **56** at row **0** and column **0**, the new node is **408**. If you flip node **56** at row **2** and column **0**, the new node is **30**.

The code below shows the source code for NineTailModel.java.

```
import java.util.*;
public class NineTailModel {
public final static int NUMBER_OF_NODES = 512;
protected AbstractGraph<Integer>.Tree tree; // Define a tree
/** Construct a model */
public NineTailModel() {
// Create edges
List<AbstractGraph.Edge> edges = getEdges();
// Create a graph
UnweightedGraph<Integer> graph = new UnweightedGraph<>(edges, NUMBER_OF_NODES);
// Obtain a BSF tree rooted at the target node
tree = graph.bfs(511);
}
/** Create all edges for the graph */
private List<AbstractGraph.Edge> getEdges() {
List<AbstractGraph.Edge> edges = new ArrayList<>(); // Store edges
for (int u = 0; u < NUMBER_OF_NODES; u++) {
for (int k = 0; k < 9; k++) {
char[] node = getNode(u); // Get the node for vertex u
if (node[k] == 'H') {
int v = getFlippedNode(node, k);
// Add edge (v, u) for a legal move from node u to node v
edges.add(new AbstractGraph.Edge(v, u));
}
}
}
return edges;
}
public static int getFlippedNode(char[] node, int position) {
int row = position / 3;
int column = position % 3;
flipACell(node, row, column);
flipACell(node, row - 1, column);
flipACell(node, row + 1, column);
flipACell(node, row, column - 1);
flipACell(node, row, column + 1);
return getIndex(node);
}
public static void flipACell(char[] node, int row, int column) {
if (row >= 0 && row <= 2 && column >= 0 && column <= 2) {
// Within the boundary
if (node[row * 3 + column] == 'H')
node[row * 3 + column] = 'T'; // Flip from H to T
else
node[row * 3 + column] = 'H'; // Flip from T to H
}
}
public static int getIndex(char[] node) {
int result = 0;
for (int i = 0; i < 9; i++)
if (node[i] == 'T')
result = result * 2 + 1;
else
result = result * 2 + 0;
return result;
}
public static char[] getNode(int index) {
char[] result = new char[9];
for (int i = 0; i < 9; i++) {
int digit = index % 2;
if (digit == 0)
result[8 - i] = 'H';
else
result[8 - i] = 'T';
index = index / 2;
}
return result;
}
public List<Integer> getShortestPath(int nodeIndex) {
return tree.getPath(nodeIndex);
}
public static void printNode(char[] node) {
for (int i = 0; i < 9; i++)
if (i % 3 != 2)
System.out.print(node[i]);
else
System.out.println(node[i]);
System.out.println();
}
}
```

The constructor (lines 8–18) creates a graph with 512 nodes, and each edge corresponds to the move from one node to the other (line 10). From the graph, a BFS tree rooted at the target node **511** is obtained (line 17).

To create edges, the **getEdges** method (lines 21–37) checks each node **u** to see if it can be flipped to another node **v**. If so, add (**v**, **u**) to the **Edge** list (line 31). The **getFlippedNode(node, position)** method finds a flipped node by flipping an **H** cell and its neighbors in a node (lines 43–47). The **flipACell(node, row, column)** method actually flips an **H** cell and its neighbors in a node (lines 52–60).

The **getIndex(node)** method is implemented in the same way as converting a binary number to a decimal number (lines 62–72). The **getNode(index)** method returns a node consisting of the letters **H** and **T** (lines 74–87).

The **getShortestpath(nodeIndex)** method invokes the **getPath(nodeIndex)**

method to get a vertices in a shortest path from the specified node to the target node

(lines 89–91).

The **printNode(node)** method displays a node on the console (lines 93–101).

The code below gives a program that prompts the user to enter an initial node and displays the steps to reach the target node.

```
import java.util.Scanner;
public class NineTail {
public static void main(String[] args) {
// Prompt the user to enter nine coins' Hs and Ts
System.out.print("Enter the initial nine coins Hs and Ts: ");
Scanner input = new Scanner(System.in);
String s = input.nextLine();
char[] initialNode = s.toCharArray();
NineTailModel model = new NineTailModel();
java.util.List<Integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));
System.out.println("The steps to flip the coins are ");
for (int i = 0; i < path.size(); i++)
NineTailModel.printNode(NineTailModel.getNode(path.get(i).intValue()));
}
}
```

The program prompts the user to enter an initial node with nine letters with a combination of **H**s and **T**s as a string in line 8, obtains an array of characters from the string (line 9), creates a graph model to get a BFS tree (line 11), obtains a shortest path from the initial node to the

target node (lines 12–13), and displays the nodes in the path (lines 16–18).

## Top comments (0)