Case Study: The Nine Tails Problem

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 Hs. getNode(511) returns the node that contains nine Ts. 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 Hs and Ts 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).