title: Hanoi Towers BackTracking bad_alloc
body: <p>I was reading  <a href="https://math.stackexchange.com/questions/1971574/generalized-problem-of-hanoi-towers">this post</a> and I tried to implement a backtracking algorithm on this version of Hanoi Towers, using the states defined in the first part of the post. Basically, it works for relative small numbers, but there are some cases when the program breaks out with the following error:</p>
  
  <blockquote>
    <p><code>terminate called after throwing an instance of std::bad_alloc 
       what(): bad_alloc
    This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information. 
    Process returned 3 (0x3)</code></p>
  </blockquote>
  
  <p>My attemp was done for <code>n = 7</code>, <code>m = 8</code>.</p>
  
  <p>I`m posting the entire code here, because it's a small one.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;map&gt;
  
  using namespace std;
  
  vector&lt;int&gt; get_initial_state(int n, int m)
  {
      vector&lt;int&gt; state(m+1, 1);
      state[0] = n;
      return state;
  }
  
  bool is_final_sate(vector&lt;int&gt; state, vector&lt;int&gt; fin_state)
  {
      if (state == fin_state)
          return true;
      return false;
  }
  
  int get_first_index_vector(vector&lt;int&gt; state, int val)
  {
      for (int i = 1; i &lt; state.size() ; ++ i)
          if (state[i] == val)
              return i;
      return state.size();
  }
  
  bool is_valid_transition(vector&lt;int&gt; state, int n, int m, int i, int j)
  {
      if (i &gt; n || j &gt; n)
          return false;
  
      int pos_i = get_first_index_vector(state, i);
      if (pos_i == state.size())
          return false;
  
      int pos_j = get_first_index_vector(state, j);
      if (pos_i &gt; pos_j)
          return false;
  
      return true;
  }
  
  vector&lt;int&gt; get_transition_state(vector&lt;int&gt; state, int n, int m, int i, int j)
  {
      if (is_valid_transition(state, n, m, i, j))
      {
          int first = get_first_index_vector(state, i);
          if (first &lt; state.size())
              state[first] = j;
      }
      return state;
  }
  
  bool backtrack_solver(vector&lt;int&gt; state, int n, int m, vector&lt;int&gt; fin_state, map&lt;vector&lt;int&gt;, bool &gt; visited, int length_sol)
  {
      if (is_final_sate(state, fin_state))
      {
          cout &lt;&lt; length_sol;
          return false;
      }
  
      /* in each state I try to move a disk from
       i-th rod to j-th rod */
      for (int i = 1; i &lt;= n; ++ i)
          for (int j = 1; j &lt;= n; ++ j)
          {
              if(i != j)
              {
                  vector&lt;int&gt; new_state = get_transition_state(state, n, m, i, j);
                  if (visited.find(new_state) == visited.cend())
                  {
                      visited.insert(make_pair(new_state, 1));
                      if (!backtrack_solver(new_state, n, m, fin_state, visited, length_sol +1))
                          return false;
                  }
              }
          }
      return true;
  }
  </code></pre>
  
  <p>And the main should be something like this:</p>
  
  <pre><code>int main()
  {
      int n = 7, m = 8;
      map&lt;vector&lt;int&gt;, bool&gt; visited;
      visited.insert(make_pair(get_initial_state(n,m), 1));
      vector&lt;int&gt; fin_state(m+1, n);
      backtrack_solver(get_initial_state(n,m), n, m, fin_state, visited, 0);
      return 0;
  }
  </code></pre>
  
  <p>What I've been trying: 
    At the begining, I thought it's about the huge number of recursive calls ,so I've set the stack size in my IDE (CodeBlocks 16.01), but no improvements. Then, I don't know, I still don't figure out how to solve it.</p>