1  #ifndef NINETAILMODEL_H
  2  #define NINETAILMODEL_H
  3  
  4  #include <iostream>
  5  #include "Graph.h" // Defined in Listing 26.2
  6  
  7  using namespace std;
  8  
  9  const int NUMBER_OF_NODES = 512;
 10  
 11  class NineTailModel
 12  {
 13  public:
 14    // Construct a model for the Nine Tail problem
 15    NineTailModel();
 16  
 17    // Return the index of the node
 18    int getIndex(vector<char>& node) const;
 19  
 20    // Return the node for the index
 21    vector<char> getNode(int index) const;
 22  
 23    // Return the shortest path of vertices from the specified
 24    // node to the root
 25    vector<int> getShortestPath(int nodeIndex) const;
 26  
 27    // Print a node to the console
 28    void printNode(vector<char>& node) const;
 29  
 30  protected:
 31    Tree* tree;
 32  
 33    // Return a vector of Edge objects for the graph
 34    // Create edges among nodes
 35    vector<Edge> getEdges() const;
 36  
 37    // Return the index of the node that is the result of flipping
 38    // the node at the specified position
 39    int getFlippedNode(vector<char>& node, int position) const;
 40  
 41    // Flip a cell at the specified row and column
 42    void flipACell(vector<char>& node, int row, int column) const;
 43  };
 44  
 45  NineTailModel::NineTailModel()
 46  {
 47    // Create edges
 48    vector<Edge> edges = getEdges();
 49  
 50    // Build a graph
 51    Graph<int> graph(NUMBER_OF_NODES, edges);
 52  
 53    // Build a BFS tree rooted at the target node
 54    tree = new Tree(graph.bfs(511));
 55  }
 56  
 57  vector<Edge> NineTailModel::getEdges() const
 58  {
 59    vector<Edge> edges;
 60  
 61    for (int u = 0; u < NUMBER_OF_NODES; u++)
 62    {
 63      for (int k = 0; k < 9; k++)
 64      {
 65        vector<char> node = getNode(u);
 66        if (node[k] == 'H')
 67        {
 68          int v = getFlippedNode(node, k);
 69          // Add edge (v, u) for a legal move from node u to node v
 70          edges.push_back(Edge(v, u));
 71        }
 72      }
 73    }
 74  
 75    return edges;
 76  }
 77  
 78  int NineTailModel::getFlippedNode(vector<char>& node, int position)
 79    const
 80  {
 81    int row = position / 3;
 82    int column = position % 3;
 83  
 84    flipACell(node, row, column);
 85    flipACell(node, row - 1, column);
 86    flipACell(node, row + 1, column);
 87    flipACell(node, row, column - 1);
 88    flipACell(node, row, column + 1);
 89  
 90    return getIndex(node);
 91  }
 92  
 93  void NineTailModel::flipACell(vector<char>& node,
 94    int row, int column) const
 95  {
 96    if (row >= 0 && row <= 2 && column >= 0 && column <= 2)
 97    { // Within boundary
 98      if (node[row * 3 + column] == 'H')
 99        node[row * 3 + column] = 'T'; // Flip from H to T
100      else
101        node[row * 3 + column] = 'H'; // Flip from T to H
102    }
103  }
104  
105  int NineTailModel::getIndex(vector<char>& node) const
106  {
107    int result = 0;
108  
109    for (int i = 0; i < 9; i++)
110      if (node[i] == 'T')
111        result = result * 2 + 1;
112      else
113        result = result * 2 + 0;
114  
115    return result;
116  }
117  
118  vector<char> NineTailModel::getNode(int index) const
119  {
120    vector<char> result(9);
121  
122    for (int i = 0; i < 9; i++)
123    {
124      int digit = index % 2;
125      if (digit == 0)
126        result[8 - i] = 'H';
127      else
128        result[8 - i] = 'T';
129      index = index / 2;
130    }
131  
132    return result;
133  }
134  
135  vector<int> NineTailModel::getShortestPath(int nodeIndex) const
136  {
137    return tree->getPath(nodeIndex);
138  }
139  
140  void NineTailModel::printNode(vector<char>& node) const
141  {
142    for (int i = 0; i < 9; i++)
143      if (i % 3 != 2)
144        cout << node[i];
145      else
146        cout << node[i] << endl;
147  
148    cout << endl;
149  }
150  
151  #endif