title: A star implementation in C++ (Language Issues)
body: <p>I am working on an A star algorithm to solve an N tile slide puzzle. Give a particular goal state I want to find the least number of steps to solve it. I understand the algorithm but I am having issues with C++ due to my lack of understanding. Any style suggestions would be greatly appreciated as well.</p>
  
  <ul>
  <li>Overload Operator Assignment: seems like there is a problem with deleting elements pointer, so right now I am manually reassigning everything    </li>
  <li>browseNeighbor: seems to do everything I want it to but the data that gets pushed back onto the open vector the values in elements seem to get jumbled when it is accessed again in the solve function. </li>
  <li>Right now I am only letting it access leftIndex to perform move left and giving it a really simple problem to solve to see if it works, but the two issues above prevent it from working right.</li>
  </ul>
  
  <p>C++ code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;cmath&gt;
  #include &lt;list&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  class board{
      public:
          int boardSize;
          int *elements; //ptr to array
          int rowSize;
          int zeroIndex;
          int upIndex;
          int downIndex;
          int leftIndex;
          int rightIndex;
          int h;
          int g;
          int f;
          board();
          board(int new_rowSize, int new_elements[]);
          ~board();
          void updateZero();
          void updateUpIndex();
          void updateDownIndex();
          void updateLeftIndex();
          void updateRightIndex();
          void updateIndexes();
          void moveUp();
          void moveDown();
          void moveLeft();
          void moveRight();
          bool operator==(const board&amp;);
          board&amp; operator=(const board&amp;);
  };
  board::board(){
      rowSize = 3;
      boardSize = rowSize * rowSize;
      elements = new int[boardSize];
  }
  board::board(int new_rowSize, int new_elements[]){
      rowSize = new_rowSize;
      boardSize = rowSize * rowSize;
      elements = new int[boardSize];
      for(int i = 0; i &lt; boardSize; i++) {
          elements[i] = new_elements[i];
      }
  }
  board::~board(){
      delete [] elements;
  }
  void board::updateZero(){
      for(int i = 0; i &lt; boardSize; i++){
          if(elements[i] == 0) {
              zeroIndex = i;
              break;
          }
      }
  }
  void board::updateUpIndex(){
      int temp_upIndex = zeroIndex + rowSize;
      if (temp_upIndex &lt; boardSize) {
          upIndex = temp_upIndex;
      }
      else {
          upIndex = -1;
      }
  }
  void board::updateDownIndex(){
      int temp_downIndex = zeroIndex - rowSize;
      if (temp_downIndex &gt;= 0) {
          downIndex = temp_downIndex;
      }
      else {
          downIndex = -1;
      }
  }
  void board::updateLeftIndex(){
      int temp_leftIndex = zeroIndex + 1;
      if(temp_leftIndex % rowSize != 0) {
          leftIndex = temp_leftIndex;
      }
      else {
          leftIndex = -1;
      }
  }
  void board::updateRightIndex(){
      int temp_rightIndex = zeroIndex - 1;
      if(zeroIndex &gt;= 0 &amp;&amp; temp_rightIndex % rowSize - 1 != 0) {
          rightIndex = temp_rightIndex;
      }
      else {
          rightIndex = -1;
      }
  }
  void board::updateIndexes(){
      updateZero();
      updateUpIndex();
      updateDownIndex();
      updateLeftIndex();
      updateRightIndex();
  }
  bool board::operator==(const board&amp; second){
      bool result = true;
      for(int i = 0; i &lt; boardSize; i++){
          if(elements[i] != second.elements[i])
              result = false;
      }
      return result;
  }
  void board::moveUp(){
      elements[zeroIndex] = elements[upIndex];
      elements[upIndex] = 0;
  }
  void board::moveDown(){
      elements[zeroIndex] = elements[downIndex];
      elements[downIndex] = 0;
  }
  void board::moveLeft(){
      elements[zeroIndex] = elements[leftIndex];
      elements[leftIndex] = 0;
  }
  void board::moveRight(){
      elements[zeroIndex] = elements[rightIndex];
      elements[rightIndex] = 0;
  }
  board&amp; board::operator=(const board&amp; rhs){
      if(this != &amp;rhs){
          delete [] elements;
          boardSize = rhs.boardSize;
          rowSize = rhs.rowSize;
  
          elements = new int[boardSize];
          for(int i = 0; i &lt; boardSize; i++) {
              elements[i] = rhs.elements[i];
          } 
  
          zeroIndex = rhs.zeroIndex;
          upIndex = rhs.upIndex;
          downIndex = rhs.downIndex;
          leftIndex = rhs.leftIndex;
          rightIndex = rhs.rightIndex;
          h = rhs.h;
          g = rhs.g;
          f = rhs.f;
      }
      return *this;
  }
  
  int manhattan(board *goal, board *current){
      int sum = 0;
      for(int i = 0; i &lt; goal-&gt;boardSize; i++) {
          for(int j = 0; j &lt; current-&gt;boardSize; j++) {
              if(goal-&gt;elements[i] == current-&gt;elements[j]) {
                  //this produces (goal.x - current.x) + (goal.y - current.y)
                  sum += abs(i%goal-&gt;rowSize - j%goal-&gt;rowSize) + abs(i/goal-&gt;rowSize - j/goal-&gt;rowSize);
                  break;
              }
          }
      }
  
      return sum;
  }
  
  void browseNeighbor(board *goal, board *x, vector&lt;board *&gt; *open, vector&lt;board *&gt; *closed){
              //check if in closed
              x-&gt;updateIndexes();
              for(int i = 0; i &lt; closed-&gt;size(); i++){
                  if(x == closed-&gt;at(i)) {
                      return;
                  }
              }
  
              int tenative_g = x-&gt;g + 1;
              //check if not in opn
              //flag for in or not
              bool in_open = false;
              int open_index = -1;
              for(int i = 0;  i &lt; open-&gt;size(); i++){
                  if(x == open-&gt;at(i)){
                      in_open = true;
                      open_index = i;
                  }
              }
              //cout &lt;&lt; "The value of in open is " &lt;&lt; in_open &lt;&lt; endl;
              bool tenative_is_better = false;
              if(in_open == false) {
                  //open-&gt;push_back(x);
                  tenative_is_better = true;
              }
              else if(tenative_g &lt; x-&gt;g){
                  tenative_is_better = true;
              }
              else {
                  //tenative_is_better = false;
                  return;
              }
              if(tenative_is_better == true){
                  //how to update correctly
                  //if just placed than access in_open.back()
                  //if not placed, find it in open
                  if(in_open == false){
                      x-&gt;g = tenative_g;
                      x-&gt;h = manhattan(goal,x);
                      x-&gt;f = x-&gt;g + x-&gt;h;
                      open-&gt;push_back(x);
                  }
                  else{
                      open-&gt;at(open_index)-&gt;g = tenative_g;
                      open-&gt;at(open_index)-&gt;h = manhattan(goal,x);
                      open-&gt;at(open_index)-&gt;f = open-&gt;at(open_index)-&gt;g + open-&gt;at(open_index)-&gt;h;
                  }
              }
  }
  void solve(board *goal, board *current){
      vector&lt;board *&gt; closed;
      vector&lt;board *&gt; open;
      //Initialize values of current
      current-&gt;g = 0;
      current-&gt;h = manhattan(goal,current);
      current-&gt;f = current-&gt;h;
      open.push_back(current);
  
      while(!open.empty()){
          //find entry in open with the lowest f value
          int lowest_index = 0;
          for(int i = 0; i &lt; open.size(); i++) {
              if(open[i]-&gt;f &lt; open[lowest_index]-&gt;f) {
                  lowest_index = i;
              }
          }
  
          board *x = open[lowest_index];
          board temp(x-&gt;rowSize, x-&gt;elements); 
          //board temp = *x;
          temp.boardSize = x-&gt;boardSize;
          temp.zeroIndex = x-&gt;zeroIndex;
          temp.upIndex = x-&gt;upIndex;
          temp.downIndex = x-&gt;downIndex;
          temp.leftIndex = x-&gt;leftIndex;
          temp.rightIndex = x-&gt;rightIndex;
          temp.g = x-&gt;g;
          temp.h = x-&gt;h;
          temp.f = x-&gt;f;
          x = &amp;temp;
          x-&gt;updateIndexes();
  
          printf("The value of x is  \n");
          for(int i = 0; i &lt; x-&gt;boardSize; i++){
              printf("%d", x-&gt;elements[i]);
          }
          cout &lt;&lt; endl;
          //stop if the goal has been reached
          if(x-&gt;h == goal-&gt;h) {
              //return answer
              return;
          }
  
          closed.push_back(x);
          open.erase(open.begin()+lowest_index);
          /*if(x-&gt;upIndex &gt;= 0){
              board *y = x;
              board temp_y(y-&gt;rowSize, y-&gt;elements);
              y = &amp;temp_y;
              y-&gt;moveUp();
              browseNeighbor(goal, y, &amp;open, &amp;closed);
          }
          if(x-&gt;downIndex &gt;= 0){
              board *y = x;
              board temp_y(y-&gt;rowSize, y-&gt;elements);
              y = &amp;temp_y;
              y-&gt;moveDown();
              browseNeighbor(goal, y, &amp;open, &amp;closed);
          }
          */
          if(x-&gt;leftIndex &gt;= 0){
              board *y = x;
              board temp_y(y-&gt;rowSize, y-&gt;elements);// = *y;
              temp_y.boardSize = y-&gt;boardSize;
              temp_y.zeroIndex = y-&gt;zeroIndex;
              temp_y.upIndex = y-&gt;upIndex;
              temp_y.downIndex = y-&gt;downIndex;
              temp_y.leftIndex = y-&gt;leftIndex;
              temp_y.rightIndex = y-&gt;rightIndex;
              temp_y.g = y-&gt;g;
              temp_y.h = y-&gt;h;
              temp_y.f = y-&gt;f;
              y = &amp;temp_y;
              y-&gt;moveLeft();
  
              y-&gt;updateIndexes();
              browseNeighbor(goal, y, &amp;open, &amp;closed);    
          }
          /*
          if(x-&gt;rightIndex &gt;= 0){
              board *y = x;
              board temp_y(y-&gt;rowSize, y-&gt;elements);
              y = &amp;temp_y;
              y-&gt;moveRight();
              browseNeighbor(goal, y, &amp;open, &amp;closed);
          }*/
      }
  }
  
  int main(){
      const int N = 3;
      int testArray[N*N] = {1,2,3,4,5,6,7,0,8}; //only need to move 8 to the left to solve
      int target[N*N] = {1,2,3,4,5,6,7,8,0}; //target state
  
      board a(N, target);
      board b(N, testArray);
      b.updateIndexes();
  
      board *goal = &amp;a;
      board *test = &amp;b;
  
      solve(goal, test);
  }
  </code></pre>